一、二叉树剩余函数
1.1二叉树的层序遍历
层序遍历： 除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。 可以参考下图：
由上图不难看出，我们要控制函数一层一层的遍历二叉树。且普通递归都是会先遍历整个左子树，然后才会进入右子树。这里可以引用队列（先进先出）的概念，思路如下：
先将根节点地址入队列，然后利用循环，每当有节点出队列时就将此节点的左孩子(root -> left)的地址和右孩子(root -> right)的地址入队列（当然入队列的节点不为空，需要判断一下）。当队列为空时(while(!QueueEmpty(&q)))，就结束循环并销毁队列。主要还是利用队列的思想，只要想到就不难，代码如下：
//二叉树层序遍历 void BinaryTreeLevelOrder(TreeNode* root) { Queue q; QueueInit(&q); //根节点入队列 if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { //出队列 TreeNode* front = QueueFront(&q); QueuePop(&q); printf("%d ", front->val); //左右孩子判空，并入队列 if (root->left) QueuePush(&q, root->left); if (root->right) QueuePush(&q, root->right); } putchar('\n'); //销毁 QueueDestroy(&q); }
代码图解：
1.2判断二叉树是否为完全二叉树
这里先要介绍一下两种特殊的二叉树：
- 满二叉树： 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为
K，且结点总数是2^k-1， 则它就是满二叉树。 - 完全二叉树： 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有
n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。(即如果一棵树只有右节点没有左节点，那不能成为完全二叉树)。
根据上面的介绍，不难发现如果想要判断二叉树是否为完全二叉树，还是要一层一层的遍历二叉树。 既然如此，那么此函数还是可以使用队列来实现。代码设计思路：
第一步： 同样可以先创建队列并初始化，将第一个根节点的地址先入队列。同样执行循环，将一个节点出队列时，并将此节点的左孩子地址(root->left)和右孩子地址(root->right)都入队列。不同的是如果遇到空节点（无左孩子或右孩子便是NULL）同样要进入队列，并以队列为空(while (!QueueEmpty(&q)))作为循环结束条件（事实上此循环无法通过此条件结束）。在循环内部，如果接收到的出队列的节点为空，同样结束循环(break)。
至于遇到空节点，为什么要结束循环？因为我们判断的是完全二叉树，在进行层序遍历时，不会出现两个有效节点间还有一个空节点的情况（可以参考完全二叉树结构来思考！）。
第二步： 进行队列后续节点判断，同样可以依靠循环来不断出队列节点，当队列所出的节点不是空时(front != NULL)就直接销毁队列，并返回false；如果队列遍历到最后都没有发现空节点，那么便结束循环，销毁队列并返回true。
代码如下：
//判断树是否为完全二叉树 bool BinaryTreeComplete(TreeNode* root) { Queue q; QueueInit(&q); //根节点入队列 if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { //队首出队列 TreeNode* front = QueueFront(&q); QueuePop(&q); if (front == NULL) break; //左右孩子入队列 QueuePush(&q, root->left); QueuePush(&q, root->right); } //队列遇空，判断后续节点 while (!QueueEmpty(&q)) { TreeNode* front = QueueFront(&q); QueuePop(&q); //当还有非空节点时说明二叉树为非完全二叉树 //销毁并返回false if (front != NULL) { QueueDestroy(&q); return false; } } //直到队列为空，认为找到非空节点 //销毁队列并返回true QueueDestroy(&q); return true; }
代码图解：
有关层序遍历的例题：
- 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列（A）
为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF
解： 解此题首先要搞清，后序遍历和中序遍历的特性，（后序：左子树，右子树，根；中序：左子树，根，右子树），根据题目所描述的后序和中序遍历相同，那么这棵二叉树必定没有右子树。
既然这样，那么可以依据后序遍历确定根节点为F，然后依次判断以后节点。
1.3二叉树销毁
关于二叉树的销毁，可以使用后续遍历的思想。 因为如果先释放上层节点，那么下层的节点将无法寻到。如：free(root);，那么root便会变为野指针，root->left来找寻左子树也是非法的。
//二叉树的销毁 void BinaryDestroy(TreeNode* root) { if (!root) return; BinaryTreeDesTroy(root->left); BinaryTreeDesTroy(root->right); free(root); }
二、二叉树的构建及遍历OJ题
二叉树的构建及遍历，牛客刷题：KY11 二叉树遍历
题目描述： 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F###其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
解此题首先要创建二叉树的节点（值val，指向左孩子指针left，指向右孩子指针right）。然后根据字符串arr中的数据来，连接各个节点，需要注意的是要使用前序遍历来连接。至于为什么要传pi的地址？ 因为在递归过程中需要取到字符串arr不同下标位置的字符，传地址，在递归过程便可任意改变pi的值。代码如下：
#include <stdio.h> #include<stdlib.h> typedef char BTDataType; //二叉树节点 typedef struct BinaryTree { BTDataType val; struct BinaryTree* left; struct BinaryTree* right; }BTNode; //读取字符串，并连接二叉树各个节点 BTNode* BinaryTreeCreat(char* arr,int* pi) { if(arr[*pi] == '#') { (*pi)++; return NULL; } BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if(node == NULL) { perror("malloc()::fail"); exit(-1); } node->val = arr[*pi]; (*pi)++; node->left = BinaryTreeCreat(arr, pi); node->right = BinaryTreeCreat(arr, pi); return node; } //中序遍历打印 void BinaryTreeInOrder(BTNode* root) { if(root == NULL) return; BinaryTreeInOrder(root->left); printf("%c ",root->val); BinaryTreeInOrder(root->right); } int main() { char arr[101]; scanf("%s",arr); int pi = 0; BTNode* tree = BinaryTreeCreat(arr,&pi); BinaryTreeInOrder(tree); return 0; }
