6.4.2森林与二叉树的转化

数据结构第六章第六章树和二叉树6.1 6.1 树的定义和基本术语树的定义5/1066.1 树的定义和基本术语树的表示AAB C D E FGHIJK L 6.1 树的定义-其他表示树的其他表示7/106结点的度结点的层次终端结点(叶子)非终端结点(分支结点)内部结点6.1 树的定义-基本术语基本术语A B C D EFG HIJK L孩子 双亲 兄弟 祖先 子孙 堂兄弟8/1069/10610/10611/106 6.1 树的定义-ADT TreeADT Tree13/1066.2 二叉树二叉树的定义二叉树有序树6.2 二叉树-性质(1)二叉树的性质6.2 二叉树-性质(2)对任一结点，若其右分支下的子孙的最大层次为。

6.2 二叉树-性质(3)6.2 二叉树-性质(4)6.2 二叉树-顺序存储结构(1)二叉树的顺序存储结构19/1066.2 二叉树-顺序存储结构(2)空间利用率问题：在最坏情况下，一个深度为支树(树中不存在度为2的结点一维数组。

12345676.2 二叉树-链式存储结构二叉树的链式存储结构6.3 遍历二叉树和线索二叉树6.3 -遍历二叉树(1)遍历二叉树4 6 75 2 3 1 (LRD)12345676.3 -遍历二叉树(2)6.3 -遍历二叉树(3)6.3 -遍历二叉树(4) 6.3 -基于先/中/后序遍历算法的应用27/106Status CreateBiTree(BiTree//按先序次序输入二叉树中结点的值(一个字符)//空格字符表示空树,构造二叉链表表示的二叉树T scanf(&ch);【本例特征】如何通过全局变量、变参、返回值三种渠道返回处理结果？【思路】【算法1// n为叶子结点的计数器 int n=0;void leaf(BiTree【算法2// 函数值为T的叶子结点数 int leaf(BiTree T)【算法3// 引用参数n为T的叶子结点数，方法一 void leaf(BiTree T, int&n)【算法3// 引用参数n等同于全局变量，方法二// 把T所指向的二叉树中的叶子结点数累加到n为什么强调使用函数调用的结果？(1)为什么强调使用函数调用的结果？(2)为什么强调使用函数调用的结果？(3)为什么强调使用函数调用的结果？(4)为什么强调使用函数调用的结果？(5)例3 教材P131 算法6.4【思路】·二叉树为空时，不必释放；·若T不为空，则先释放其左右子树的所有结点的空间，再释放根结点的空间【本例特征】如何选择二叉树的先序、中序、后序遍历来解决问题，它们对问题求解有何影响？【算法1void deleteXTree(BiTree&T, ElemType x) {【算法2void deleteXTree(BiTree&T, ElemType x) {【算法3 void deleteXTree(BiTree &T, ElemType x) {【本例特征】如何处理多个返回结果？【思路】待查结点的存在性：【算法】Status PreorderKnode(BiTree // 输入：T 为二叉链表示的二叉树，k 为待查找的结点在先序序列中的位序// 输出：TRUE ：待查找的结点存在；FALSE ：待查找的结点不存在// e—当待查结点存在时，该结点的值通过 6.3 –先序遍历的非递归算法(1)47/1066.3 –先序遍历的非递归算法(2)48/1066.3 –先序遍历的非递归算法(3)6.3 –中序遍历的非递归算法 6.3 –后序遍历的非递归算法(1)51/1066.3 –后序遍历的非递归算法(2) 6.3 –层次遍历算法及其应用【思路】先访问的结点，其孩子结点必然也先访问。

2020年清华-伯克利深圳学院962数学-数据方向基础综合考试大纲——盛世清北本文由盛世清北查阅整理，专注清华大学考研信息，为备考清华大学考研学子服务。

以下为2020年清华大学深圳国际研究生院962 《数学-数据方向基础综合》考研考试大纲：962 《数学-数据方向基础综合》考试内容：1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间需求2 线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加3栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.2.1数制转换3.2.2括号匹配的检验3.2.3行编辑程序3.2.4迷宫求解3.2.5表达式求值3.3栈与递归的实现3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.4.3循环队列——队列的顺序表示和实现3.5离散事件模拟4 串4.1串类型的定义4.2串的表示和实现4.2.1定长顺序存储表示4.2.2堆分配存储表示4.2.3串的块链存储表示4.3串的模式匹配算法4.3.1求子串位置的定位函数Index（S，T，pos）4.3.2模式匹配的一种改进算法4.4串操作应用举例4.4.1文本编辑4.4.2建立词索引表5 数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义5.5广义表的存储结构5.6m元多项式的表示5.7广义表的递归算法5.7.1求广义表的深度5.7.2复制广义表5.7.3建立广义表的存储结构6 树和二叉树6.1树的定义和基本术语6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.4.3树和森林的遍历6.5树与等价问题6.6赫夫曼树及其应用6.6.1最优二叉树（赫夫曼树）6.6.2赫夫曼编码6.7回溯法与树的遍历6.8树的计数7 图7.1图的定义和术语7.2图的存储结构7.2.1数组表示法7.2.2邻接表7.2.3十字链表7.2.4邻接多重表7.3图的遍历7.3.1深度优先搜索7.3.2广度优先搜索7.4图的连通性问题7.4.1无向图的连通分量和生成树7.4.2有向图的强连通分量7.4.3最小生成树7.4.4关节点和重连通分量7.5有向无环图及其应用7.5.1拓扑排序7.5.2关键路径7.6最短路径7.6.1从某个源点到其余各顶点的最短路径7.6.2每一对顶点之间的最短路径8 动态存储管理8.1概述8.2可利用空间表及分配方法8.3边界标识法8.3.1可利用空间表的结构8.3.2分配算法8.3.3回收算法8.4伙伴系统8.4.1可利用空间表的结构8.4.2分配算法8.4.3回收算法8.5无用单元收集8.6存储紧缩9 查找9.1静态查找表9.1.1顺序表的查找9.1.2有序表的查找9.1.3静态树表的查找9.1.4索引顺序表的查找9.2动态查找表9.2.1二叉排序树和平衡二叉树9.2.2B树和B+树9.2.3键树9.3哈希表9.3.1什么是哈希表9.3.2哈希函数的构造方法9.3.3处理冲突的方法9.3.4哈希表的查找及其分析10 内部排序10.1概述10.2插入排序10.2.1直接插入排序10.2.2其他插入排序10.2.3希尔排序10.3快速排序10.4选择排序10.4.1简单选择排序10.4.2树形选择排序10.4.3堆排序10.5归并排序10.6基数排序10.6.1多关键字的排序10.6.2链式基数排序10.7各种内部排序方法的比较讨论11 外部排序11.1外存信息的存取11.2外部排序的方法11.3多路平衡归并的实现11.4置换一选择排序11.5最佳归并树12 文件12.1有关文件的基本概念12.2顺序文件12.3索引文件12.4ISAM文件和VSAM文件12.4.1ISAM文件12.4.2VSAM文件12.5直接存取文件（散列文件）12.6多关键字文件12.6.1多重表文件12.6.2倒排文件备考清华，需要完整的资料，需要坚定的信念，更需要完善的复习策略，把书本从薄读到厚，再从厚读到薄，最后通过目录，就能就能把所有知识脉络延展，相互关联起来，检查是否有知识盲区，这中间是一个艰难的过程，需要有足够的耐力和毅力，一路有盛世清北陪伴你，你的备考不会孤单！。

二叉树,树,森林遍历之间的对应关系一、引言在计算机科学中，数据结构是非常重要的知识点之一。

而树这一数据结构，作为基础的数据结构之一，在软件开发中有着广泛的应用。

本文将重点探讨二叉树、树和森林遍历之间的对应关系，帮助读者更加全面地理解这些概念。

二、二叉树1. 二叉树的定义二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以为空，也可以是一棵空树。

2. 二叉树的遍历在二叉树中，有三种常见的遍历方式，分别是前序遍历、中序遍历和后序遍历。

在前序遍历中，节点的访问顺序是根节点、左子树、右子树；在中序遍历中，节点的访问顺序是左子树、根节点、右子树；在后序遍历中，节点的访问顺序是左子树、右子树、根节点。

3. 二叉树的应用二叉树在计算机科学领域有着广泛的应用，例如用于构建文件系统、在数据库中存储有序数据、实现算法中的搜索和排序等。

掌握二叉树的遍历方式对于理解这些应用场景非常重要。

三、树1. 树的定义树是一种抽象数据类型，由n(n>0)个节点组成一个具有层次关系的集合。

树的特点是每个节点都有零个或多个子节点，而这些子节点又构成了一颗子树。

树中最顶层的节点称为根节点。

2. 树的遍历树的遍历方式有先根遍历、后根遍历和层次遍历。

在先根遍历中，节点的访问顺序是根节点、子树1、子树2...；在后根遍历中，节点的访问顺序是子树1、子树2...，根节点；在层次遍历中，节点的访问顺序是从上到下、从左到右依次访问每个节点。

3. 树的应用树广泛用于分层数据的表示和操作，例如在计算机网络中的路由算法、在操作系统中的文件系统、在程序设计中的树形结构等。

树的遍历方式对于处理这些应用来说至关重要。

四、森林1. 森林的定义森林是n(n>=0)棵互不相交的树的集合。

每棵树都是一颗独立的树，不存在交集。

2. 森林的遍历森林的遍历方式是树的遍历方式的超集，对森林进行遍历就是对每棵树进行遍历的集合。

3. 森林的应用森林在实际编程中经常用于解决多个独立树结构的问题，例如在数据库中对多个表进行操作、在图像处理中对多个图形进行处理等。

ElemType data ; struct CSnode *firstchild, *nextsibing ; }CSNode;
6.4.1 树的存储结构
R AB C D EG F
R⋀
A
⋀D
⋀B
⋀E ⋀
C⋀
⋀G
⋀F ⋀
6.4.2 树、森林和二叉树的转换
1. 树转换为二叉树 将树转换成二叉树在“孩子兄弟表示法”中已 给出，其详细步骤是： ⑴ 加线。在树的所有相邻兄弟结点之间加一 条连线。 ⑵ 去连线。除最左的第一个子结点外，父结点 与所有其它子结点的连线都去掉。 ⑶ 旋转。将树以根结点为轴心，顺时针旋转 450，使之层次分明。
B C
D
A E
L HK
M
技巧：无左孩子 者即为叶子结点
6.4.3 树和森林的遍历
1. 树的遍历 由树结构的定义可知，树的遍历有二种方法。 ⑴ 先序遍历：先访问根结点，然后依次先序 遍历完每棵子树等。价于对应二叉树的先序遍历
⑵ 后序遍历：先依次后序遍历完每棵子树，然 后访问根结点。等价于对应二叉树的中序遍历
0 R -1 1A 0 2B 0 3C 0
}Ptree ; R
4D 1 5E 1
AB C
6F 3
7G 6
DE
F
8H 6
9I 6
G H I 10~MAX_Size-1 ... ...
6.4.1 树的存储结构
2. 孩子表示法
每个结点的孩子结点构成一个单链表，即有n 个结点就有n个孩子链表；
n个孩子的数据和n个孩子链表的头指针组成一 个顺序表； 结点结构定义： 顺序表定义：
typedef struct PTNode { ElemType data ;

有以下两种遍历方法：
先根遍历 后根遍历
注意：先根和后根遍历算法都是递归的。
先根遍历: 若树不空，则先访问根结点，然后依次先根遍历各 棵子树。
后根遍历: 若树不空，则先依次后根遍历各棵子树，然后访问 根结点。
【示例-5】 遍历下图所示的树。
A
B
C
D
EF
G
H
IJ K
先根遍历的顶点访问次序： A B E F C D G H I JK
一棵二叉树的根结点作为前一棵二叉树根结点的右 孩 子结点，当所有二叉树连在一起后，此时所得到 的二 叉树就是由森林转换得到的二叉树。
【示例-2】 将下图所示的森林转换成二叉树。
G
A
C
H
I
B DEF
J
K
A
B
C
A
C
B
D
E
F
G H
J
I
K
D E
G H
FJ
I
K
6.4.3 二叉树还原为树/森林
当一棵二叉树是由一棵树转换而来的，则该二叉树还 原为树的过程如下：
A
A
BC D
EF
G
一棵树 A
B
E
C
F
D
G
பைடு நூலகம்
相邻兄弟之间 加连线(虚线)
BC D
EF
G
删除与双亲 结点的连线
转换后的二叉树
A BC D
EF
G
当要转换为二叉树的森林由两棵或以上树构成时，将 这样的森林转换为二叉树的过程如下：
➢ 将森林中的每棵树转换成相应的二叉树。 ➢ 第一棵二叉树不动，从第二棵二叉树开始，依次把后

森林转换成二叉树的方法
森林转换成二叉树的方法是一种将多棵树合并成一棵二叉树的
算法。

这种方法可以方便地对树进行遍历和搜索，同时也可以减少树的存储空间。

该方法的核心思想是将森林中每个节点的左子树指向其在同一树中的前一个兄弟节点，右子树指向其在同一树中的后一个兄弟节点。

这样，整个森林就可以转换成一棵二叉树。

具体实现时，可以遍历每个节点，如果该节点不是该树的根节点，则将该节点的父节点作为其前一个兄弟节点，将该节点的下一个兄弟节点作为其后一个兄弟节点，然后将该节点的左子树指向其前一个兄弟节点，右子树指向其后一个兄弟节点。

如果该节点是根节点，则将其左子树和右子树都赋值为NULL。

通过这种方法，可以将多棵树合并成一棵二叉树，并且保证二叉树的结构和原来的树相同。

在实际应用中，这种方法可以用于对树进行遍历和搜索，也可以用于减少树的存储空间，提高程序的效率。

- 1 -。

链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）
结点。
下图为树的孩子兄弟表示结构。
A
1∧
2
B
C
∧4
3∧
DE F G
∧5
∧7 ∧
∧6 ∧
树的孩子兄弟表示法
孩子兄弟表示法的类型定义如下：
typedef struct CSNode
{
DataType data;
/*结点信息*/
Struct CSNode *FirstChild;
/*第一个孩子*/
Struct CSNode *Nextsibling; /*下一个兄弟*/
} CSNode, *CSTree;
这种存储结构便于实现树的各种操作，例如，如果要访问结点 x 的第 i 个孩子，则只要先从
FirstChild 域找到第一个孩子结点，然后沿着这个孩子结点的 Nextsibling 域连续走 i-1
A
A
B
C
DB
C
D
EF
G
EF
G
A B
E
C
FD
H
H
H
G
树到二叉树的转换
通过转换过程可以看出，树中的任意一个结点都对应于二叉树中的一个结点。树中某结 点的第一个孩子在二叉树中是相应结点的左孩子，树中某结点的右兄弟结点在二叉树中是相 应结点的右孩子。也就是说，在二叉树中，左分支上的各结点在原来的树中是父子关系，而 右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉 树的根结点的右孩子必然为空。
（2）中序遍历
若森林非空，则遍历方法为：
①中序遍历森林中第一棵树的根结点的子树森林。

§6.4 树和森林 ❖树的存储结构——孩子兄弟表示法
这种存储结构便于实现各种树的操作。首先易于 实现找结点孩子等的操作。如果为每个结点增设一个 (parent)域，则同样能方便地实现Parent(T, x)操作。
§6.4 树和森林
❖森林和二叉树的转换
1. 树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存储结构，
R AB C
DE
F
GHK
R^
A
^D
^B
^E ^
C^
F^
^G
^H
^K ^
§6.4 树和森林
❖树的二叉链表（孩子 - 兄弟）存储表示
typedef struct CSNode { Elem data; struct CSNode *firstchild , *nextsibling;
} CSNode, *CSTree;
A BC D E F GH
A BC D
E F GH A
BC D
1）在兄弟之间加一条连线； 2）对每个结点，除了左孩子外，去除其与其余孩子之间的联系； 3）以根结点为轴心，将整个树顺时针转45°。
Ia
A B
Ib
E F
d
C D
G H I
c E F G H I
§6.4 树和森林
❖森林和二叉树的转换
2. 森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一棵
§6.4 树和森林
3
6^
5^
0
1
7
8
2^ 9^
R AB C
DE
F
GHK
§6.4 树和森林 ❖树的存储结构——孩子兄弟表示法
或称二叉树表示法，或称二叉链表表示法。即以 二叉链表作树的存储结构。链表中结点的两个链域分 别指向该结点的第一个孩子结点和下一个兄弟结点。

森林转换成二叉树例题森林转换成二叉树是一种常见的树结构转换问题。

森林是由多个树组成的集合，而二叉树是一种每个节点最多有两个子节点的树结构。

下面我将从多个角度全面回答这个问题。

首先，让我们明确森林和二叉树的定义。

森林是由多个树组成的集合，每棵树由根节点和若干子树组成。

而二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

将森林转换成二叉树的一种常见方法是将森林中的每棵树都转换成二叉树，然后将这些二叉树连接起来。

具体的转换过程如下：1. 对于森林中的每棵树，选择一个节点作为二叉树的根节点。

2. 对于每个节点，将其第一个子节点作为其左子节点，将其后续的子节点作为其右子节点。

3. 对于每个节点的子节点，按照它们在森林中的顺序进行连接。

这样，通过对每棵树进行上述转换，最终得到的二叉树就是森林转换后的结果。

举个例子来说明。

假设有一个森林，其中包含三棵树。

第一棵树的根节点为A，子节点为B和C；第二棵树的根节点为D，子节点为E和F；第三棵树的根节点为G，子节点为H和I。

按照上述转换方法，我们首先选择第一棵树的根节点A作为二叉树的根节点，将B作为A的左子节点，将C作为A的右子节点。

然后选择第二棵树的根节点D作为新的二叉树的根节点，将E作为D的左子节点，将F作为D的右子节点。

最后选择第三棵树的根节点G作为新的二叉树的根节点，将H作为G的左子节点，将I作为G的右子节点。

将上述三棵二叉树连接起来，得到的最终二叉树如下：A D G./ \ / \ / \。

B C E F H I.通过这个例子，我们可以看到，将森林转换成二叉树的过程是将每棵树转换成二叉树，然后将它们连接起来。

这样可以保持每个节点最多有两个子节点的特性。

总结起来，森林转换成二叉树的过程是将森林中的每棵树转换成二叉树，然后将它们连接起来。

这种转换方法可以保持树的结构特性，并且可以方便地对二叉树进行遍历和其他操作。

希望以上回答能够满足你的需求。

}
}
第3页/共20页
4. 二叉树的层次遍历
二叉树的层次遍历:即按照“从上到下，从左至右”的次序访问所有结点 一次且仅一次。对一棵非空的二叉树，先访问根结点，再依次访问左孩子、 右孩子，并记录该层结点的访问次序；依次访问各结点的左孩子和右孩子， 直到访问到最右端的叶子结点。
层次遍历存在容易理解的非递归算法。这里有一个“依序访问下层结点” 的问题，为了记录上一层结点的访问次序，需要使用队列。算法描述如下：
19
第19页/共20页
• 4.画出以下森林对应的二叉树
A
B
C
D
E
F
G
H
A
B
C
D
E FG
H
2020/6/11
20
第20页/共20页
• 要求输入时表示出叶子结点。 • 如图所示：
• 输入序列为： • ABD#GL###E##CFH##K### • 其中的 # 表示空
A
B
C
D
EF
G
H
K
L
第6页/共20页
算法6.4 按扩展先序序列建立二叉树的算法
• typedef char elemtype ;
/* 结点数据为char型 */
• bitree creatbit()
/* 遍历左子树（递归调用） */
preorder(root->rchild);
/* 遍历右子树（递归调用） */
}
}
第1页/共20页
中序遍历二叉树的递归算法
void Inorder(bitree root)
/* root为根结点，visit()为访问结点的函数 */
{ if ( root !=0)

树和森林的存储结构
4.树的孩子兄弟表示法
又称二叉树表示法或二叉链表表示法。即以二叉链 表作为树的存储结构，链表中的两个链域 firstchild和nextsibling分别指向此结点的第一个 孩子结点和下一个兄弟结点。
结点结构描述如下：
typedef struct CSNode{ DataType data; struct CSNode *firstchild, *nextsibling;
} CSNode;
过程: (1) 加线,(2) 抹线, (3) 旋转
A
BC
D
E FGH
KL M N
∧B E
A∧
C ∧D∧
∧K
∧F
∧L∧
∧G
∧M
H∧
∧N∧
树和森林的基本操作
1. 树及森林和二叉树的相互转换
由于二叉树和树都可以用二叉链表做存储结 构，因此，利用二叉链表作为媒介可导出树和 二叉树的一个对应关系。也就是说，对一棵树， 可找到一棵二叉树与之对应，从物理存储方式 来看，存储方式是完全一样二叉树的相互转换
树二叉树
加线：将兄弟结点用线相连
去线：保留双亲与最左边孩子的连线，去掉双亲和 其他孩子的连线
旋转：将经过加线和去线以后的结果，进行旋转处 理得到转换后的二叉树
A
B
CD
E FGH I
B E
F
A
C D
GH
I
树转换成的二叉树其根结点的右子树一定为空
二叉树树
加线：将结点和其左孩子结点的右孩子及右子孙 全部加线相连
去线：去掉所有结点与右孩子的连线
旋转：将加线、去线后的结果，进行旋转处理， 就得到转换后的树
B E

6.5.2 堆的建立 方法一：通过构造函数MinHeap建空堆 方法一：通过构造函数 建空堆 template <class Type> MinHeap <Type>:: MinHeap ( int maxSize ) { //根据给定大小 根据给定大小maxSize,建立堆对象 根据给定大小 建立堆对象 MaxHeapSize = DefaultSize < maxSize ? maxSize : DefaultSize; //确定堆大小 确定堆大小 heap = new Type [MaxHeapSize]; //创建堆空 创建堆空 间 CurrentSize = 0; //初始化 初始化 } template <class Type> MinHeap <Type>:: MinHeap ( Type arr[ ], int n ) {
int IsFull ( ) const { return CurrentSize == MaxHeapSize; } void MakeEmpty ( ) { CurrentSize = 0; } private: enum { DefaultSize = 10 }; Type *heap; int CurrentSize; int MaxHeapSize; void FilterDown ( int i, int m ); void FilterUp ( int i ); }
6.4 线索化二叉树 6.4.1 线索 6.4 线索化二叉树
用于指示前驱与后继的指针， 用于指示前驱与后继的指针，加了线索的二叉树叫线 索化二叉树
6.5 堆 ( Heap )
6.5.1 堆的定义 定义 最小堆:任一节点的关键码均小于或等于它的左、右子女的

A B
E
G I J 1。森林中第一棵树的根 结点； 结点； 2。森林中第一棵树的子 树森林； 树森林； 3。森林中其它树构成的森 林。
14
C D F H
• 先序遍历 若森林为空，返回； 若森林为空，返回； 访问森林中第一棵树的根结点； 访问森林中第一棵树的根结点； 先序遍历第一棵树的根结点的子树森林； 先序遍历第一棵树的根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。 除去第一棵树之后剩余的树构成的森林 先序遍历除去第一棵树之后剩余的树构成的森林。 •中序遍历 中序遍历 若森林为空，返回； 若森林为空，返回； 中序遍历森林中第一棵树的根结点的子树森林； 中序遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点； 访问第一棵树的根结点； 中序遍历除去第一棵树之后剩余的树构成的森林。 除去第一棵树之后剩余的树构成的森林 中序遍历除去第一棵树之后剩余的树构成的森林。
第6 章 树和二叉树 （Tree & Binary Tree） ） 树的基本概念 二叉树 遍历二叉树和线索二叉树 树和森林 赫夫曼树及其应用
6.1 6.2 6.3 6.4 6.5
1
6.4 树和森林
一、 树和森林与二叉树的转换 二、 树和森林的存储方式 三、 树和森林的遍历
2
一、 树和森林与二叉树的转换
//左孩子的深度 //右兄弟的深度
return( (h1+1) > h2? (h1+1): h2 );
17
结论： 结论：
1. 树的先根遍历与二叉树的先序遍历相同； 树的先根遍历与二叉树的先序遍历相同； 先根遍历与二叉树的先序遍历相同 2. 树的后根遍历相当于二叉树的中序遍历； 树的后根遍历相当于二叉树的中序遍历 后根遍历相当于二叉树的中序遍历； 3. 树没有中根遍历。 树没有中根遍历。

6.4树、森林和二叉树的关系6.4.1 树的存储结构6.4.2 树、森林与二叉树的相互转换6.4.3 树与森林遍历树的主要存储方法有：1.双亲表示法2.孩子表示法3.孩子兄弟表示法1. 双亲表示法：用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置，其结点的结构如下：数据双亲Data Parent124563716151432-11ParentData4321结点序号树的双亲表示法如下图：双亲表示法的优点：利用了树中每个结点（根结点除外）只有一个双亲结点的性质，使得查找某个结点的双亲结点非常容易。

双亲表示法的缺点：在求某个结点的孩子时，需要遍历整个向量。

双亲表示法的存储结构#define MAX100 typedef struct TNode{DataType data;int parent;}TNode; 一棵树可以定义为：typedef struct{TNode tree[MAX];int nodenum;/*结点数*/ }ParentTree;2.孩子表示法：通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。

n个结点共有n个孩子链表（叶结点的孩子链表为空表），而n个结点的数据和n个孩子链表的头指针又组成一个顺序表。

A B C D ∧E ∧F ∧G∧0123456136∧r2∧45∧孩子表示法的存储结构：typedef struct ChildNode/*孩子链表结点的定义*/{int Child;/*该孩子结点在线性表中的位置*/ struct ChildNode*next;/*指向下一个孩子结点的指针*/ }ChildNode;typedef struct/*顺序表结点的结构定义*/{DataType data;/*结点的信息*/ChildNode*FirstChild;/*指向孩子链表的头指针*/}DataNode;typedef struct/*树的定义*/{DataNode nodes[MAX];/*顺序表*/int root,num;/*该树的根结点在线性表中的位置和该树的结点个数*/3. 孩子兄弟表示法（二叉链表表示法）：链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。

性质1 若二叉树的层次从1开始, 则在二叉树的 第 i 层最多有 2i-1 个结点。(i 0)
证明：i = 1 时，有2i-1 = 20 =1，成立 假定 ：i = k 时性质成立；
当 i = k+1 时，第k+1的结点至多是第k层结点 的两倍，即总的结点个数至多为2×2k-1 = 2k
故命题成立
的子树 7、删除指定结点的某一子树 8、树的遍历
23.10.2019
8
二叉树 (Binary Tree)
二叉树的定义
一棵二叉树是结点的一个有限集合，该集合 或者为空，或者是由一个根结点加上两棵分别称 为左子树和右子树的、互不相交的二叉树组成。
23.10.2019
二叉树的五种不同形态
9
二叉树的性质
n = 23.10.2019 0
n2
+
1
12
定义1 满二叉树(Full Binary Tree) 一棵深度为k 且有2k-1个结点的二叉树。
定义2 完全二叉树(Complete Binary Tree)
若设二叉树的高度为h，则共有h+1层。 除第h层外，其它各层(0h-1)的结点数都达 到最大个数，第h层从右向左连续缺若干结 点，这就是完全二叉树。
左向右连续给结点编号1, 2, …, n-1,n，然后按此结点编号将树中
各结点顺序地存放于一个一维数组中, 并简称编号为i的结点为结
点i (1 i n)。则有以下关系：
若i == 1, 则 i 无双亲
若i > 1, 则 i 的双亲为i /2
若2*i <= n, 则 i 的左子女为2*i；否则，i无左子女，必定是
23.10.2019

树、森林与二叉树的转换2008-10-10 13:36:41| 分类：C语言|字号订阅2005-07-12页面 1 共 4从树的孩子兄弟表示法和二叉树的二叉链表表示法可以看出，树的孩子兄弟表示法实质上是二叉树的二叉链表存储形式，第一个孩子指针和右兄弟指针分别相当于二叉链表的左孩子指针和右孩子指针。

所以，从物理结构上看，树的孩子兄弟表示法和二叉树的二叉链表是相同的，只是解释不同而已，如图5-32所示。

以二叉链表作为媒介，可导出树和二叉树之间的一个对应关系。

也就是说，给定一棵树，可以找到唯一的一棵二叉树与之对应。

这样，对树的操作实现就可以借助二叉树存储，利用二叉树上的操作来实现。

将一棵树转换为二叉树的方法是：⑴加线--树中所有相邻兄弟结点之间加一条连线；⑵去线--对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线；⑶层次调整--以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。

图5-33给出了树及其转换为二叉树的过程。

可以看出，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。

由于树的根结点没有兄弟，所以转换后，二叉树的根结点的右子树必为空。

根据树与二叉树的转换关系以及树和二叉树遍历的操作定义可知，树的遍历序列与由树转化成的二叉树的遍历序列之间具有如下对应关系：树的前序遍历二叉树的前序遍历树的后序遍历二叉树的中序遍历2．森林转换为二叉树森林是若干棵树的集合，将森林中的每棵树转换为二叉树，再将每棵树的根结点视为兄弟，这样，森林也同样可以转换为二叉树。

森林转换为二叉树的方法如下：⑴将森林中的每棵树转换成二叉树；⑵从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

图5-34给出了森林及其转换为二叉树的过程。

下面给出森林转换为二叉树的形式化描述。

由于一般二叉树必须仿照完全二叉树那样存 储，可能会浪费很多存储空间，单支树就是 一个极端情况。
单支树
2020/3/18
18
链表表示
2020/3/18
19
二叉树链表表示的示例
2020/3/18
20
二叉链表的静态结构
2020/3/18
21
树结点的描述 typedef int datatype; typedef struct node { datatype data;
INORDER(bitree *cnt)
{
if (cnt)
{
INORDER(t->lch);
printf(“\t%c\n”,t->data);
INORDER(t->rch);
}
}
2020/3/18
26
2020/3/18 中序遍历二叉树的递归过程图解 27
前序遍历
前序遍历二叉树算法的框架是 • 若二叉树为空，则空操作； • 否则
} return root; }
2020/3/18
24
二叉树的遍历
中序遍历
中序遍历二叉树算法的框架是： • 若二叉树为空，则空操作； • 否则
– 中序遍历左子树 (L)； – 访问根结点 (V)； – 中序遍历右子树 (R)。
遍历结果 a+b*c-d-e/f
2020/3/18
表达式语法树25
中序遍历算法
– 访问根结点 (V)； – 前序遍历左子树 (L)； – 前序遍历右子树 (R)。
遍历结果
-+a*b-cd/ef
2020/3/18
28
后序遍历
后序遍历二叉树算法的框架是 • 若二叉树为空，则空操作； • 否则