当前位置：文档之家 › 树、森林和二叉树的关系

树、森林和二叉树的关系

  • 格式：pdf
  • 大小：155.96 KB
  • 文档页数：7

下载文档原格式

  / 7

合集下载

二叉树,树,森林遍历之间的对应关系

二叉树,树,森林遍历之间的对应关系

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构树的知识点总结

数据结构树的知识点总结

数据结构树的知识点总结一、树的基本概念。

1. 树的定义。

- 树是n（n ≥ 0）个结点的有限集。

当n = 0时，称为空树。

在任意一棵非空树中：- 有且仅有一个特定的称为根（root）的结点。

- 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、…、Tm，其中每个集合本身又是一棵树，并且称为根的子树（sub - tree）。

2. 结点的度、树的度。

- 结点的度：结点拥有的子树个数称为结点的度。

- 树的度：树内各结点的度的最大值称为树的度。

3. 叶子结点（终端结点）和分支结点（非终端结点）- 叶子结点：度为0的结点称为叶子结点或终端结点。

- 分支结点：度不为0的结点称为分支结点或非终端结点。

- 除根结点之外，分支结点也称为内部结点。

4. 树的深度（高度）- 树的层次从根开始定义起，根为第1层，根的子结点为第2层，以此类推。

树中结点的最大层次称为树的深度（或高度）。

二、二叉树。

1. 二叉树的定义。

- 二叉树是n（n ≥ 0）个结点的有限集合：- 或者为空二叉树，即n = 0。

- 或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

2. 二叉树的特点。

- 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。

- 二叉树的子树有左右之分，次序不能颠倒。

3. 特殊的二叉树。

- 满二叉树。

- 一棵深度为k且有2^k - 1个结点的二叉树称为满二叉树。

满二叉树的特点是每一层上的结点数都是最大结点数。

- 完全二叉树。

- 深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

完全二叉树的叶子结点只可能在层次最大的两层上出现；对于最大层次中的叶子结点，都依次排列在该层最左边的位置上；如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子。

三、二叉树的存储结构。

1. 顺序存储结构。

- 二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。

数据结构-第6章 树和二叉树---4. 树和森林(V1)

数据结构-第6章 树和二叉树---4. 树和森林(V1)
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 ;

第6章树和二叉树

第6章树和二叉树
2.孩子表示法 孩子表示法 在结点中设置指向每个孩子的指针域， 在结点中设置指向每个孩子的指针域，利用指针 指向该结点的所有孩子结点。 指向该结点的所有孩子结点。 大多采用按树的度设置结点的指针域的个数。 大多采用按树的度设置结点的指针域的个数。
9
6.1.4 树的存储结构
3.孩子兄弟表示法 孩子兄弟表示法 在结点中设置两个指针域， 在结点中设置两个指针域，一个指针域指向该结 点的第一个孩子，另一个指针域指向其右兄弟。 点的第一个孩子，另一个指针域指向其右兄弟。
2
6.1.1树的定义 树的定义
结点的度：结点所拥有子树的个数称为结点的度。 结点的度：结点所拥有子树的个数称为结点的度。 子树 称为结点的度 树的度：树中所有结点的度的最大值称为树的度。 最大值称为树的度 树的度：树中所有结点的度的最大值称为树的度。 叶结点：度为零的结点称为叶结点。也称终端结点 终端结点或 叶结点：度为零的结点称为叶结点。也称终端结点或叶 子 分支结点：度不为零的结点称为分支结点。也称非终端 分支结点：度不为零的结点称为分支结点。也称非终端 结点。除根结点以外，分支结点也称为内部结点。 结点。除根结点以外，分支结点也称为内部结点。 孩子结点和双亲结点： 孩子结点和双亲结点：树中一个结点的子树的根结点称 为孩子结点。该结点就称为孩子结点的双亲结点。 为孩子结点。该结点就称为孩子结点的双亲结点。 兄弟结点：具有同一双亲的孩子结点互为兄弟结点。 兄弟结点：具有同一双亲的孩子结点互为兄弟结点。 结点的祖先：从根到该结点所经分支上的所有结点， 结点的祖先：从根到该结点所经分支上的所有结点，称 为结点的祖先。 为结点的祖先。
17
6.2.2 二叉树的性质
性质4 具有n（ 性质 具有 （n>0）个结点的完全二叉树的深度 ）个结点的完全二叉树的深度h= log 2 n + 1 证明： 证明： 根据完全二叉树的定义可知深度为h-1层及以上的结点构成 根据完全二叉树的定义可知深度为 层及以上的结点构成 满二叉树，因此由性质2得深度为 得深度为h的完全二叉树满足 满二叉树，因此由性质 得深度为 的完全二叉树满足 n>2h-1-1和n≤2h-1 和 整理后得到 2h-1≤n<2h 不等式两边取对数， 不等式两边取对数，得 h-1≤log2n<h 由于h为正整数 为正整数， 由于 为正整数，因此 h= log 2 n + 1

