大热天敲代码与看书更配哦
数据结构系列 栈 https://hubojing.github.io/2017/11/14/%E6%A0%88/ 队列 https://hubojing.github.io/2017/11/12/%E9%98%9F%E5%88%97/ 线性表 https://hubojing.github.io/2019/06/12/%E7%BA%BF%E6%80%A7%E8%A1%A8/
二叉树的链式存储结构 1 2 3 4 typedef struct BiTNode { ElemType data; struct BiTNode *lchild , *rchild ; }BiTNode, *BiTree;
二叉树的遍历 例: 1 2 3 4 5 6
先序遍历(PreOrder) 根->左->右1 2 3 4 5 6 7 void PreOrder (BiTree T) { if (T != NULL ){ visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } }
124635
中序遍历(InOrder) 左->根->右1 2 3 4 5 6 7 void InOrder (BiTree T) { if (T != NULL ){ InOrder(T->lchild); visit(T); InOrder(T->rchild); } }
264135
后序遍历(PostOrder) 左->右->根1 2 3 4 5 6 7 8 void PostOrder (BiTree T) { if (T != NULL ) { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } }
642531
时间复杂度都是O(n),空间复杂度为O(n)。
中序遍历的非递归算法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void InOrder2 (BiTree T) { InitStack(S); BiTree p = T; while (p || !IsEmpty(S)){ if (p){ Push(S, p); p = p->lchild; } else { Pop(S, p); visit(p); p = p->rchild; } } }
二叉树的层次遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void LevelOrder (BiTree T) { InitQueue(Q); BiTree p; EnQueue(Q, T); while (!IsEmpty(Q)){ DeQueue(Q, p); visit(p); if (p->lchild != NULL ) { EnQueue(Q, p->lchild); } if (p->rchild != NULL ) { EnQueue(Q, p->rchild); } } }
树的存储结构 双亲表示法 1 2 3 4 5 6 7 8 9 #define MAX_TREE_SIZE 100 typedef struct { ElemType data; int parent; }PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE]; int n; }PTree;
求结点的孩子时需遍历整个结构。
孩子表示法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 typedef struct CTNode //孩子结点{ int child; struct CTNode *next ; }*ChildPtr; typedef struct { TElemType data; ChildPtr firstchild; }CTBox; typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; }CTree;
求结点的双亲时需遍历N个结点中孩子链表指针域所指向的N个孩子链表。
孩子兄弟表示法(二叉树表示法) 1 2 3 4 5 typedef struct CSNode { ElemType data; struct CSNode *firstchild , *nextsibling ; }CSNode, *CSTree;
易查找结点的孩子,若为每个结点增设一个parent域指向其父节点,则查找结点的父结点也很方便。
树转换为二叉树的规则:每个结点左指针指向它的第一个孩子结点,右指针指向它在树中的相邻兄弟结点,可表示为“左孩子右兄弟”。由于根节点没有兄弟,所以由树转换而得的二叉树没有右子树。
例:
一颗具体的树
转换后
C++实现 数组实现 tree.h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #ifndef TREE_H #define TREE_H class Tree { public : Tree(int size, int *pRoot); ~Tree(); int *SearchNode (int nodeIndex) ; bool AddNode (int nodeIndex, int direction, int *pNode) ; bool DeleteNode (int nodeIndex, int *pNode) ; void TreeTraverse () ; private : int *m_pTree; int m_iSize; }; #endif
tree.cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 #include <iostream> #include "tree.h" using namespace std ;Tree::Tree(int size, int *pRoot) { m_iSize = size; m_pTree = new int [size]; for (int i = 0 ; i < size; ++i) { m_pTree[i] = 0 ; } m_pTree[0 ] = *pRoot; } Tree::~Tree() { delete []m_pTree; m_pTree = NULL ; } int *Tree::SearchNode(int nodeIndex){ if (nodeIndex < 0 || nodeIndex >= m_iSize) { return NULL ; } if (m_pTree[nodeIndex] == 0 ) { return NULL ; } return &m_pTree[nodeIndex]; } bool Tree::AddNode(int nodeIndex, int direction, int *pNode){ if (nodeIndex < 0 || nodeIndex >= m_iSize) { return false ; } if (m_pTree[nodeIndex] == 0 ) { return false ; } if (direction == 0 ) { if (nodeIndex * 2 + 1 >= m_iSize) { return false ; } if (m_pTree[nodeIndex * 2 + 1 ] != 0 ) { return false ; } m_pTree[nodeIndex * 2 + 1 ] = *pNode; } if (direction == 1 ) { if (nodeIndex * 2 + 2 >= m_iSize) { return false ; } if (m_pTree[nodeIndex * 2 + 2 ] != 0 ) { return false ; } m_pTree[nodeIndex * 2 + 2 ] = *pNode; } } bool Tree::DeleteNode(int nodeIndex, int *pNode){ if (nodeIndex < 0 || nodeIndex >= m_iSize) { return false ; } if (m_pTree[nodeIndex] == 0 ) { return false ; } *pNode = m_pTree[nodeIndex]; m_pTree[nodeIndex] = 0 ; return true ; } void Tree::TreeTraverse(){ for (int i = 0 ; i < m_iSize; ++i) { cout << m_pTree[i] << " " ; } }
demo.cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <iostream> #include <stdlib.h> #include "tree.h" using namespace std ;int main () { int root = 1 ; Tree *pTree = new Tree(10 , &root); int node1 = 2 ; int node2 = 3 ; int node3 = 4 ; int node4 = 5 ; int node5 = 6 ; int node6 = 7 ; pTree->AddNode(0 , 0 , &node1); pTree->AddNode(0 , 1 , &node2); pTree->AddNode(1 , 0 , &node3); pTree->AddNode(1 , 1 , &node4); pTree->AddNode(2 , 0 , &node5); pTree->AddNode(2 , 1 , &node6); pTree->TreeTraverse(); int *p = pTree->SearchNode(2 ); cout << endl << "node = " << *p << endl ; delete pTree; return 0 ; }
链表实现 Node.h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #ifndef NODE_H #define NODE_H class Node { public : Node(); Node *SearchNode (int nodeIndex) ; void DeleteNode () ; void PreoderTraversal () ; void InorderTraversal () ; void PostorderTraversal () ; int index; int data; Node *pLChild; Node *pRChild; Node *pParent; }; #endif
Node.cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 #include "Node.h" #include <stdlib.h> #include <iostream> using namespace std ;Node::Node() { index = 0 ; data = 0 ; pLChild = NULL ; pRChild = NULL ; pParent = NULL ; } Node *Node::SearchNode(int nodeIndex) { if (this ->index == nodeIndex) { return this ; } Node *temp = NULL ; if (this ->pLChild != NULL ) { if (this ->pLChild->index == nodeIndex) { return this ->pLChild; } else { temp = this ->pLChild->SearchNode(nodeIndex); if (temp != NULL ) { return temp; } } } if (this ->pRChild != NULL ) { if (this ->pRChild->index == nodeIndex) { return this ->pRChild; } else { temp = this ->pRChild->SearchNode(nodeIndex); return temp; } } return NULL ; } void Node::DeleteNode(){ if (this ->pLChild != NULL ) { this ->pLChild->DeleteNode(); } if (this ->pRChild != NULL ) { this ->pRChild->DeleteNode(); } if (this ->pParent != NULL ) { if (this ->pParent->pLChild == this ) { this ->pParent->pLChild = NULL ; } } if (this ->pParent != NULL ) { if (this ->pParent->pRChild == this ) { this ->pParent->pRChild = NULL ; } } delete this ; } void Node::PreoderTraversal(){ cout << this ->index << " " << this ->data << endl ; if (this ->pLChild != NULL ) { this ->pLChild->PreoderTraversal(); } if (this ->pRChild != NULL ) { this ->pRChild->PreoderTraversal(); } } void Node::InorderTraversal(){ if (this ->pLChild != NULL ) { this ->pLChild->InorderTraversal(); } cout << this ->index << " " << this ->data << endl ; if (this ->pRChild != NULL ) { this ->pRChild->InorderTraversal(); } } void Node::PostorderTraversal(){ if (this ->pLChild != NULL ) { this ->pLChild->PostorderTraversal(); } if (this ->pRChild != NULL ) { this ->pRChild->PostorderTraversal(); } cout << this ->index << " " << this ->data << endl ; }
tree.h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #ifndef TREE_H #define TREE_H #include "Node.h" class Tree { public : Tree(); ~Tree(); Node *SearchNode (int nodeIndex) ; bool AddNode (int nodeIndex, int direction, Node *pNode) ; bool DeleteNode (int nodeIndex, Node *pNode) ; void PreoderTraversal () ; void InorderTraversal () ; void PostorderTraversal () ; private : Node *m_pRoot; }; #endif
tree.cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #include "tree.h" #include <stdlib.h> Tree::Tree() { m_pRoot = new Node(); } Tree::~Tree() { DeleteNode(0 , NULL ); } Node *Tree::SearchNode(int nodeIndex) { return m_pRoot->SearchNode(nodeIndex); } bool Tree::AddNode(int nodeIndex, int direction, Node *pNode){ Node *temp = SearchNode(nodeIndex); if (temp == NULL ) { return false ; } Node *node = new Node(); if (node == NULL ) { return false ; } node->index = pNode->index; node->data = pNode->data; node->pParent = temp; if (direction == 0 ) { temp->pLChild = node; } if (direction == 1 ) { temp->pRChild = node; } return true ; } bool Tree::DeleteNode(int nodeIndex, Node *pNode){ Node *temp = SearchNode(nodeIndex); if (temp == NULL ) { return false ; } if (pNode != NULL ) { pNode->data = temp->data; } temp->DeleteNode(); return true ; } void Tree::PreoderTraversal(){ m_pRoot->PreoderTraversal(); } void Tree::InorderTraversal(){ m_pRoot->InorderTraversal(); } void Tree::PostorderTraversal(){ m_pRoot->PostorderTraversal(); }
demo.cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <iostream> #include <stdlib.h> #include "tree.h" using namespace std ;int main () { Node *node1 = new Node(); node1->index = 1 ; node1->data = 5 ; Node *node2 = new Node(); node2->index = 2 ; node2->data = 4 ; Node *node3 = new Node(); node3->index = 3 ; node3->data = 3 ; Node *node4 = new Node(); node4->index = 4 ; node4->data = 2 ; Node *node5 = new Node(); node5->index = 5 ; node5->data = 1 ; Node *node6 = new Node(); node6->index = 6 ; node6->data = 7 ; Tree *tree = new Tree(); tree->AddNode(0 , 0 , node1); tree->AddNode(0 , 1 , node2); tree->AddNode(1 , 0 , node3); tree->AddNode(1 , 1 , node4); tree->AddNode(2 , 0 , node5); tree->AddNode(2 , 1 , node6); tree->DeleteNode(6 , NULL ); tree->PostorderTraversal(); delete tree; return 0 ; }
参考 数据结构教材数据结构与算法——普通树的定义与C++实现 C++树(兄弟孩子结构实现) VC++ 树的孩子兄弟表示法 使用C++ 和 孩子兄弟表示法实现树 孩子兄弟表示法实现树