【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
一、二叉树剩余函数
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;
}