二叉树03（数据结构初阶）

欢迎大家阅读我的博客，给生活加点impetus,！！

今天我们学习二叉树的实现，感受递归的魅力！！

一：实现链式结构二叉树

⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。

我们先来定义链式结构二叉树的结构。

链式结构二叉树是由结点组成的，定义二叉树的结构就是定义结点的结构。

在数据结构初阶的学习过程中中，前期对于二叉树的插入代码不会深入研究，在后期c++阶段学习红黑树，平衡树等会对二叉树数据的插入操作进行研究。

我们需要了解二叉树的遍历方式有哪些

1.1前中后序遍历

为了后方我们能够理解深刻，我们先依据下列图示来手动创建一个二叉树

这里我们的存储类型为char类型，因为存储的是字符。
创建结点：

构造链式二叉树：

接下来我们来深入讲解各种遍历方法的规则。

1.1.1遍历规则

按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：
1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前
访问顺序为：根结点、左⼦树、右⼦树
2）中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）
访问顺序为：左⼦树、根结点、右⼦树
3）后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后
访问顺序为：左⼦树、右⼦树、根结点

接下来依靠规则自行先思考上述二叉树的遍历顺序，先来说明结果

前序遍历：首先从根结点进入，依照前序遍历规则–根左右首先A结点是根结点，可以直接打印，左方为B结点，B同样也是根结点，所以打印B后会继续向下遍历，直到找到不为根结点的结点，其实就是叶子结点NULL，右的话就是D结点右子树NULL，此时B结点的整个左子树遍历完全，同样方法遍历右子树，直至A结点的左子树全部遍历完毕。同理遍历右子树。

顺序为A B D NULL NULL NULL C E NULL NULL F NULL NULL

中序遍历：首先从根结点进入，依照前序遍历规则–左根右首先A结点是根结点，不能打印，会继续向左遍历，直至找到不为任何子树的结点（度为0的结点，即叶子结点），先打印D的左子树，再打印D，最后打印D的右子树，随后B的整个左子树打印完毕，打印B后，再打印B的右子树，随后A的整个左子树打印完毕打印A后，随后打印A的右子树，同理。

顺序为NULL D NULL B NULL A NULL E NULL C NULL F NULL

后序遍历：首先从根结点进入，依照前序遍历规则–左右根首先A结点是根结点，不能打印，会继续向左遍历，直至找到不为任何子树的结点（度为0的结点，即叶子结点），先打印D的左子树，再打印D的右子树，再打印D，随后B的整个左子树打印完毕，打印B的右子树NULL，随后打印B，A的整个左子树打印完毕，同理打印A的右子树。

打印顺序：NULL NULL D NULL B NULL NULL E NULL NULL F C A

所以遍历时我们需要注意：

1：除叶子结点以外，其他结点都是根结点，当层次很多时，1到h-1层都是层次>=2的树或子树。
2：遍历时主要是涉及递归函数

1.1.2代码实现

前序遍历：

中序遍历：

后序遍历：

图解（前序遍历）：

细节：
1：遍历只能从根结点开始遍历，且一定要根据口诀的顺序
2：遍历都是先经过包含叶子结点的二叉树
3：叶子结点其实是递归的结束条件
4：递推回归时与函数栈帧创建的联系
5：遍历时某结点看做根结点，该棵树一定要延伸到叶子结点，才能看做一棵树。

1.2结点个数以及高度等

1.2.1二叉树结点个数

大部分人想到的都是设置计数器，那我们来看看这个算法的好坏。

方法一：

所以这个地方我们需要传地址，而且，size既不能做全局变量，也不能做局部变量。那我们索性添加一个参数。

来看下面这段代码：

方法二：直接来返回int
思路：结点个数=根结点（1）+左子树结点+右子树结点

我们来画图演示一下：

逐步递推，逐步回归、
方法二同样能够实现预期结果，并且思路更加简单。

总结：
1：函数栈帧销毁：函数执行完全或者return提前返回
:2：局部变量+static生命周期延长，仍然存在作用域，上例修饰size时仍然错误

1.2.2二叉树叶子结点个数

思路**：左子树叶子结点个数+右子树叶子结点个数**

1.2.3二叉树第k层结点个数

思路：深度优先遍历，k自减，准确找到第k层，最后返回个数

1.2.4二叉树的深度/高度

思路：根结点+max{左子树，右子树}

最好使用变量接收一下，因为我们需要比较大小

1.2.5 二叉树查找值为x的结点

思路：查找左子树与右子树，同时该结点是否为X

1.2.6二叉树的销毁

思路：只能后序遍历，因为每一个结点malloc都要释放，如果先释放根结点，孩子结点就找不到了。

注意：优先级高低:->大于*。
free之后及时置空，防止成为野指针。

1.3层序遍历

前方的所有遍历都是涉及前中后序遍历，都是深度优先遍历。
下面我们来讲解广度优先遍历(层序遍历)，我们来看这样一个题目：

如果我们仍然按照深度优先来遍历的话，肯定是不行的，因为只有当该部分函数栈帧销毁之后，才会继续进入到上一个函数栈帧。

思路：借助数据结构–队列，根结点入队列，循环判断队列是否为空
不为空取队头出队头，将队头的左右且不为空的孩子入队列。

我们来画图演示一下：

再来看一张：

下面是代码部分：

细节
1：我们涉及到了Queue，我们需要重新添加Queue.c和Queue.h文件。
2：队列中存储的是二叉树结点指针类型，需要将Queue中定义的int改为struct BTNode。
3：typedef重定义的是数据类型，一定要加struct加以声明，只写BTNode会报错。
4：存储指针是因为结构体访问成员是指针类型（左孩子，右孩子），如果直接存储结构体会报错。
5：如果也把空孩子加入，就会退出循环。

1.4判断是否为完全二叉树

性质：
1：除最后一层外，其余结点的度都为2
2：有序

我们需要使用层序遍历

思路：层序遍历，根结点入队列，循环判断队列是否为空不为空取队头出队头，将队头的左右孩子入队列，不管是不是空遇到空停止循环，比较队列剩余元素，如果还有非空元素，则为非完全二叉树，反之是完全二叉树。

我们来画图理解观察区别，层序遍历部分我将不再演示：

接下来来看代码：

细节：
1：层序遍历入得都是top(队头)的左右孩子，如果写成root->left，这将面临死循环。
:2：这里的队列并不是依次相连的，中间有很多断开的，而最开始的Queue结点是一个一个依次相连的

二：结语

最后，感谢大家的阅读，欢迎大家有更多的思路与我交流，同时不足之处欢迎指正！！
逆水行舟–不进则退！！！加油，希望早日看见最好的自己！！