当前课程知识点：数据结构 > 第6章 树和二叉树 > 6.7 树的转换和遍历 > 6.7 树的转换和遍历
同学们大家好
我是云南大学信息学院教师孔兵
这节课我们讨论树的转化与遍历
为了讨论森林的存储，需要介绍森林和二叉树的转换
我们从树出发来讨论这个问题
给定一棵树，可以找到唯一一棵二叉树与之对应
前面介绍了孩子兄弟表示法
图1是一棵树，如果按照孩子兄弟表示法实现它的存储结构
形态如图2所示。图3是一棵二叉树
如果我们按照二叉链表实现它的存储的话
它的存储的形态也是图2这个样子
对图1的树和图3的二叉树来说
实现它们存储的二叉链表形态是一样的
我们就说，图1这棵树和图3的二叉树是对应的
这里之所以我们要讨论这个问题
是因为后面讨论树和森林遍历的时候
二者之间会有联系
森林和二叉树也可以建立这样的对应关系
森林包括多棵树，如果在森林中
把每棵树的根结点看作是兄弟的话
同样可以采用孩子兄弟表示法的方式
实现森林的存储，那么根据刚才的讨论
这样存储以后，森林也和一棵二叉树是对应的
图1是三棵树组成的森林
图2是森林对应的二叉树的形式
具体的转换就不多说了，把森林的根结点看成兄弟
按孩子兄弟表示法的方法就可以了
我们可以说，森林的存储也可以通过二叉链表来实现
解决了森林存储的问题
在对树和森林的处理当中
最重要的操作也是遍历操作
先讨论树的遍历
针对树的遍历问题
我们仍然是进行递归分解，把遍历树的原问题
分解为这样的子问题，访问根，遍历根的每棵自身
根据访问根的时机不同
具体的遍历策略分为两种
先序策略，先访问根
再依次遍历根的每棵子树
后序策略，先依次遍历根的每棵子树
最后访问根。不同的访问策略，其访问结点的次序是不同的
下面以图1的树为例
观察两种策略的访问序列
先序遍历，按照先序策略
第1个访问结点是整个树的根A
随后递归遍历它的三棵子树
先遍历第1棵以B为根的子树
访问B，B没有孩子，对B子树的遍历也就结束了
返回A层。随后遍历A的第2棵子树C，先访问C
随后遍历C的每棵子树，递归遍历D为根的子树
访问D，D没有子树，返回C层，C没有其它子树
返回A层。随后访问A的第3棵子树E，访问E
E没有子树，返回A层。A没有其它子树了
返回，对树的遍历结束，获得访问序列ABCDE
再看一下后序遍历
按照后序遍历的策略，先遍历根的每棵子树
最后访问根
首先递归遍历B为根的这棵树
B没有子树，访问B，返回A层
随后递归遍历C为根的子树，在C为根的这棵子树中
同样先递归遍历C的每个子树
递归遍历以D为根的这棵子树，D没有子树
访问D，返回C层，C没有其它子树，访问C
返回A层。随后递归遍历A的第3棵子树
以E为根的这棵树，E没有子树，访问E
返回A层。到此，A的所有子树都已经遍历
随后访问A，完成对整棵树的遍历
获得访问序列：BDCEA
那么，怎么编程实现树的先序和后序遍历呢？
前面讨论过，利用孩子兄弟表示法
可以把树存储成二叉链表的形态
图2是图1所对应的二叉树
如果对图2这棵二叉树进行先序遍历的话
可以得到ABCDE，同学们应该注意到了
这个访问序列和图1这棵树的先序序列是完全相同的
如果我们对图2的二叉树中做中序遍历
可以得到访问序列BDCEA
这个序列和图1树的后序序列是一样的
这给了我们一个启示，如果树采用孩子兄弟表示法存储的时候
可以通过移植二叉树的遍历算法实现树的先序和后序遍历
具体来看，就是移植二叉树的先序遍历算法来实现树的先序遍历
只需要把树的先序遍历算法中
涉及指针lchild的地方替换为firstchild
涉及指针rchild的地方替换为nextsibling
其它基本不变
同理，用类似的办法
可以移植二叉树的中序遍历算法来实现树的后序遍历
同学们课后思考一下具体怎么做
下面我们看一下森林的遍历
森林中包含多棵树，森林的遍历策略
是在树的遍历策略上拓展的
森林有两种遍历策略
先序遍历
首先访问第1棵树的根
随后递归遍历第1棵树中，根的子树森林
第一课树遍历完成后，先序遍历其余树组成的森林
从先序策略的描述上可以看出，森林的先序策略
实际上是按树的先序策略，从第1棵树开始
依次遍历森林中的每棵树
森林的中序策略，森林的中序遍历，首先递归遍历第一棵树中根的子树森林
接着访问第一棵树的根，随后中序遍历其余树组成的森林
参考先序，可以看出，森林的中序策略
实际上是按树的后序策略，从第1棵树开始
依次遍历森林中的每棵树
前面讨论过，森林同样可以用孩子兄弟表示法
存储为二叉链表的形态，同样可以和二叉树对应
图中是三棵树的森林以及它对应的二叉树
例子中给出了森林的先序和中序访问序列
同学们可以自己下去验证一下
对应二叉树的先序和中序序列是否和它们相同
森林遍历的实现
我们同样可以通过移植二叉树的先序和中序算法来完成
好同学们，这节课我们就讲到这儿
下次课再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结
