引入
上一节,我们详细说明了二叉树的 4 种遍历方式,根据根的位置不同,我们分为前序遍历、中序遍历和后序遍历以及最常用的层序遍历。今天我们就来实战一下, 看看如何建立一棵树,并且按照我们需要的方式遍历树上的结点。
需求
- 根据输入建立一棵二叉树
- 输出其前序遍历、中序遍历和后序遍历结果
代码分析
首先要构建一棵树,因为是二叉树,所以结构体中包含左右两棵子树
- 存放数据的
data
- 存放左右子树的
指针域
1 |
|
接着,我们开始创建树,我们使用的是返回树根节点地址的方式
- 先创建一个临时结点
- 在创建一个临时 char 变量,用于存放用户输入的内容
- scanf 让用户输入内容,将值赋值给 char 变量
- 如果输入的是#号,则表示结点为空
- 如果不为空,则将这个结点看成根,将输入的值赋予根结点
- 接着将这个根的左右子树通过递归获取到
- 将所有的叶子结点都输入为#后,即所有结点都是 NULL ,没有左右子树,树创建完成。
1 |
|
树的遍历,我们使用递归的思路,其实很好遍历
- 前序遍历是,根在前面,所以是中左右,所以先输出 data,再递归左右子树
- 中序遍历是,根在中间,所以是左中右,所以先递归左子树,再输出 data,再递归右子树
- 后序遍历是,根在后面,所以是左右中,所以先递归左右子树,再输出 data。
- 我们判断条件也非常简单,只要结点不为 NULL,就执行!
1 | void PreVisitTree(struct BiTNode *Temptree){ |
主调 Main 函数
- 首先创建一个树指针,用于存放生成好的树。
- 然后使用前序、中序、后续遍历的函数,分别调用这棵树。
- 输出的结果就是这棵树的前序、中序、后续遍历了。
1 | int main(){ |
完整代码
1 |
|
输出结果
请输入前序结点:
ABDH##I##E#J##CF#K##G##
ABDHIEJCFKG
HDIBEJAFKCG
HIDJEBKFGCA
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。