1 #include<iostream> 2 #include<queue> 3 using namespace std; 4 typedef struct BinTree 5 { 6 char data; //节点信息 7 struct BinTree *lchild, *rchild; //左右孩子 8 9 } BiTNode, *BiTree; 10 //*BiTree的意思是给 struct node*起了个别名，叫BiTree， 11 //故BiTree为指向节点的指针。 12 13 //初始化二叉树，可以省略。 14 void InitBiTree(BiTree &T) 15 { 16 T = NULL; 17 } 18 19 //判断树是否为空 20 int EmptyBiTree(BiTree T) 21 { 22 if(!T) return 1; 23 else return 0; 24 } 25 26 //求树的深度 27 int DepthBiTree(BiTree T) 28 { 29 int count1, count2; 30 if(!T) return 0; 31 count1 = DepthBiTree(T->lchild); //数左子树深度 32 count2 = DepthBiTree(T->rchild); //数右子树深度 33 if(count1 > count2) return count1 + 1; //深度大的加上根节点 34 else return count2 + 1; 35 } 36 37 //求节点数 38 int NodeCount(BiTree T) 39 { 40 if(!T) return 0; 41 //左加右加根 42 else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1; 43 } 44 45 //销毁二叉树 46 void DestoryBiTree(BiTree &T) 47 { 48 if(!T) 49 { 50 if(T->lchild) 51 DestoryBiTree(T->lchild); 52 if(T->rchild) 53 DestoryBiTree(T->rchild); 54 delete(T); 55 T = NULL; 56 } 57 } 58 59 60 void ClearBiTree(BiTree &T) 61 { 62 if(T) 63 { 64 ClearBiTree(T->lchild); 65 ClearBiTree(T->rchild); 66 delete(T); 67 T = NULL; 68 } 69 } 70 71 //创建二叉树 72 void CreateBiTree(BiTree &T) 73 { 74 //&的意思是传进来节点指针的引用，括号内等价于 BiTreeNode* &T, 75 //目的是让传递进来的指针发生改变 76 77 char ch; //输入二叉树结点值 78 cin >> ch; 79 if(ch == '#') 80 T = NULL; //当遇到#时，令树的根节点为NULL, 81 //从而结束该"分支"的递归(如 a##表示a无子孩子) 82 else 83 { 84 T = new BiTNode; //先序遍历建立二叉树链表 85 T->data = ch; 86 CreateBiTree(T->lchild); 87 CreateBiTree(T->rchild); 88 } 89 } 90 91 //统计叶子节点 92 void CountLeaf(BiTree T, int &count) 93 { 94 if (T) 95 { 96 if ((!T->lchild) && (!T->rchild)) //左右子树都无 97 { 98 count++; 99 } 100 CountLeaf(T->lchild, count); 101 CountLeaf(T->rchild, count); 102 } 103 } 104 105 void PreTree(BiTree T) //先序遍历 106 { 107 if (T) 108 { 109 cout << T->data << ","; //根 110 PreTree(T->lchild); //左 111 PreTree(T->rchild); //右 112 } 113 } 114 void MidTree(BiTree T) //中序遍历 115 { 116 if (T) 117 { 118 MidTree(T->lchild); //左 119 cout << T->data << ","; //根 120 MidTree(T->rchild); //右 121 } 122 } 123 void PostTree(BiTree T) 124 { 125 if (T) 126 { 127 PostTree(T->lchild); //左 128 PostTree(T->rchild); //右 129 cout << T->data << ","; //根 130 } 131 } 132 133 //层次遍历 134 void LevelOrder(BiTree T) 135 { 136 queue<BiTree> q; //建立队列Q 137 q.push(T); //根节点入队 138 while(!q.empty()) 139 { 140 BiTree t = q.front(); 141 if (t->lchild) //将左子树入队 142 q.push(t->lchild); 143 if (t->rchild) //将右子树入队 144 q.push(t->rchild); 145 cout << t->data << " "; //输出队首 146 q.pop(); //队首出队 147 } 148 } 149 150 //查找 151 int FindBiTree(BiTree T, int e) 152 { 153 if(!T) return 0; 154 if((T->data == e)) return 1; 155 if(FindBiTree(T->lchild, e) || FindBiTree(T->rchild, e)) 156 return 1; 157 } 158 159 int main() 160 { 161 BiTree tree; 162 int count = 0; 163 cout << "初始化树 "; 164 InitBiTree(tree); 165 cout << "(1)This BiTree is " << (EmptyBiTree(tree) ? "Empty" : "Not Empty") << " now "; 166 cout << "(2)请输入二叉树(如ab##c##,即根节点为a,左孩子b,又孩子c)： "; 167 CreateBiTree(tree); 168 cout << "(3)树已建立。This BiTree is " << (EmptyBiTree(tree) ? "Empty" : "Not Empty") << " now "; 169 cout << "(4)树的节点总数为：" << NodeCount(tree) << endl; 170 CountLeaf(tree, count); 171 cout << "(5)树的叶子节点数为：" << count; 172 cout << " (6)树的深度为：" << DepthBiTree(tree); 173 cout << " (7)树的先序遍历为："; 174 PreTree(tree); 175 cout << " (8)树的中序遍历为："; 176 MidTree(tree); 177 cout << " (9)树的后序遍历为："; 178 PostTree(tree); 179 cout << " (10)树的层次遍历为："; 180 LevelOrder(tree); 181 cout << " (11)This BiTree is " << (EmptyBiTree(tree) ? "Empty" : "Not Empty") << " now "; 182 char x; 183 cout << "(12)请输入要查找的字符X:"; 184 cin >> x; 185 cout << (FindBiTree(tree, x) ? "Bingo" : "owl") << endl; 186 ClearBiTree(tree); 187 cout << "(13)已调用Clear()"; 188 cout << "(14)This BiTree is " << (EmptyBiTree(tree) ? "Empty" : "Not Empty") << endl; 189 return 0; 190 } 191 /* 192 请输入二叉树(如ab##c##,即根节点为a,左孩子b,又孩子c)： 193 abd##e##c## 194 树的叶子节点数为：3 195 树的先序遍历为：a,b,d,e,c, 196 树的中序遍历为：d,b,e,a,c, 197 树的后序遍历为：d,e,b,c,a, 198 */
结果如下：
