面试常考之二叉树

二叉树在数据结构面试中的地位举足轻重，算得上是大公司面试必问，笔试必考；因为对二叉树的操作直接反应一个人的数据结构功底有多深厚，基础知识是否扎实。。。（一点废话），下面就二叉树的基本操作说一说二叉树的知识点，不对之处还请指正。

面试常考的几个操作：

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 ₂ 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 }

运行结果：

转载请注明出处，谢谢！