二叉树的递归遍历
1. 二叉树的链式结构
2. 二叉树的遍历
2.1 二叉树的前序遍历
2.2 二叉树的中序遍历
2.3 二叉树的后序遍历
2.4 二叉树的层序遍历（难点）
3. 二叉树节点的个数
4.二叉树叶子节点的个数
5.二叉树第k层节点的个数
6.二叉树前k层节点的个数
7. 二叉树查找值为x的节点
8. 求二叉树的最大深度
9. 判断二叉树是否是完全二叉树
10. 销毁二叉树
11. 由二叉树的遍历序列构造二叉树
12. 总结
1. 二叉树的链式结构
二叉树节点的结构：
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
二叉树是：
- 空树
- 非空：根节点，根节点的左子树、根节点的右子树组成的。
- 因此，为了快速闯创建二叉树，我们以下图为模板：（注：下述遍历以此图讲述）
将其用代码实现：
BTNode* CreateTree()//创建二叉树 { BTNode* n1 = (BTNode*)malloc(sizeof(BTNode)); assert(n1); BTNode* n2 = (BTNode*)malloc(sizeof(BTNode)); assert(n2); BTNode* n3 = (BTNode*)malloc(sizeof(BTNode)); assert(n3); BTNode* n4 = (BTNode*)malloc(sizeof(BTNode)); assert(n4); BTNode* n5 = (BTNode*)malloc(sizeof(BTNode)); assert(n5); BTNode* n6 = (BTNode*)malloc(sizeof(BTNode)); assert(n6); n1->data = 1; n2->data = 2; n3->data = 3; n4->data = 4; n5->data = 5; n6->data = 6; n1->left = n2; n1->right = n4; n2->left = n3; n2->right = NULL; n3->left = NULL; n3->right = NULL; n4->left = n5; n4->right = n6; n5->left = NULL; n5->right = NULL; n6->left = NULL; n6->right = NULL; return n1; }
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
2. 二叉树的遍历
前中后序遍历是按照递归实现。层序遍历
2.1二叉树的前序遍历
前序遍历：即按照：根->左子树->右子树 的顺序访问。
意为访问一条路上所有的根，再访问所有的左子树，最后访问所有的右子树。
前序遍历递归图解：
访问的顺序为 ： 1、2、3、NULL、NULL 、NULL、4、5、NULL 、NULL、6、NULL、NULL 。
即按照递归调用的实际顺序：
代码实现：
//二叉树前序遍历 void PreOrder(BTNode* root) { if (root == NULL)//递归结束条件 { printf("NULL "); return; } printf("%d ", root->data);//先打印 PreOrder(root->left);//左子树遍历 PreOrder(root->right);//右子树遍历 }
有的描述中可能不含有NULL,碰到root == NULL 直接return,但是打印NULL这样才能让我们更容易理解。
对于递归这里，就个人而言，由于每一步递归的方式都相同。我更喜欢把它进行形象化的假设。就此结构，有多个分支，6个节点，但是我会将他看成一个根节点和两个子树:
或者更加精确一点，即一个根节点，两个树叶：
如果只看成这样，那就是先打印根，再按照相同的方式访问left、right即可
将这个以前序遍历打印的形式实现的话，代码是这样：
有的描述中可能不含有NULL,碰到root == NULL 直接return,但是打印NULL这样才能让我们更容易理解。
printf("%d ", root->data);//先打印 printf("%d ", root->left->data);//左子叶打印 printf("%d ", root->right->data);//右子叶打印
再看一下前序遍历的主体代码：
printf("%d ", root->data);//先打印 PreOrder(root->left);//左子树遍历 PreOrder(root->right);//右子树遍历
不难发现，两个的区别就是在left和right时的方式不一样，一个是递归，一个是直接打印，但终究的思想还是一样的。将思路化繁为简，把递归看成一步，再由这一步通过递归化成无数步，才是递归的精髓。由于递归不能一直进行，因此才有了root == NULL的结束条件。
即递归有两个必要的条件：
- 递归的方式（如何递归）
- 截止条件（通过题干了解什么时候该从下往上返回）
2.2二叉树的中序遍历
中序遍历：即按照： 左子树->根->右子树 的顺序访问。
仍然是这个二叉树，根据中序遍历的条件，先访问的应该是1的左子树，然后访问1，最后访问1的右子树。当我们看到2也就是1的左子树的根时，发现2仍然作为左子树的根，因此，访问时应该先访问2的左子树，再访问2，最后访问2的右子树。当我们看到3也就是2的左子树的根时，其左子树右子树都为空，但仍相当于有左右子树，仍然先访问3的左子树，再访问3，最后访问3的右子树。因此，左子树->根->右子树的打印的顺序如下：
①-> ②-> ③-> ④-> ⑤-> ⑥-> ⑦-> ⑧-> ⑨-> ⑩-> ⑪-> ⑫-> ⑬
NULL->3->NULL->2->NULL->1->NULL->5->NULL->4->NULL->6->NULL
事实上，中序遍历的代码也与所描述的递归顺序一样，对比前序，只有顺序上的差别。
二叉树的中序遍历的风格与前序遍历相同，只不过在顺序上有了变化，通过对于前序遍历递归的理解，这里采用上述提到的由简到繁的思维帮助实现。
先思考一下只有两层的二叉树：
那么代码打印的方式为：
void InOrder(BTNode* root) { printf("%d ", root->left->data);//打印左孩子 printf("%d ", root->data);//打印根 printf("%d ", root->right->data);//打印右孩子 }
通过一层的方式改变成多层，因此改成递归，将打印替换成递归，并加上截止条件：
//二叉树中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left);//将left的改成递归 printf("%d ", root->data); InOrder(root->right);//将right的改成递归 }
通过上述的一系列探讨，为什么前序中序都这么改递归呢，为什么改左右呢？当然了，这个问题的答案是一边写一边思考的，写到这里也算是发现了其中的一些规律吧。首先，对于递归，看重的除了递归方式和截止条件之外，还需要看该递归函数传的参数，此代码参数为root，第一次调用的即我们所认为的根，对于每层调用的参数本身（即root），是需要进行你想要的运算的，毕竟是你传进来的参数，而当我们在这层函数中继续传参，按照此代码的root->left 和root->right 继续传进去之后，一样会变成下一层的root ，因此，才说只需要将每一层的root该有的运算处理好，其左右的子树一样会处理好！
2.3 二叉树的后序遍历
中序遍历：即按照： 左子树->右子树->根 的顺序访问。
①-> ②-> ③-> ④->⑤-> ⑥-> ⑦-> ⑧-> ⑨-> ⑩-> ⑪->⑫->⑬
NULL->NULL->3->NULL>2>NULL->NULL->5->NULL->NULL->6->4->1
通过前面的大量探讨及描述，后序遍历直接写也已经可以写出来了，方式及思想与前面相同，可以直接写，也可以先按照两层的写，再改成递归。那么重复的话也不多说，直接上代码：
//二叉树的后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
2.4 二叉树的层序遍历（难点）
层序遍历： 除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
那么如何进行层序遍历呢？
这里直接引入：利用队列
队列具有先入先出的特性，当遍历二叉树的节点不为空，就将这个节点指针存入队列，当打印这个节点指向的数据时，由于遍历的特性，将这个节点指向的left和right拽到队列中，再弹出这个root 。那么我们具体展开试试。
因此，像如图这样的流程思想，同时注意需要强调理解的，我们则需要将队列的Queue.h,Queue.c引入。（与之前文章的队列对比，这个队列的data的类型变成了BTNode*.
Queue.h
#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;//只是将原data的int类型变成了这个节点的指针类型 typedef BTNode* QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { //int size; QNode* head; QNode* tail; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); bool QueueEmpty(Queue* pq); int QueueSize(Queue* pq);
Queue.c的功能不变，这里就不引入了。（队列的文章里面有）
接下来就是层序遍历的代码：
void TreeLevelOrder(BTNode* root)//层序遍历，利用队列 { //队列是用链表实现的，队列节点的data保存的是二叉树节点的指针 Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%d ", front->data); if (front->left)//递归思想 QueuePush(&q, front->left); if (front->right)//递归思想 QueuePush(&q, front->right); } printf("\n"); QueueDestory(&q); }
3. 二叉树节点的个数
对于求二叉树节点个数而言，为了遍历所有节点，仍需要递归。当然仍然可以利用我上文提到的思想：化繁为简，由简到繁 （emm……自己编的句子哈哈哈）化繁为简当然就是把n层就看成两层的思想，由简到繁就是将两层的代码以递归的方式写出来，就会变成n
即先看看两层
通过化繁为简，那么代码就可以写成这样：
int TreeSize(BTNode* root) { return 1+1+1;//可按顺序看成root->left+root->right+root }
再由简到繁，就是改成递归，求n层的节点个数：
//二叉树节点的个数 int TreeSize(BTNode* root) { if(root == NULL) return 0; return TreeSize(root->left) + TreeSize(root->right) + 1; //即相对于参数root,每层只针对root计数，root->left/right在递归中的下一层栈帧一定也会被调用。 }
当然，这里也可以采用static亦或是全局变量的形式，不过都有缺点，static的缺点是只有第一次是正确的的调用，全局变量则是每次计算之后都需要手动将其置为0。
4.二叉树叶子节点的个数
对于求叶子结点的个数，应该采取分治的思想。举个例子：有一位校长，两个院长，四个辅导员，八个班长，十六名普通同学，现在校长想统计普通同学的个数，让其下面的两个院长去计数，而每一位院长又让其直系的两个辅导员去计数，辅导员又让班长计数，最后经过班长通知，普通同学因此自己报上名字。这个例子中的普通同学就代表叶子结点，因此，只要遍历到最后一层的数，我们就返回1，相当于每一位同学报名字，除此之外不加1，因为只统计同学的数量，因此，代码可以通过这种思路实现了：
//求叶子节点个数（即求度为0的节点的个数） int TreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return TreeLeafSize(root->left) + TreeLeafSize(root->right); }
5.二叉树第k层节点的个数
这个问题相当于求叶子节点个数的进阶版本，因为当k为最后一层的代表时，即变成了求叶子节点的个数。事实上，与上一个函数相比，这个仅仅多了一次限制，假设k经过每一层减1，那么当k=1时，就得返回此层节点的个数了，对于每一个节点来说，同样与上一个相同，返回1。
int TreeLevel(BTNode* root, int k) { assert(k > 0); if (root == NULL) return 0; if (k == 1) return 1; k--; return TreeLevel(root->left, k) + TreeLevel(root->right, k); }
6.二叉树前k层节点的个数
相比较前一个函数，此函数仍然可以使用化繁为简的思想，即让根+左子树+右子树，直到k=1为止。思想上比上一个多加了子树的根。
int TreeLevelSum(BTNode* root, int k) { assert(k > 0); if (root == NULL) return 0; if (k == 1) return 1; k--; return TreeLevelSum(root->left, k) + TreeLevelSum(root->right, k) + 1;//左+右+根 }
