放一个自己很久之前学习数据结构的时候写的一些二叉树相关的代码。
花了快有三个星期，当时写层次遍历是真的想了很久，然后调试bug又改了很久，不过最后还是做出来了。
1 //二叉树 2 3 # include<stdio.h> 4 # include<stdlib.h> 5 6 typedef char TElemType; 7 8 typedef struct BiTNode{ //二叉链表结构定义 9 TElemType date; 10 struct BiTNode * lchild, * rchild; 11 }BiTNode, * BiTree; 12 13 typedef struct QNode{ //队列结构定义 14 BiTree node; 15 struct QNode * next; 16 }QNode, * Queue; 17 18 typedef struct{ 19 Queue front; 20 Queue rear; 21 }LinkQ; 22 23 void CreateBinTree(BiTree &T)//建立一颗二叉树 （先序序列创建） 24 { 25 char ch; 26 scanf("%c", &ch); 27 if (ch=='#') T = NULL; //递归结束，建空树 28 else 29 { 30 T=new BiTNode; 31 T->date = ch; //生成根结点 32 CreateBinTree(T->lchild); //递归创建左子树 33 CreateBinTree(T->rchild); //递归创建右子树 34 } 35 } 36 37 int BinTreeEmpty(BiTree T)//判断一棵二叉树是否为空树。 38 { 39 if(T) return 1; 40 else return 0; 41 } 42 43 void PreOrderTraverse(BiTree T)//先序遍历二叉树T，并输出节点序列。 44 { 45 if(T) 46 { 47 printf("%c", T->date); 48 PreOrderTraverse(T->lchild); 49 PreOrderTraverse(T->rchild); 50 } 51 } 52 53 void InOrderTraverse(BiTree T)//中序遍历二叉树T，并输出节点序列。 54 { 55 if(T) 56 { 57 InOrderTraverse(T->lchild); 58 printf("%c", T->date); 59 InOrderTraverse(T->rchild); 60 } 61 } 62 63 void PostOrderTraverse(BiTree T)//后序遍历二叉树T，并输出节点序列。 64 { 65 if(T) 66 { 67 PostOrderTraverse(T->lchild); 68 PostOrderTraverse(T->rchild); 69 printf("%c", T->date); 70 } 71 } 72 73 void enter(BiTree T, LinkQ &q)//入队列 74 { 75 if(T == NULL) 76 return; 77 78 Queue p = new QNode;//创建新节点 79 if(!p) 80 { 81 printf("队列节点建立失败 "); 82 return; 83 } 84 p->node = T; 85 q.rear->next = p; 86 p->next = NULL; 87 q.rear = p; 88 } 89 90 void delqueue(LinkQ &q)//出队 91 { 92 Queue p = q.front->next;//保存要删除的头结点 93 q.front->next = q.front->next->next; 94 free(p); 95 } 96 97 void LevelOrderTraverse(BiTree T)//层次遍历二叉树T，并输出节点序列。 98 { 99 if (T == NULL) 100 return; 101 102 // BiTree tp = T;//树的工作指针 103 LinkQ lq; //队列的头尾指针 104 lq.front = lq.rear = new QNode;//队列初始化 105 if(!lq.front) 106 { 107 printf("队列初始化失败 "); 108 return; 109 } 110 111 enter(T, lq);//将树的根节点压入队列 112 while(lq.front != lq.rear && lq.front->next) 113 { 114 printf("%c", lq.front->next->node->date); 115 // tp = lq.front->next->node; 116 if(lq.front->next->node->lchild) 117 enter(lq.front->next->node->lchild, lq); 118 if(lq.front->next->node->rchild) 119 enter(lq.front->next->node->rchild, lq); 120 delqueue(lq); 121 } 122 printf(" "); 123 } 124 125 BiTree Value(BiTree T,TElemType e)//查找值为e的节点，并返回该节点的地址。 126 { 127 if((!T) || T->date == e) return T; 128 129 BiTree p = Value(T->lchild, e); 130 if(p) return p; 131 132 BiTree q = Value(T->rchild, e); 133 if(q) return q; 134 135 return NULL; 136 } 137 138 int BinTreeDepth(BiTree T)//返回二叉树的深度。 139 { 140 int m,n; 141 if(T == NULL) return 0; 142 else 143 { 144 m = BinTreeDepth(T->lchild ); 145 n = BinTreeDepth(T->rchild ); 146 if(m > n) return m+1; 147 else return n+1; 148 } 149 } 150 151 BiTree Parent(BiTree T,char e)//查找二叉树T中值为e的节点的双亲，若e为根节点，操作失败。 152 { 153 if (!T) return NULL; 154 if (T->lchild && T->lchild->date == e || T->rchild && T->rchild->date == e) return T; 155 156 BiTree p = Parent(T->lchild, e); 157 if(p) return p; 158 159 BiTree q = Parent(T->rchild, e); 160 if(q) return q; 161 162 return NULL; 163 } 164 165 BiTree LeftChild(BiTree T, TElemType e)//查找二叉树T中值为e的节点的左孩子，若e没有左孩子，则操作失败。 166 { 167 BiTree p = Value(T, e); 168 if(p) 169 { 170 printf("值为%c的节点找到 ", e); 171 return p->lchild; 172 } 173 else 174 { 175 printf("值为%c的节点未找到 ", e); 176 return NULL; 177 } 178 } 179 180 BiTree RightChild(BiTree T, TElemType e)//查找二叉树T中值为e的节点的右孩子，若e没有右孩子，则操作失败。 181 { 182 BiTree p = Value(T, e); 183 if(p) 184 { 185 printf("值为%c的节点找到 ", e); 186 return p->rchild; 187 } 188 else 189 { 190 printf("值为%c的节点未找到 ", e); 191 return NULL; 192 } 193 } 194 195 int CountNode(BiTree T)//计算二叉树中节点的个数。 196 { 197 if(T == NULL) //如果是空树返回 0 198 return 0; 199 return CountNode(T->lchild) + CountNode(T->rchild) + 1; 200 } 201 202 int Leaf(BiTree T)//计算二叉树中叶子节点的个数。 203 { 204 if(T == NULL) //如果是空树返回 0 205 return 0; 206 if (T->lchild == NULL && T->rchild == NULL) 207 return 1; //如果是叶子结点返回 1 208 return Leaf(T->lchild) + Leaf(T->rchild); 209 } 210 211 int OneChild(BiTree T)//计算二叉树中度为1的节点个数。 212 { 213 if(T == NULL) return 0; 214 if(T->lchild != NULL && T->rchild == NULL || T->lchild == NULL && T->rchild != NULL) 215 return OneChild(T->lchild) + OneChild(T->rchild) + 1; 216 return OneChild(T->lchild) + OneChild(T->rchild); 217 } 218 219 void menu_print(void) 220 { 221 printf("二叉树基本操作 "); 222 printf("------------------------------------------------ "); 223 printf("输入1 建立一颗二叉树。 "); 224 printf("输入2 判断一棵二叉树是否为空树。 "); 225 printf("输入3 先序遍历二叉树 "); 226 printf("输入4 中序遍历二叉树 "); 227 printf("输入5 后序遍历二叉树 "); 228 printf("输入6 层次遍历二叉树 "); 229 printf("输入7 查找值为e的节点，并返回该节点的地址。 "); 230 printf("输入8 返回二叉树的深度 "); 231 printf("输入9 查找二叉树T中值为e的节点的双亲 "); 232 printf("输入10 查找二叉树T中值为e的节点的左孩子 "); 233 printf("输入11 查找二叉树T中值为e的节点的右孩子 "); 234 printf("输入12 计算二叉树中节点的个数 "); 235 printf("输入13 计算二叉树中叶子节点的个数 "); 236 printf("输入14 计算二叉树中度为1的节点个数 "); 237 printf("请输入操作项 "); 238 } 239 int main(void) 240 { 241 BiTree T; 242 int i, mark = 1;//i为判断二叉树执行语句，mark为是否继续执行 243 char e;//查找值 244 BiTree p;//二叉树工作指针 245 do 246 { 247 system("cls"); 248 menu_print(); 249 scanf("%d", &i); 250 getchar();//吸收回车 251 switch (i) 252 { 253 case 1: 254 printf("请输入树的先序结果，用#表示空 "); 255 CreateBinTree(T);//建立一颗二叉树 （先序序列创建） 256 break; 257 case 2: 258 if(BinTreeEmpty(T))//判断一棵二叉树是否为空树。 259 printf("不是一颗空树 "); 260 else 261 printf("是一颗空树 "); 262 break; 263 case 3: 264 printf("先序遍历结果是："); 265 PreOrderTraverse(T);//先序遍历 266 printf(" "); 267 break; 268 case 4: 269 printf("中序遍历结果是："); 270 InOrderTraverse(T);//中序遍历 271 printf(" "); 272 break; 273 case 5: 274 printf("后序遍历结果是："); 275 PostOrderTraverse(T);//后序遍历 276 printf(" "); 277 break; 278 case 6: 279 printf("层次遍历结果是："); 280 LevelOrderTraverse(T);//层次遍历 281 printf(" "); 282 break; 283 case 7: 284 printf("请输入要查找的结点的值："); 285 e = getchar(); 286 p = Value(T,e);//查找值为e的节点 287 if(p) 288 printf("找到值为%c的节点为%o ", p->date, p); 289 else 290 printf("未找到值为%c的节点 ", e); 291 break; 292 case 8: 293 printf("二叉树的深度为：%d ", BinTreeDepth(T));//返回二叉树的深度 294 break; 295 case 9: 296 char a; 297 printf("请输入要查找的结点的值："); 298 a = getchar(); 299 p = Parent(T, a);//查找二叉树T中值为e的节点的双亲 300 if(p) 301 printf("找到值为%c的节点的双亲，其值为%c ", a, p->date); 302 else 303 printf("未找到该节点的"); 304 break; 305 case 10: 306 printf("请输入要查找的结点的值："); 307 e = getchar(); 308 p = LeftChild(T,e);//查找二叉树T中值为e的节点的左孩子 309 if(p) 310 printf("找到值为%c的节点的左孩子，其值为%c ", e, p->date); 311 else 312 printf("未找到该节点的左孩子 "); 313 break; 314 case 11: 315 printf("请输入要查找的结点的值："); 316 e = getchar(); 317 p = RightChild(T,e);//查找二叉树T中值为e的节点的右孩子 318 if(p) 319 printf("找到值为%c的节点的右孩子，其值为%c ", e, p->date); 320 else 321 printf("未找到该节点的右孩子 "); 322 break; 323 case 12: 324 printf("二叉树的节点的个数为%d ", CountNode(T));//计算二叉树中节点的个数 325 break; 326 case 13: 327 printf("二叉树的叶子节点的个数为%d ", Leaf(T));//计算二叉树中叶子节点的个数 328 break; 329 case 14: 330 printf("二叉树中度为1的节点个数为%d ", OneChild(T));//计算二叉树中度为1的节点个数 331 break; 332 default: 333 printf("输入错误 "); 334 break; 335 } 336 337 printf("输入0结束，或任意其他数字继续 "); 338 scanf("%d", &mark); 339 getchar();//吸收字符 340 } while(mark); 341 342 return 0; 343 }