当前位置：首页 > article >正文

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

article 2025/2/5 16:32:39

文章目录

一：实现链式结构二叉树
- 1.1前中后序遍历
- - 1.1.1遍历规则
  - 1.1.2代码实现
- 1.2结点个数以及高度等
- - 1.2.1二叉树结点个数
  - 1.2.2二叉树叶子结点个数
  - 1.2.3二叉树第k层结点个数
  - 1.2.4二叉树的深度/高度
  - 1.2.5 二叉树查找值为x的结点
  - 1.2.6二叉树的销毁
- 1.3层序遍历
- 1.4判断是否为完全二叉树
二：结语

欢迎大家阅读我的博客，给生活加点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：如果也把空孩子加入，就会退出循环。