数据结构习题及答案与实验指导(树和森林)7

数据结构习题及答案与实验指导(树和森林)7

第7章树和森林树形结构是一类重要的非线性结构。

树形结构的特点是结点之间具有层次关系。

本章介绍树的定义、存储结构、树的遍历方法、树和森林与二叉树之间的转换以及树的应用等内容。

重点提示：●树的存储结构●树的遍历●树和森林与二叉树之间的转换7-1 重点难点指导7-1-1 相关术语1．树的定义：树是n（n>=0）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：①有且仅有一个特定的称为根的结点；②其余的结点可分为m（m>=0）个互不相交的子集T1，T2，…，T m，其中每个子集本身又是一棵树，并称为根的子树。

要点：树是一种递归的数据结构。

2．结点的度：一个结点拥有的子树数称为该结点的度。

3．树的度：一棵树的度指该树中结点的最大度数。

如图7-1所示的树为3度树。

4．分支结点：度大于0的结点为分支结点或非终端结点。

如结点a、b、c、d。

5．叶子结点：度为0的结点为叶子结点或终端结点。

如e、f、g、h、i。

6．结点的层数：树是一种层次结构，根结点为第一层，根结点的孩子结点为第二层，…依次类推，可得到每一结点的层次。

7．兄弟结点：具有同一父亲的结点为兄弟结点。

如b、c、d；e、f；h、i。

8．树的深度：树中结点的最大层数称为树的深度或高度。

9．有序树：若将树中每个结点的子树看成从左到右有次序的（即不能互换），则称该树为有序树，否则称为无序树。

10．森林：是m棵互不相交的树的集合。

7-1-2 树的存储结构1．双亲链表表示法以图7-1所示的树为例。

（1）存储思想:因为树中每个元素的双亲是惟一的，因此对每个元素，将其值和一个指向双亲的指针parent构成一个元素的结点，再将这些结点存储在向量中。

（2）存储示意图:-1 data:parent:（3）注意: Parrent域存储其双亲结点的存储下标，而不是存放结点值。

下面的存储是不正确的：-1 data:parent:2．孩子链表表示法（1）存储思想：将每个数据元素的孩子拉成一个链表，链表的头指针与该元素的值存储为一个结点，树中各结点顺序存储起来，一般根结点的存储号为0。

第6章演示

第6章演示
返回
二叉树的性质
性质1：二叉树第i层上的结点数目最多为2i-1(i≥1)。 性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。 性质3：在任意一棵二叉树中，若终端结点的个数为 n0，度为2的结点数为n2，则n0=n2+1。
返回
满二叉树和完全二叉树
满二叉树和完全二叉树是二叉树的两种特殊情形。 1、满二叉树(FullBinaryTree) 一棵深度为k且有2k-1个结点的二叉树称为满二叉树。 满二叉树的特点： (1)每一层上的结点数都达到最大值。即对给定的高度， 它是具有最多结点数的二叉树。 (2)满二叉树中不存在度数为1的结点，每个分支结点 均有两棵高度相同的子树，且树叶都在最下一层上。
满二叉树和完全二叉树
2、完全二叉树(Complete BinaryTree) 若一棵二叉树至多只有最下面的两层上结点的度 数可以小于2，并且最下一层上的结点都集中在该层 最左边的若干位置上，则此二叉树称为完全二叉树。 具有n个结点，其形状与满二叉树按层编号的前n 个结点的位置顺序一一对应。 完全二叉树的特点： (1)满二叉树是完全二叉树，完全二叉树不一定是满二 叉树。 (2)在满二叉树的最下一层上，从最右边开始连续删去 若干结点后得到的二叉树仍然是一棵完全二叉树。 (3)在完全二叉树中，若某个结点没有左孩子，则它一 定没有右孩子，即该结点必是叶结点。
祖先(Ancestor)和子孙(Descendant) ①路径（path） 注意： 若一个结点序列是路径，则在树的树形图表示中， 该结点序列“自上而下”地通过路径上的每条边。 从树的根结点到树中其余结点均存在一条惟一的 路径 。 A B E K L F C G H M D I J
祖先(Ancestor)和子孙(Descendant) ②祖先(Ancestor)和子孙(Descendant) 若树中结点k到ks存在一条路径，则称k是ks的祖 祖 先(Ancestor)，ks是k的子孙 子孙(Descendant)。 子孙 一个结点的祖先是从根结点到该结点路径上所经 过的所有结点，而一个结点的子孙则是以该结点为根 的子树中的所有结点。 约定： 结点k的祖先和子孙不包含结点k本身。

