面试常考之二叉树
二叉树在数据结构面试中的地位举足轻重，算得上是大公司面试必问，笔试必考；因为对二叉树的操作直接反应一个人的数据结构功底有多深厚，基础知识是否扎实。。。（一点废话），下面就二叉树的基本操作说一说二叉树的知识点，不对之处还请指正。
面试常考的几个操作：
1：二叉树的基本性质
2：递归建立二叉树
3：递归遍历二叉树（先序，中序，后序）
4：非递归遍历二叉树（先序，中序，后序）
5：求二叉树中的节点个数
6：求二叉树的深度
7：分层遍历二叉树
8：求二叉树第K层的节点个数
9：求二叉树的镜像
10：测试源码
下面就常用的算法给大家讲解这些二叉树的基本性质。
说明：
所有代码使用C语言编写，头信息，常量如下：
1 ** 2 * 树的基本操作tree 3 */ 4 #include <stdio.h> 5 #include <stdlib.h> 6 #include <string.h> 7 8 #define ERROR -1 9 #define OK 1 10 #define OVERFLOW 2 11 #define STACK_INIT_SIZE 100 12 #define STACKINCREMENT 20 13 14 //最大队列长度 15 #define MAXQSIZE 100 16 17 typedef int Struct; 18 typedef char TElement; 19 typedef int Status; 20 int i = 0; //记录树初始化过程，数据的偏移 21 int j = 0; //记录树初始化过程，数据的偏移
二叉树结构体，以及栈、队列的结构体（层次遍历，非递归要用到）如下：
1 //二叉树结构体（二叉链表存储结构） 2 typedef struct BiNode{ 3 TElement data; 4 struct BiNode *lchild,*rchild; 5 }BiTNode, *BiTree; 6 7 //栈表示（用于非递归） 8 typedef struct{ 9 BiTree *base; 10 BiTree *top; 11 int stacksize; 12 }SqStack; 13 14 //使用队列，实现层次遍历 15 typedef struct QNode{ 16 BiTree data; 17 struct QNode *next; 18 }QNode, *QueuePtr; 19 20 typedef struct{ 21 QueuePtr front; 22 QueuePtr rear; 23 }LinkQueue;
1：二叉树的基本性质
一、二叉树第 i 层上最多有2 i-1 个节点
二、深度为 k 的二叉树，最多有2 k - 1个节点
三、对于任意一颗二叉树T,如果其终端节点数为n1度数为2的节点数为n2 则 n1 = n2 + 1;
四、具有n个节点的完全二叉树深度为[ log 2 n] + 1;
2： 递归建立二叉树
递归常见二叉树，先从左子树开始，arr 是调用传值过去的节点值，i 用于移动数组内的节点值
//创建二叉树 Struct CreateBiTree(BiTree &T, char arr[]){ if(arr[i] == ' '){ i++; T = NULL; }else{ T = (BiTree)malloc(sizeof(BiNode)); if(!T){ exit(ERROR);//分配空间失败； } T->data = arr[i]; i++; CreateBiTree(T->lchild, arr); CreateBiTree(T->rchild, arr); } return OK; }
3：递归遍历二叉树（先序，中序，后序）
这是三中常规的遍历二叉树的方法，用的非常多，不仅便于理解，而且三个函数只是调用顺序不同，所以书上页数先给出了这三种遍历。当然在面试中也长问到。
1 //先序遍历（递归方法） 2 int PrintTree(BiTree T){ 3 if(T){ 4 printf("%c ",T->data); 5 PrintTree(T->lchild); 6 PrintTree(T->rchild); 7 8 } 9 return OK; 10 } 11 12 //中序遍历（递归方法） 13 int PrintTreeL(BiTree T){ 14 if(T){ 15 PrintTreeL(T->lchild); 16 printf("%c ",T->data); 17 PrintTreeL(T->rchild); 18 } 19 return OK; 20 } 21 22 //后序遍历（递归方法） 23 int PrintTreeR(BiTree T){ 24 if(T){ 25 PrintTreeR(T->lchild); 26 PrintTreeR(T->rchild); 27 printf("%c ",T->data); 28 } 29 return OK; 30 }
4：非递归遍历二叉树（先序，中序，后序）
非递归遍历在面试中问的非常多，特别是大公司的面试，几乎是必问，所以这里就非递归的方法每个给出了两种
一、先序遍历：
先序遍历这里给出了两个方法，两种方法都是借助于栈来实现，具体的栈的操作在最后源程序中都有，看家可以看看，非递归的操作比递归麻烦得多，第一种方法是：首先根节点入栈，然后while循环一致判断栈是否为空，第二个while循环一直讲左节点入栈，知道左子树为空。其中 PopN(S); 方法是为了将多余的空元素弹出。第二种方法比较推荐开始根节点不入栈，先判断根节点是否为空，这样栈空间中不会有空元素，效率高一点，并且便于理解
1 //先序遍历（非递归方法）(方法1) 2 int PrintTree_Re(BiTree T){ 3 SqStack S; 4 InitStack(S);//建立栈 5 Push(S,T); //树的根节点先入栈 6 BiTree P; 7 while(StackEmpty(S) == 1){ 8 while(GetTop(S,P) && P){ 9 printf("%c ",P->data); 10 Push(S,P->lchild); 11 } 12 PopN(S); 13 if(StackEmpty(S) == 1){ 14 Pop(S,P); 15 Push(S,P->rchild); 16 } 17 } 18 return OK; 19 } 20 21 //先序遍历（非递归方法）(方法2) 22 int PrintTree_Re_T(BiTree T){ 23 SqStack s; 24 InitStack(s); 25 BiTree p; 26 p = T; 27 while(p || StackEmpty(s) == 1){ 28 while(p){ 29 printf("%c ",p->data); 30 Push(s,p); 31 p = p->lchild; 32 } 33 if(StackEmpty(s) == 1){ 34 Pop(s,p); 35 p = p->rchild; 36 } 37 } 38 return OK; 39 }
二、中序遍历：
中序遍历这里也给出2种方法。感觉和先序差不多，只是遍历顺序不同，处理的时候方式一样，这里不再多说。
1 //中序遍历（非递归）（方法1） 2 int PrintTreeL_Re(BiTree T){ 3 SqStack S; 4 InitStack(S);//建立栈 5 Push(S,T); //树的根节点先入栈 6 BiTree P; 7 while(StackEmpty(S) == 1){ 8 while(GetTop(S,P) && P){ 9 Push(S,P->lchild); 10 } 11 PopN(S); 12 if(StackEmpty(S) == 1){ 13 Pop(S,P); 14 printf("%c ",P->data); 15 Push(S,P->rchild); 16 } 17 } 18 return OK; 19 } 20 21 //中序遍历（非递归）（方法2） 22 int PrintTreeL_Re_T(BiTree T){ 23 SqStack S; 24 InitStack(S);//建立栈 25 BiTree P; 26 P = T; 27 while(P || StackEmpty(S) == 1){ 28 if(P){ 29 Push(S,P); 30 P = P->lchild; 31 }else{ 32 Pop(S,P); 33 printf("%c ",P->data); 34 P = P->rchild; 35 } 36 } 37 return OK; 38 }
二、后序遍历：
个人感觉后序遍历的非递归是三种遍历方式中最难的。写了很长时间，总感觉找不到一种合适的方法来保证孩子节点完全遍历。下面来说说这种非递归的遍历。其实会了也比较简单，对于结点P， 要保证根结点在左孩子和右孩子访问之后才能访问 ，先将其入栈。如果P不存在左孩子和右孩子，可以直接访问；或者P 存在左孩子或者右孩子，访问过左孩子和右孩子后可以直接访问该结点。其他情况，则将P的右孩子和左孩子依次入栈。这个就会这一种，应该有其他方法，欢迎指出
1 //后序遍历（非递归方法） 2 int PrintTreeR_Re(BiTree T){ 3 SqStack s; 4 InitStack(s);//建立栈 5 Push(s,T); //树的根节点先入栈 6 BiTree p,q; 7 while(StackEmpty(s) == 1){ 8 GetTop(s,p); 9 if((p->lchild == NULL && p->rchild == NULL) || ( q && ( q == p->lchild || q == p->rchild))){ 10 printf("%c ",p->data); 11 PopN(s); 12 q = p; 13 }else{ 14 if(p->rchild){ 15 Push(s,p->rchild); 16 } 17 if(p->lchild){ 18 Push(s,p->lchild); 19 } 20 } 21 } 22 return OK; 23 }
5：求二叉树中的节点个数
其实就是遍历一遍二叉树，不再多说，看程序便知
1 //统计二叉树节点的个数 2 void getTreeNodeNum(BiTree T,int &num){ 3 if(!T){ 4 num = 0; 5 } 6 num++; 7 if(T->lchild){ 8 getTreeNodeNum(T->lchild,num); 9 } 10 if(T->rchild){ 11 getTreeNodeNum(T->rchild,num); 12 } 13 }
6：求二叉树的深度
思想就是从左子树开始遍历，递归完整个树结构，如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1，参考代码如下：
1 //得到树的深度 2 int getTreeHeight(BiTree T){ 3 int hl,hr,max; 4 if(T!=NULL){ 5 hl=getTreeHeight(T->lchild); 6 hr=getTreeHeight(T->rchild); 7 max=hl>hr?hl:hr; 8 return (max+1); 9 }else{ 10 return 0; 11 } 12 }
7：分层遍历二叉树
一、树的层次结构分层打印与队列的的先进先出相似，所以我选择用队列来完成，首先根节点入队列，然后左孩子，又孩子以此入队列，打印即可
1 /*层次遍历二叉树（借助队列实现）*/ 2 void HierarchicalTree_Q(BiTree T){ 3 LinkQueue Q; 4 InitQueue(Q); //建立队列 5 EnQueue(Q,T); //树的根节点先入列 6 BiTree Ta; 7 while(Q.front != Q.rear){ 8 DeQueue(Q,Ta); 9 if(Ta->lchild){ 10 EnQueue(Q,Ta->lchild); 11 } 12 if(Ta->rchild){ 13 EnQueue(Q,Ta->rchild); 14 } 15 printf("%c ",Ta->data); 16 } 17 }
二、说到分层如果打印树的真实结构应该也可以，所以我想借助堆栈来实现，有兴趣的可以看一下，思想：其实和层次遍历一样，最难的是怎样控制换行先，我的想法是创建一个标志位*，当前行入栈完毕就插入标志位*遍历一个节点就把左孩子和右孩子入栈，以此一层一层的打印，代码检验过，不知道还有没有错误，欢迎指正
1 /*层次遍历二叉树（并且分层打印）（借助栈实现）*/ 2 void HierarchicalTree_DA(BiTree T){ 3 LinkQueue Q; 4 InitQueue(Q);//建立队列 5 EnQueue(Q,T);//树的根节点先入列 6 BiTree Ta1,Tb1,Tc1; 7 8 //创建标志位 9 char data[3] = {'*',' ',' '}; 10 CreateBiTree(Ta1,data); 11 12 //创建移动的指针 13 QueuePtr point; 14 point = Q.front->next;//移动指针先指向头结点 15 EnQueue(Q,Ta1);//插入标志位 16 printf("/n"); 17 while(point){ 18 //判断左右节点 19 if(point->data->lchild || point->data->rchild){ 20 if(point->data->lchild){ 21 EnQueue(Q,point->data->lchild); 22 } 23 if(point->data->rchild){ 24 EnQueue(Q,point->data->rchild); 25 } 26 } 27 point = point->next; //指针下移一位 28 if(point->data->data == '*'){ 29 if(!point->next){//判断是否到结尾（到结尾直接退出） 30 break; 31 } 32 EnQueue(Q,Ta1);//插入标志节点 33 point = point->next; //如果遇到标志位，则指针下移 34 } 35 } 36 37 printf("/n"); 38 //循环输出节点 39 while(Q.front != Q.rear){ 40 DeQueue(Q,Tc1); 41 char str = Tc1->data; 42 if(str == '*'){ 43 printf("/n"); 44 }else{ 45 printf("%c ",str); 46 } 47 } 48 }
8：求二叉树第K层的节点个数
利用递归的次数来（孩子节点不为空 的条件 ）来简介得到k层节点的个数，比较简单，代码如下
1 //得到第k层的节点个数 2 int getNodeNum(BiTree T, int k){ 3 if (!T || k < 1){ 4 return 0; 5 } 6 if (k == 1){ 7 return 1; 8 } 9 return getNodeNum(T->lchild, k-1) + getNodeNum(T->rchild, k-1); 10 }
9：求二叉树的镜像
所谓的镜像其实就是左子树和右子树互换颠倒，如下面代码。
1 //写出二叉树的镜像 2 void getNoClone(BiTree &T){ 3 BiTree Ta; 4 if(T){ 5 Ta = T->lchild; 6 T->lchild = T->rchild; 7 T->rchild = Ta; 8 getNoClone(T->lchild); 9 getNoClone(T->rchild); 10 } 11 }
10：测试源码
最后附上完整的测试代码，其中包含了，队列的初始化，插入队列，出队列操作，栈的初始化，进栈，出栈，得到栈顶元，树的初始化素等也可以复习一下。中间可定有不对不足的地方，还望大神们多多指正
1 /** 2 * 树的基本操作tree 3 */ 4 #include <stdio.h> 5 #include <stdlib.h> 6 #include <string.h> 7 8 #define ERROR -1 9 #define OK 1 10 #define OVERFLOW 2 11 #define STACK_INIT_SIZE 100 12 #define STACKINCREMENT 20 13 14 //最大队列长度 15 #define MAXQSIZE 100 16 17 typedef int Struct; 18 typedef char TElement; 19 typedef int Status; 20 int i = 0; //记录树初始化过程，数据的偏移 21 int j = 0; //记录树初始化过程，数据的偏移 22 23 24 //二叉树结构体（二叉链表存储结构） 25 typedef struct BiNode{ 26 TElement data; 27 struct BiNode *lchild,*rchild; 28 }BiTNode, *BiTree; 29 30 //栈表示 31 typedef struct{ 32 BiTree *base; 33 BiTree *top; 34 int stacksize; 35 }SqStack; 36 37 //使用队列，实现层次遍历 38 typedef struct QNode{ 39 BiTree data; 40 struct QNode *next; 41 }QNode, *QueuePtr; 42 43 typedef struct{ 44 QueuePtr front; 45 QueuePtr rear; 46 }LinkQueue; 47 48 49 //初始化队列 50 Status InitQueue(LinkQueue &Q){ 51 Q.front = Q.rear = (QueuePtr)malloc(sizeof(BiTree));//动态分配空间 52 if(!Q.front){ 53 exit(ERROR);//分配空间失败 54 } 55 Q.front->next = NULL; 56 return OK; 57 } 58 59 //在队尾插入新元素 60 Status EnQueue(LinkQueue &Q, BiTree e){ 61 QueuePtr p; 62 p = (QueuePtr)malloc(sizeof(BiTree)); 63 if(!p){ 64 exit(ERROR);//分配失败 65 } 66 p->data = e; 67 p->next = NULL; 68 Q.rear->next = p; 69 Q.rear = p; 70 return OK; 71 } 72 73 //删除队头元素,并用e返回 74 void DeQueue(LinkQueue &Q,BiTree &e){ 75 76 if(Q.front != Q.rear){//先判断队列是否为空 77 QueuePtr p; 78 e = Q.front->next->data; 79 if(Q.front->next == Q.rear){//队列只有一个元素 80 p = Q.rear; 81 Q.rear = Q.front; 82 Q.front->next = NULL; 83 }else{ 84 p = Q.front->next; 85 Q.front->next = p->next; 86 p->next = NULL; 87 } 88 //free(p->data); 89 } 90 } 91 92 //创建二叉树 93 Struct CreateBiTree(BiTree &T, char arr[]){ 94 if(arr[i] == ' '){ 95 i++; 96 T = NULL; 97 }else{ 98 T = (BiTree)malloc(sizeof(BiNode)); 99 if(!T){ 100 exit(ERROR);//分配空间失败； 101 } 102 T->data = arr[i]; 103 i++; 104 CreateBiTree(T->lchild, arr); 105 CreateBiTree(T->rchild, arr); 106 } 107 return OK; 108 } 109 110 //先序遍历（递归方法） 111 int PrintTree(BiTree T){ 112 if(T){ 113 printf("%c ",T->data); 114 PrintTree(T->lchild); 115 PrintTree(T->rchild); 116 117 } 118 return OK; 119 } 120 121 //中序遍历（递归方法） 122 int PrintTreeL(BiTree T){ 123 if(T){ 124 PrintTreeL(T->lchild); 125 printf("%c ",T->data); 126 PrintTreeL(T->rchild); 127 } 128 return OK; 129 } 130 131 //后序遍历（递归方法） 132 int PrintTreeR(BiTree T){ 133 if(T){ 134 PrintTreeR(T->lchild); 135 PrintTreeR(T->rchild); 136 printf("%c ",T->data); 137 } 138 return OK; 139 } 140 141 142 //初始化栈 143 Struct InitStack(SqStack &S){ 144 S.base = (BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree)); 145 S.top = S.base; 146 if(!S.base){ 147 exit(ERROR);//分配失败 148 } 149 S.stacksize = STACK_INIT_SIZE; 150 return OK; 151 } 152 153 //push入栈操作 154 Struct Push(SqStack &S, BiTree T){ 155 if(S.top - S.base >= S.stacksize){ 156 S.base = (BiTree *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(BiTree)); 157 if(!S.base){ 158 exit(ERROR); 159 } 160 S.top = S.base + S.stacksize; 161 S.stacksize += STACKINCREMENT; 162 } 163 *S.top = T; 164 S.top++; 165 166 return OK; 167 } 168 169 //出栈操作 170 Struct Pop(SqStack &S,BiTree &P){ 171 if(S.base != S.top){ 172 P = *(--S.top); 173 } 174 return OK; 175 } 176 177 //出栈操作 178 Struct PopN(SqStack &S){ 179 if(S.base != S.top){ 180 --S.top; 181 } 182 return OK; 183 } 184 185 //得到栈顶元素操作 186 Struct GetTop(SqStack S,BiTree &P){ 187 if(S.base != S.top){ 188 P = *(S.top - 1); 189 } 190 return OK; 191 } 192 193 //判断是否是空栈 194 int StackEmpty(SqStack S){ 195 if(S.base != S.top){ 196 return 1; 197 }else{ 198 return 0; 199 } 200 } 201 202 //返回栈长度 203 int GetLength(SqStack S){ 204 return S.top - S.base; 205 } 206 207 //先序遍历（非递归方法）(方法1) 208 int PrintTree_Re(BiTree T){ 209 SqStack S; 210 InitStack(S);//建立栈 211 Push(S,T); //树的根节点先入栈 212 BiTree P; 213 while(StackEmpty(S) == 1){ 214 while(GetTop(S,P) && P){ 215 printf("%c ",P->data); 216 Push(S,P->lchild); 217 } 218 PopN(S); 219 if(StackEmpty(S) == 1){ 220 Pop(S,P); 221 Push(S,P->rchild); 222 } 223 } 224 return OK; 225 } 226 227 //先序遍历（非递归方法）(方法2) 228 int PrintTree_Re_T(BiTree T){ 229 SqStack s; 230 InitStack(s); 231 BiTree p; 232 p = T; 233 while(p || StackEmpty(s) == 1){ 234 while(p){ 235 printf("%c ",p->data); 236 Push(s,p); 237 p = p->lchild; 238 } 239 if(StackEmpty(s) == 1){ 240 Pop(s,p); 241 p = p->rchild; 242 } 243 } 244 return OK; 245 } 246 247 //中序遍历（非递归）（方法1） 248 int PrintTreeL_Re(BiTree T){ 249 SqStack S; 250 InitStack(S);//建立栈 251 Push(S,T); //树的根节点先入栈 252 BiTree P; 253 while(StackEmpty(S) == 1){ 254 while(GetTop(S,P) && P){ 255 Push(S,P->lchild); 256 } 257 PopN(S); 258 if(StackEmpty(S) == 1){ 259 Pop(S,P); 260 printf("%c ",P->data); 261 Push(S,P->rchild); 262 } 263 } 264 return OK; 265 } 266 267 //中序遍历（非递归）（方法2） 268 int PrintTreeL_Re_T(BiTree T){ 269 SqStack S; 270 InitStack(S);//建立栈 271 BiTree P; 272 P = T; 273 while(P || StackEmpty(S) == 1){ 274 if(P){ 275 Push(S,P); 276 P = P->lchild; 277 }else{ 278 Pop(S,P); 279 printf("%c ",P->data); 280 P = P->rchild; 281 } 282 } 283 return OK; 284 } 285 286 //后序遍历（非递归方法） 287 int PrintTreeR_Re(BiTree T){ 288 SqStack s; 289 InitStack(s);//建立栈 290 Push(s,T); //树的根节点先入栈 291 BiTree p,q; 292 while(StackEmpty(s) == 1){ 293 GetTop(s,p); 294 if((p->lchild == NULL && p->rchild == NULL) || ( q && ( q == p->lchild || q == p->rchild))){ 295 printf("%c ",p->data); 296 PopN(s); 297 q = p; 298 }else{ 299 if(p->rchild){ 300 Push(s,p->rchild); 301 } 302 if(p->lchild){ 303 Push(s,p->lchild); 304 } 305 } 306 } 307 return OK; 308 } 309 310 311 /*层次遍历二叉树*/ 312 void HierarchicalTree(BiTree T){ 313 BiTree Ta = T; 314 if(Ta){ 315 printf("%c ",Ta->data); 316 if(Ta->lchild){ 317 //printf("%c ",Ta->lchild->data); 318 HierarchicalTree(Ta->lchild); 319 } 320 if(Ta->rchild){ 321 //printf("%c ",Ta->rchild->data); 322 HierarchicalTree(Ta->rchild); 323 } 324 } 325 } 326 327 /*层次遍历二叉树（借助队列实现）*/ 328 void HierarchicalTree_Q(BiTree T){ 329 LinkQueue Q; 330 InitQueue(Q); //建立队列 331 EnQueue(Q,T); //树的根节点先入列 332 BiTree Ta; 333 while(Q.front != Q.rear){ 334 DeQueue(Q,Ta); 335 if(Ta->lchild){ 336 EnQueue(Q,Ta->lchild); 337 } 338 if(Ta->rchild){ 339 EnQueue(Q,Ta->rchild); 340 } 341 printf("%c ",Ta->data); 342 } 343 } 344 345 /*层次遍历二叉树（并且分层打印）（借助栈实现）*/ 346 void HierarchicalTree_DA(BiTree T){ 347 LinkQueue Q; 348 InitQueue(Q);//建立队列 349 EnQueue(Q,T);//树的根节点先入列 350 BiTree Ta1,Tb1,Tc1; 351 352 //创建标志位 353 char data[3] = {'*',' ',' '}; 354 CreateBiTree(Ta1,data); 355 356 //创建移动的指针 357 QueuePtr point; 358 point = Q.front->next;//移动指针先指向头结点 359 EnQueue(Q,Ta1);//插入标志位 360 printf("/n"); 361 while(point){ 362 //判断左右节点 363 if(point->data->lchild || point->data->rchild){ 364 if(point->data->lchild){ 365 EnQueue(Q,point->data->lchild); 366 } 367 if(point->data->rchild){ 368 EnQueue(Q,point->data->rchild); 369 } 370 } 371 point = point->next; //指针下移一位 372 if(point->data->data == '*'){ 373 if(!point->next){//判断是否到结尾（到结尾直接退出） 374 break; 375 } 376 EnQueue(Q,Ta1);//插入标志节点 377 point = point->next; //如果遇到标志位，则指针下移 378 } 379 } 380 381 printf("/n"); 382 //循环输出节点 383 while(Q.front != Q.rear){ 384 DeQueue(Q,Tc1); 385 char str = Tc1->data; 386 if(str == '*'){ 387 printf("/n"); 388 }else{ 389 printf("%c ",str); 390 } 391 } 392 } 393 394 //统计二叉树节点的个数 395 void getTreeNodeNum(BiTree T,int &num){ 396 if(!T){ 397 num = 0; 398 } 399 num++; 400 if(T->lchild){ 401 getTreeNodeNum(T->lchild,num); 402 } 403 if(T->rchild){ 404 getTreeNodeNum(T->rchild,num); 405 } 406 } 407 408 //得到树的深度 409 int getTreeHeight(BiTree T){ 410 int hl,hr,max; 411 if(T!=NULL){ 412 hl=getTreeHeight(T->lchild); 413 hr=getTreeHeight(T->rchild); 414 max=hl>hr?hl:hr; 415 return (max+1); 416 }else{ 417 return 0; 418 } 419 } 420 421 //得到第k层的节点个数 422 int getNodeNum(BiTree T, int k){ 423 if (!T || k < 1){ 424 return 0; 425 } 426 if (k == 1){ 427 return 1; 428 } 429 return getNodeNum(T->lchild, k-1) + getNodeNum(T->rchild, k-1); 430 } 431 432 void main(){ 433 i = 0; 434 //char Data[15] = {'A','B','C',' ',' ','D','E',' ','G',' ',' ','F',' ',' ',' '}; 435 //char Data[15] = {'A','B','C',' ',' ','D','E',' ',' ','G',' ',' ','F',' ',' '}; 436 char Data[16] = {'A','B','C',' ',' ',' ','D','E',' ','G',' ',' ','F',' ',' ',' '}; 437 //char Data[7] = {'A','B','C',' ',' ',' ',' '}; 438 //char Data[7] = {'A',' ','b',' ','c',' ',' '}; 439 BiTree Ta,Tb; 440 CreateBiTree(Ta,Data); 441 printf("*****************递归方法遍历二叉树**************/n"); 442 printf("先序遍历："); 443 PrintTree(Ta); 444 445 printf("/n"); 446 printf("中序遍历："); 447 PrintTreeL(Ta); 448 449 printf("/n"); 450 printf("后序遍历："); 451 PrintTreeR(Ta); 452 printf("/n"); 453 454 printf("非递归先序遍历法1："); 455 PrintTree_Re(Ta); 456 printf("/n"); 457 458 printf("非递归先序遍历法2："); 459 PrintTree_Re_T(Ta); 460 printf("/n"); 461 462 printf("非递归中序遍历法1："); 463 PrintTreeL_Re(Ta); 464 printf("/n"); 465 466 printf("非递归中序遍历法2："); 467 PrintTreeL_Re_T(Ta); 468 printf("/n"); 469 470 printf("非递归后序遍历："); 471 PrintTreeR_Re(Ta); 472 printf("/n"); 473 474 printf("层次遍历："); 475 HierarchicalTree_Q(Ta); 476 printf("/n"); 477 478 printf("/n"); 479 printf("层次遍历（分层显示）："); 480 i = 0; 481 HierarchicalTree_DA(Ta); 482 printf("/n"); 483 484 printf("总结点个数："); 485 int TreeNum = 0; 486 getTreeNodeNum(Ta,TreeNum); 487 printf("%d ",TreeNum); 488 printf("/n"); 489 490 printf("树的深度："); 491 int TreeHeight = 0; 492 TreeHeight = getTreeHeight(Ta); 493 printf("%d ",TreeHeight); 494 printf("/n"); 495 496 printf("得到第3层的节点个数："); 497 printf("%d",getNodeNum(Ta,3)); 498 printf("/n"); 499 500 }
运行结果：
转载请注明出处，谢谢！
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
