【初阶数据结构11】——链式二叉树知识补充
文章目录
前言
在上篇文章中，我们实现了二叉树的部分基本功能，三种遍历，以及统计高度、叶子节点数和指定高度的节点数。本篇文章我们将会完成二叉树的创建、销毁、层序遍历以及判断是否为完全二叉树等功能的实现。
1. 二叉树的层序遍历及相关应用
1.1 二叉树的层序遍历
除了上一篇文章中，介绍到的三种遍历方法，二叉树还存在一种广度遍历方法，即层序遍历。
1.1.1 层序遍历相关概念
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根结点所在 层数为1，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
// 层序遍历 void LevelOrder(Btnode* root)1.1.2 层序遍历的实现
不同于其他三种遍历方法，层序遍历需要借助堆来实现。具体思想：先将根节点放入堆中，然后利用堆的功能函数，输出对头数据，然后将该节点的非空子节点放入队列中，然后将队头节点出对，在进行下一轮循环，直到此时堆头元素为空。在实际实现中，我们将指向根节点的指针放入队中，一是为了节省空间，二来可以避免因为pop函数导致将树的节点也释放了；同时我们需要将我们以前实现过的Queue.h以及Queue.c放入我们本次项目的文件目录中，然后执行如下操作
将Queue.h以及Queue.c添加进来，就可以利用了，同时需要将Queue.h中的int类型改为指向树的节点的指针。
代码展示：
void LevelOrder(Btnode* root) { Que q; QueInit(&q); if (root != NULL) Quepush(&q,root);//把树的根节点放进队列 while (!QueEmpty(&q)) { Btnode* front = Quefront(&q);//取队头元素，为了后面进行访问左右节点 Quepop(&q); printf("%d ", front->data); if (front->left) Quepush(&q, front->left); if (front->right) Quepush(&q, front->right); } QueDestroy(&q); }1.2 判断是否为完全二叉树
关于这个问题的一些误区：对于满二叉树，我们可以直到确切的数量关系，但是对于完全二叉树，我们只能得到一个大概的范围，所以没办法通过节点的数量来判断，因为一个相同的节点，可以有很多种不同的形态。
对于证明题，最直白的方法就是通过定义来证明。
对于上面的完全二叉树来说，如果进行层序遍历，不论根节点的左右子树是否为空，都存进队列中，那在最后一个叶子节点之后应该是全为空的，否则不是完全二叉树，根据上述的说明，我们可以写出一下代码来进行判断：
bool BinaryTreeComplete(Btnode* root) { Que q; QueInit(&q); if (root) Quepush(&q,root); while (!QueEmpty(&q)) { Btnode* front = Quefront(&q); Quepop(&q); if (front == NULL) { break; } Quepush(&q, front->left);//空节点也进队 Quepush(&q, front->right); } while (!QueEmpty(&q)) { Btnode* front = Quefront(&q); Quepop(&q); if (front != NULL) { QueDestroy(&q); return false; } } QueDestroy(&q); return true; }2.二叉树的创建与销毁
2.1 二叉树的创建
给出一段字符串的内容，通过前序遍历创建对应的二叉树：
#include <stdio.h> #include<stdlib.h> typedef struct BinaryTreenode { char data; struct BinaryTreenode* left; struct BinaryTreenode* right; }Btnode; Btnode* CreatTree(char* s, int* pi) { if (s[*pi] == '#' || s[*pi] == '\0') { (*pi)++; return NULL; } //abc##de#g##f### Btnode* root = (Btnode*)malloc(sizeof(Btnode)); root->data = s[(*pi)++]; root->left = CreatTree(s, pi); root->right = CreatTree(s, pi); return root; } int main() { char s[100]; scanf("%s", s); //先通过先序遍历的数据进行建树 int i = 0; Btnode* root = CreatTree(s, &i); return 0; }这里在记录数组下标时，应该调用指针进行解引用，因为如果是值传递的，在函数递归返回时，i没办法作有效的更改，不同栈帧中的i不会进行相互传递，所以应当用址传递。
2.2 二叉树的销毁
如我们常用的销毁思想一致，就是释放所有节点的空间，那么我们就需要对所有节点进行遍历，这就是我们要思考的，二叉树可用的遍历方法那么多，我们应该使用哪一种？还是说每一种都可以？
我们稍加思考就可以想到，左右子树需要根节点才可以进行调用，那如果我们先将根节点的空间进行释放，我们是不是就没办法释放左右子树，所以根节点应该在最后释放，那么我们需要采用的遍历方法就是后续遍历了，知道了大概思路后，写出代码就变得尤为简单了。
void DestroyTree(Btnode* root) { if (root == NULL) return; DestroyTree(root->left); DestroyTree(root->right); free(root); root = NULL; }但是需要在函数外部对node进行置空，防止成为野指针，也可以使用二级指针置空。
3. 知识内容补充
1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.
2. 若规定根结点的层数为1，则深度为h的二叉树的最大结点数是2^h-1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n2＝ n0＋1
假设二叉树有N个结点* 从总结点数角度考虑：N = n0 + n1 + n2 ①** 从边的角度考虑，N个结点的任意二叉树，总共有N-1条边* 因为二叉树中每个结点都有双亲，根结点没有双亲，每个节点向上与其双亲之间存在一条边* 因此N个结点的二叉树总共有N-1条边** 因为度为0的结点没有孩子，故度为0的结点不产生边; 度为1的结点只有一个孩子，故每个度为1的结点* * 产生一条边; 度为2的结点有2个孩子，故每个度为2的结点产生两条边，所以总边数为：n1+2*n2* 故从边的角度考虑：N-1 = n1 + 2*n2 ②* 结合① 和 ②得：n0 + n1 + n2 = n1 + 2*n2 - 1* 即：n0 = n2 + 1
结语
下篇文章将作一些关于链式二叉树的OJ题讲解，感谢观看。