数据结构(树)习题与答案

一、单选题1、树最适合用来表示（）。

A.元素之间具有分支层次关系的数据B.有序数据元素C.元素之间无联系的数据D.无序数据元素正确答案：A2、在树结构中，若结点A有三个兄弟，且B是A的双亲，则B的度是（）。

A.5B.4C.3D.2正确答案：B3、下列陈述中正确的是（）。

A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中每个结点最多只有两棵子树，并且有左右之分D.二叉树中必有度为2的结点正确答案：C4、设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至少为（）。

A.2h-1B.2h+1C.h+1D.2h正确答案：A解析： A、除根之外，每层只有两个结点，且互为兄弟。

5、设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至多为（）。

A.2h-1B. 2h+1-1C. 2h-1-1D. 2h+1正确答案：A解析： A、构成完全二叉树。

6、具有n(n>0)个结点的完全二叉树的深度为（）。

A.⌊ log2(n)⌋ +1B.⌈log2(n)⌉C.⌊ log2(n)⌋D.⌈log2(n)+1⌉正确答案：A7、具有32个结点的完全二叉树有（）个叶子结点。

A.16B.14C.15D.17正确答案：A解析： A、对结点按层序编号，32号结点的双亲结点编号为16，则17至32号结点都为叶子，共16个。

8、一棵完全二叉树的第6层上有23个叶子结点，则此二叉树最多有（）结点。

A.81B.78C.80D.79正确答案：A解析： A、完全二叉树的叶子结点只能在最下两层，要使结点最多，这棵二叉树深度为7，前6层结点数共为63，第6层有32个结点，其中叶子为23个，非叶子为9个，它们的度都为2，第7层只有18个结点，故整棵二叉树结点数为81.9、具有3个结点的二叉树有（）种。

A.6B.3C.5D.4正确答案：C10、若一棵二叉树有9个度为2的结点，5个度为1的结点，则叶子结点的个数为（）。

树与二叉树的关系

右的次序顺序编号，即把树看作为有序树。
将一棵树转换为二叉树的方法： ⑴ 树中所有相邻兄弟之间加一条连线。 ⑵ 对树中的每个结点，只保留其与第一个 孩子结点之间的连线，删去其与其它孩子结 点之间的连线。 ⑶ 以树的根结点为轴心，将整棵树顺时针 旋转一定的角度，使之结构层次分明。
树转换为二叉树示意图
A
A
B
E
CF G
DH
I
A
B
E
CF G
DH
I
J
J
A
BC D EG FH I J
用递归的方法描述其转换
若B是一棵二叉树，T是B的根结点，L是B的 左子树，R为B的右子树，设B对应的森林F（B） 中含有的n棵树为T1,T2, …,Tn，则有： （1）B为空，则：F（B）为空的森林（n＝0）。
（2）B非空，则：
树
森林
二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历
3、森林的后序遍历*
若森林非空，则遍历方法为：
（1）后序遍历森林中第一棵树的根结点的子 树森林。 （2）后序遍历除去第一棵树之后剩余的树构 成的森林。 （3）访问第一棵树的根结点。
6.5 哈夫曼树及其应用
6.5.1 哈夫曼树
哈夫曼树最典型、最广泛的应用是在 编码技术上，利用哈夫曼树，可以得到 平均长度最短的编码。这在通讯领域是 极其有价值的。
权值 双亲序号 左孩子序号 右孩子序号
静态三叉链表结构定义
#define N 20 #define M 2*N-1 typedef struct { int weight ;
int parent，Lchild，Rchild ; }HTNode, HuffmanTree[M+1];

数据结构第6章树和二叉树3树和森林ppt课件


§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 树和森林 ❖树的存储结构——孩子兄弟表示法
或称二叉树表示法，或称二叉链表表示法。即以 二叉链表作树的存储结构。链表中结点的两个链域分 别指向该结点的第一个孩子结点和下一个兄弟结点。

二叉树,树,森林互相转化的题

二叉树,树,森林互相转化的题
二叉树、树和森林是数据结构中常见的概念，它们之间可以相互转化。

首先我们来看一下它们的定义和特点。

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

树是由n（n>=1）个节点组成的有限集合，它们之间存在唯一的父子关系。

而森林是由若干棵互不相交的树组成。

现在我们来看一下它们之间的转化关系：
1. 二叉树转化为树，将二叉树的左子节点作为树的子节点，右子节点作为兄弟节点，这样就可以将二叉树转化为树。

2. 树转化为二叉树，将树的每个节点的第一个子节点作为二叉树的左子节点，其余的子节点作为左子节点的右子节点，这样就可以将树转化为二叉树。

3. 树转化为森林，如果一个树有多个子节点，可以将它的子节点拆分成多棵树，这样就可以将树转化为森林。

4. 森林转化为树，将森林中的每棵树的根节点作为新树的子节点，这样就可以将森林转化为树。

通过以上转化方法，我们可以实现二叉树、树和森林之间的互相转化。

这些转化方法在实际的数据结构操作中有着重要的应用，能够帮助我们更好地理解和利用这些数据结构。

在实际编程中，我们可以根据具体的需求选择合适的数据结构，并通过转化实现各种操作和算法。

希望这些信息能够对你有所帮助。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）
结点。
下图为树的孩子兄弟表示结构。
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）中序遍历
若森林非空，则遍历方法为：
①中序遍历森林中第一棵树的根结点的子树森林。
②访问第一棵树的根结点。
③中序遍历除去第一棵树之后剩余的树构成的森林。
例如，右图中森林的中序遍历序列为 BCDAFEHJIG。
（3）后序遍历
若森林非空，则遍历方法为：
①后序遍历森林中第一棵树的根结点的子树森林。
② 后序遍历除去第一棵树之后剩余的树构成的森林。
后根遍历分别与森林的先序遍历和中序遍历对应。森林的遍历算法可以采用其对应的二叉树
的遍历算法来实现。
树采用这种存储结构时，其结果如下图所示。
r
A
B
C
DE F G
0A 1B 2C 3 D∧ 4 E∧ 5 F∧ 6 G∧
1 3 6∧
2∧ 4
5∧
树的孩子表示法
孩子表示法的存储结构定义如下：
typedef struct ChildNode
/* 孩子链表结点的定义 */
{
int Child;
/* 该孩子结点在线性表中的位置 */
1．树转换为二叉树
对于一棵无序树，树中结点的各孩子的次序是无关紧要的，而二叉
树中结点的左、右孩子结点是有区别的。为了避免混淆，约定树中每一
A
个结点的孩子结点按从左到右的次序顺序编号，也就是说，把树作为有 序树看待。如右图所示的一棵树，根结点 A 有三个孩子 B、C、D，可以
BC D
认为结点 B 为 A 的第一个孩子结点，结点 D 为 A 的第三个孩子结点。 将一棵树转换为二叉树的方法是：
双亲 Parent
双亲表示法结点结构
整棵树用含有 MAX 个上述结点的一维数组来表示，如下图所示。
这种存储法利用了树中每个结点（根结点除外）只有一
结点
个双亲结点的性质，使得查找某个结点的双亲结点非常容易。
Data
序号
反复使用求双亲结点的操作，也可以较容易地找到树根。但
0A
是，在这种存储结构中，求某个结点的
第 8 讲 树、森林和二叉树的关系——教学讲义
本节主要讨论树的存储结构以及树、森林与二叉树的转换关系。
一、 树的存储结构
树的主要存储方法有以下三种： 1．双亲表示法
这种方法用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指 示其双亲结点在表中的位置，其结点的结构如下图所示。：
数据 Data
}
A BC D EF G
H
树
}
3. 森林的遍历 森林的遍历方法主要有以下三种： （1）先序遍历
若森林非空，则遍历方法为： ①访问森林中第一棵树的根结点。
A
E
G
B
C
D
H F
I
J 森林
②先序遍历第一棵树的根结点的子树森林。
③先序遍历除去第一棵树之后剩余的树构成的森林。
例如，右图中森林的先序遍历序列为 ABCDEFGHIJ。
6.4.3 树与森林的遍历
1．树的遍历
树的遍历方法主要有以下两种：
（1）先根遍历
若树非空，则遍历方法为：
① 访问根结点。
② 从左到右，依次先根遍历根结点的每一棵子树。
例如，右图中树的先根遍历序列为 ABECFHGD。
（2）后根遍历
若树非空，则遍历方法为：
①从左到右，依次后根遍历根结点的每一棵子树。
②访问根结点。
struct ChildNode * next; /*指向下一个孩子结点的指针 */
} ChildNode;
typedef struct {
DataType data; ChildNode * FirstChild ; } DataNode;
/* 顺序表结点的结构定义 */
/* 结点的信息 */ /* 指向孩子链表的头指针 */
A
1B
孩子时需要遍历整个数组。
双亲表示法的形式说明如下：
2C
#define MAX 100
B
C
3D
typedef struct TNode
4E
{ DataType data;
5F
DE F G
6G
int parent;
Parent
-1 0 0 1 1 1 2
} TNode;
树可以定义为:
typedef struct
E A∧
C
∧D ∧ ∧E ∧
树与二叉树的对应关系
因此，二叉链表的有关处理算法可以很方便地转换为树的孩子兄弟链表的处理算法。 2．森林转换为二叉树 森林是若干棵树的集合。树可以转换为二叉树，森林同样也可以转换为二叉树。因此， 森林也可以方便地用孩子兄弟链表表示。森林转换为二叉树的方法如下： （1） 将森林中的每棵树转换成相应的二叉树。 （2） 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前
void RootFirst(CSTree root)
{
if (root!=NULL)
{
Visit (root ->data);
/*访问根结点*/
RootFirst (root->FirstChild); /*先根遍历首子树*/
RootFirst (root->Nextsibling); /*先根遍历兄弟树*/
步，便可找到 x 的第 i 个孩子。如果在这种结构中为每个结点增设一个 Parent 域，则同样
可以方便地实现查找双亲的操作。
二、树、森林与二叉树的相互转换
前面介绍了树的存储结构和二叉树的存储结构，从中可以看到，树的孩子兄弟链表结构 与二叉树的二叉链表结构在物理结构上是完全相同的，只是它们的逻辑含义不同，所以树和 森林与二叉树之间必然有着密切的关系。本节介绍树和森林与二叉树之间的相互转换方法。
{
if (root!=NULL)
{ Visit(root ->data);
/* 访问根结点 */
p= root-> FirstChild;
while (p!=NULL)
{ RootFirst( p );
/* 访问以 p 为根的子树 */
p = p -> Nextsibling;
}
}
}
[方法二]：
一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由 森林转换得到的二叉树。 森林转换为二叉树的过程，还可以用递归的方法描述上述转换过程： 将森林 F 看作树的有序集 F={T1，T2，…,TN}，它对应的二叉树为 B（F）： （1）若 N=0，则 B（F）为空。 （2）若 N>0，二叉树 B（F）的根为森林中第一棵树 T1 的根； B（F）的左子树为 B （{T11，…，T1m}），其中{T11，…，T1m}是 T1 的子树森林；B（F）的右子树是 B（{T2，…， TN}）。 根据这个递归的定义，可以很容易地写出递归的转换算法。
③访问第一棵树的根结点。
例如，右图中森林的后序遍历序列为 DCBFJIHGEA。
对照二叉树与森林之间的转换关系可以发现，森林的先序遍历、中序遍历和后序遍历与
其相应二叉树的先序遍历、中序遍历和后序遍历是对应相同的，因此可以用相应二叉树的遍
历结果来验证森林的遍历结果。另外，树可以看成只有一棵树的森林，所以树的先根遍历和
B C
A
E
B
F
G
C
A
E
F
G
D
H
D
H
(a)
I
(b)
I
J
J
二叉树到森林的转换
A
E
BCD F
G
HI
(c)
J
同样，可以用递归的方法描述上述转换过程。 若 B 是一棵二叉树，T 是 B 的根结点，L 是 B 的左子树，R 为 B 的右子树，且 B 对应的森 林 F（B）中含有的 n 棵树为 T1,T2, …,Tn，则有：
子，而森林转换后的二叉树，其根结点有右孩子。将一棵二叉树还原为树或森林，具体方法 如下：
（1） 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、……都与 该结点的双亲结点用线连起来。