第六章 树和二叉树

1.本章中主要介绍下列内容 ⑴树的定义和存储结构 ⑵二叉树的定义、性质、存储结构 ⑶二叉树的遍历、线索算法 ⑷树和二叉树的转换 　　⑴树的定义和存储结构 　　⑵二叉树的定义、性质、存储结构 　　⑶二叉树的遍历、线索算法 　　⑷树和二叉树的转换 　　⑸赫夫曼树及其应用

⒉教学目的 ⑴ 深刻理解二叉树的定义、性质及其存储方法； ⑵ 深刻理解树的定义、术语； ⑶ 熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义； ⑷ 领会并掌握树的各种存储结构； ⑸ 理解并掌握二叉树的三种遍历算法； ⑹ 掌握二叉树的线索化方法； ⑺ 灵活运用二叉树的遍历方法解决相关的应用问题； ⑻ 熟练掌握森林与二叉树间的相互转换； ⑼ 领会树和森林的遍历； ⑽ 了解树的简单应用。

⑴二叉树的定义、逻辑特点及性质，在二叉树上定义的基本运算； ⒊教学重点 ⑴二叉树的定义、逻辑特点及性质，在二叉树上定义的基本运算； ⑵二叉树的链式存储结构及其类型说明，二叉树的顺序存储结构及其类型说明； ⑶二叉树链式存储结构的组织方式； ⑷二叉树的三种遍历方法及其算法； ⑸以遍历为基础在二叉树上实现的几种运算； ⑹赫夫曼树和赫夫曼算法； ⑺树的存储结构； ⑻森林与二叉树的转换。

4.本章难点：     ⑴二叉树的遍历     ⑵线索算法     ⑶赫夫曼树及其应用

6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林的表示方法 6.7 树和森林的遍历 6.8 赫夫曼树与赫夫曼编码

6.1 树的类型定义

数据对象 D： D是具有相同特性的数据元素的集合。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1, T2, …, Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 树的定义是递归。

树是一类重要的非线性数据结构，是以分支关系定义的层次结构 特点： 树中至少有一个结点——根 树中各子树是互不相交的集合

A 只有根结点的树 A B C D E F G H I J K L M 有子树的树 根 子树

树的定义还可形式化的描述为二元组的形式： T＝（D，R） 其中D为树T中结点的集合，R为树中结点之间关系的集合。 当树为空树时，D＝Φ；当树T不为空树时有： D＝{Root}∪DF 其中，Root为树T的根结点，DF为树T的根Root的子树集合。DF可由下式表示： DF＝D1∪D2∪…∪Dm且Di∩Dj＝Φ （i≠j，1≤i≤m，1≤j≤m) 当树T中结点个数n≤1时，R＝Φ；当树T中结点个数n>1时有： R＝{<Root，ri>，i＝1，2，…，m} 其中，Root为树T的根结点，ri是树T的根结点Root的子树Ti的根结点。

下图是一棵具有9个结点的树，即T＝{A，B，C，…，H，I}，结点A为树T的根结点，除根结点A之外的其余结点分为两个不相交的集合：T1＝{B,D,E,F,H,I}和T2={C,G}，T1和T2构成了结点A的两棵子树，T1和T2本身也分别是一棵树。例如，子树T1的根结点为B，其余结点又分为三个不相交的集合： T11＝{D}，T12＝{E,H,I}和T13＝{F}。T11、T12和T13构成了子树T1的根结点B的三棵子树。如此可继续向下分为更小的子树，直到每棵子树只有一个根结点为止。

从树的定义和上图(6.2)的示例可以看出，树具有下面两个特点： ⑴树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。 ⑵树中所有结点可以有零个或多个后继结点。 由此特点可知，下图所示的都不是树结构。

基本操作： 查 找 类 插 入 类 删 除 类

查找类： Root(T) // 求树的根结点 Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历

插入类： InitTree(&T) // 初始化置空树 CreateTree(&T, definition) // 按定义构造树 Asflag(T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树

删除类： DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树 ClearTree(&T) // 将树清空 DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树

7.1.2 树的表示 树的表示方法有四种，各用于不同的目的。 1．直观表示法 7.1.2 树的表示 树的表示方法有四种，各用于不同的目的。 1．直观表示法 树的直观表示法就是以倒着的分支树的形式表示，下图就是一棵树的直观表示。其特点就是对树的逻辑结构的描述非常直观。是数据结构中最常用的树的描述方法。

2．嵌套集合表示法 所谓嵌套集合是指一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个。用嵌套集合的形式表示树，就是将根结点视为一个大的集合，其若干棵子树构成这个大集合中若干个互不相交的子集，如此嵌套下去，即构成一棵树的嵌套集合表示。下图就是一棵树的嵌套集合表示。

3．凹入表示法 树的凹入表示法如左图所示。 4．广义表表示法 树用广义表表示，就是将根作为 由子树森林组成的表的名字写在表 的左边，这样依次将树表示出来。 (A(B(D,E(H,I),F),C(G)))

对比树型结构和线性结构的结构特点

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 线性结构 树型结构 根结点 (无前驱) 第一个数据元素 (无前驱) 最后一个数据元素 (无后继) 多个叶子结点 (无后继) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 其它数据元素 (一个前驱、 一个后继) 其它数据元素 (一个前驱、 多个后继)

基 本 术 语

结点: 数据元素+若干指向子树的分支 结点的度: 分支的个数 树的度: 树中所有结点的度的最大值 D 叶子结点: 度为零的结点 H I J 分支结点: 度大于零的结点 M

(从根到结点的)路径： 结点的层次: 树的深度： 由从根到该结点所经分支和结点构成 孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点 A 由从根到该结点所经分支和结点构成 B C D E F G H I J 孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点 K L M 结点的层次: 假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1 树的深度： 树中叶子结点所在的最大层次

结点A的度：3 结点B的度：2 结点M的度：0 叶子：K，L，F，G，M，I，J 结点I的双亲：D 结点L的双亲：E 结点A的孩子：B，C，D 结点B的孩子：E，F A B C D E F G H I J K L M 结点B，C，D为兄弟 结点K，L为兄弟 树的度：3 树的深度：4 结点F，G为堂兄弟 结点A是结点F，G的祖先 结点A的层次：1 结点M的层次：4

有向树： 有序树： 无序树： (１) 有确定的根； (２) 树根和子树根之间为有向关系。 子树之间存在确定的次序关系。 子树之间不存在确定的次序关系。

森林： 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林 是m（m≥0）棵互 A 森林： B C D 是m（m≥0）棵互 不相交的树的集合 E F G H I J K L M 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林

森林: 零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林。

6.2 二叉树的类型定义

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。 A B E C F G D 左子树 H K

二叉树的五种基本形态： 只含根结点 空树 左右子树均不为空树 N 右子树为空树 左子树为空树 N N N L R L R

二叉树的主要基本操作： 查 找 类 插 入 类 删 除 类

PreOrderTraverse(T, Visit()); Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit());

CreateBiTree(&T, definition); InsertChild(T, p, LR, c); InitBiTree(&T); Asflag(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);

ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(T, p, LR);

二叉树的相关概念 (1）结点的度。结点所拥有的子树的个数称为该结点的度。 （2）叶结点。度为0的结点称为叶结点，或者称为终端结点。 （3）分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。 （4）左孩子、右孩子、双亲、兄弟。树中一个结点的子树的根结点称为这个结点的孩子。在二叉树中，左子树的根称为左孩子，右子树的根称为右孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。

（5）路径、路径长度。如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（1≤i<k）,就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。 （6）祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。 （7）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。 （8）树的深度。树中所有结点的最大层数称为树的深度。 （9）树的度。树中各结点度的最大值称为该树的度。

（10）满二叉树。 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。如图所示，(a)图就是一棵满二叉树，(b)图则不是满二叉树，因为，虽然其所有结点要么是含有左右子树的分支结点，要么是叶子结点，但由于其叶子未在同一层上，故不是满二叉树。 特点：每一层上的结点数都是最大结点数

(11) 完全二叉树。 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。 特点 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1

1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 4 5 6 7 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6

二叉树 的重要特性

在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1) 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1) 用归纳法证明： 归纳基： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点： 2i-1 = 20 = 1； 假设对所有的 j，1≤ j  i，命题成立； 二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2i-2 2 = 2i-1 。

性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）。 证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+       +2k-1 = 2k-1 。

性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。 在二叉树中，除根结点外，其余结点都有唯一的一个进入分支。设B为二叉树中的分支数，那么有： B＝n－1 （6-2） 这些分支是由度为1和度为2的结点发出的，一个度为1的结点发出一个分支，一个度为2的结点发出两个分支，所以有： B＝n1＋2n2 （6-3） 综合（6-1）、（6-2）、（6-3）式可以得到： n0＝n2＋1

例如 n0=1,n2=0，按性质3有n0=n2+1， (a) 单枝二叉树 (b) 二叉树 n0=6，n2=5，则n0=n2+1=6

性质 4 ： 具有 n 个结点的完全二叉树的深度为  log2n +1 。 证明： 设完全二叉树的深度为 k 则根据第二条性质得 2k-1≤ n < 2k 即 k-1 ≤ log2 n < k 因为 k 只能是整数,因此, k =log2n + 1 。

性质 5 ： 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点； (2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

证明：对于j=1，如果2×1≤n，则1的左孩子是2。如果2j=2×1=2>n，说明不存在两个结点，当然也就没有左孩子，以上是证(2)。如果2×1+1=3≤n的话，这个结点是存在的，它的右孩子是2×1+1=2×j+1=3，如果3>n，说明此结点不存在，所以j没有右孩子。 现在假定对于所有的j(1≤j≤i)，j的左孩子是2j，并且2j>n没有左孩子；j的右孩子是2j+1，2j+1>n没有右孩子。要证j=i+1时，i+1的左孩子是2(i+1)，i+1的右孩子是2(i+1)+1，以及2(i+1)>n，i+1没有左孩子，2(i+1)+1>n，i+1没有右孩子。

结点i和i+1在同一层上 结点i和i+l不在同一层上。 根据完全二叉树的特点，与i+1的左孩子相邻的前两个结点是i的左孩子和右孩子，由归纳法假定，i的左孩子是2i，i的右孩子是2i+1，所以，i+1的左孩子应该是2i+2=2(i+1)，如果2(i+1)>n，说明这个结点不存在，所以i+1没有左孩子，而i+1的右孩子应该是2i+3=2(i+1)+1，如果2(i+1)+1>n，说明不存在这个结点，也就没有右孩子。

最后证明(1)，当i=1时，就是根，因此没有双亲，当i≠1时，由(2)、(3)可知，如果i为左孩子，即2×i/2=i，则i/2是i的双亲，如果i为右孩子，i=2p+1，i的双亲应该是p，p== (i-1)/2，所以无论哪种情况都有i/2是i的双亲，证毕。

6.3 二叉树的存储结构 一、 二叉树的顺序 存储表示 二、二叉树的链式 存储表示

一、 二叉树的顺序存储表示 所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系，然而只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点，这种存储才有意义。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

#define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_ TREE_SIZE]; // 0号单元存储根结点 SqBiTree bt;

下面给出一棵完全二叉树的顺序存储示意。 如bt[5]的双亲在bt[2](利用性质5(1)，i=5， i/2 =2)， 如bt[4]的双亲在bt[2]，i=4， i/2 =2)，而它的左、右孩子则在bt[8]和bt[9]中（利用性质5(2)、(3)，i=4，2i=8，2i+1=9 )

对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。 1 2 3 4 5 6 7 一般二叉树的顺序存储结构

如图给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。

例如: A 2 1 B D 6 4 E C 13 F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 A B D C E F

最坏的情况是右单支树，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。

二、二叉树的链式存储表示 1. 二叉链表 2．三叉链表

1.二叉链表存储 链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为： 其中，data域存放某结点的数据信息；lchild 与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。

下图(a)给出一棵二叉树的二叉链表示。二叉链表也可以带头结点的方式存放，如图(b)所示。

尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。后面所涉及到的二叉树的链式存储结构不加特别说明的都是指二叉链表结构。 二叉树的二叉链表存储表示可描述为：

即将BiTree定义为指向二叉链表结点结构的指针类型。 C 语言的类型描述如下: typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; 即将BiTree定义为指向二叉链表结点结构的指针类型。 结点结构: lchild data rchild

2.三叉链表存储 每个结点由四个域组成，具体结构为： 其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。

下图给出一棵二叉树的三叉链表示。

struct TriTNode *lchild, *rchild; // 左右孩子指针 typedef struct TriTNode { // 结点结构 TElemType data; struct TriTNode *lchild, *rchild; // 左右孩子指针 struct TriTNode *parent; //双亲指针 } TriTNode, *TriTree; 结点结构: parent lchild data rchild

6.4 遍历二叉树

一、问题的提出 二、先左后右的遍历算法 三、算法的递归描述 四、中序遍历算法的非递归描述 五、遍历算法的应用举例

一、问题的提出 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结点的信息等。

“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构， 每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题。

二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。 遍历是二叉树中经常要用到的一种操作。按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。 通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，找一个完整而有规律的走法，以得到树中所有结点的一个线性排列，即遍历操作使非线性结构线性化。

由二叉树的定义可知，一棵二叉树是由根结点、根结点的左子树和根结点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。 若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。 如果限定先左后右，则只有前三种方式，即 DLR（称为先序遍历） LDR（称为中序遍历） LRD（称为后序遍历） D L R LDR、LRD、DLR RDL、RLD、DRL

二、先左后右的遍历算法 先（根）序的遍历算法 中（根）序的遍历算法 后（根）序的遍历算法

1．先序遍历（DLR） 先序遍历的递归过程为：若二叉树为空，遍历结束。否则, ⑴访问根结点； ⑵先序遍历根结点的左子树； ⑶先序遍历根结点的右子树。 先序遍历二叉树的递归算法如下： void PreOrder（BiTree bt） /*先序遍历二叉树bt*/ { if (bt==NULL) return; /*递归调用的结束条件*/ Visite（bt->data）; /*访问结点的数据域*/ PreOrder（bt->lchild）; /*先序递归遍历bt的左子树*/ PreOrder（bt->rchild）; /*先序递归遍历bt的右子树*/ }

先序遍历: 先序遍历序列：A B D C D L R D L R A D L R A D B C B > D L R C >

对于上图所示的二叉树，按先序遍历所得到的结点序列为： A B D G C E F

void preorder(BiTree bt) { if(bt!=NULL) { printf("%d\t",bt->data); preorder(bt->lchild); preorder(bt->rchild); } T A printf(A); pre(T L); A pre(T R); T B printf(B); pre(T L); T C printf(C); pre(T L); B C T > 左是空返回 pre(T R); T > 左是空返回 T > 右是空返回 T D printf(D); pre(T L); D 返回 T > 左是空返回 T > 右是空返回 主程序 Pre( T ) 返回 pre(T R); 返回 返回 先序序列：A B D C pre(T R); 返回

2．中序遍历（LDR） 中序遍历的递归过程为：若二叉树为空，遍历结束。否则， ⑴中序遍历根结点的左子树； ⑵访问根结点； ⑶中序遍历根结点的右子树。 中序遍历二叉树的递归算法如下： void InOrder（BiTree bt） /*中序遍历二叉树bt*/ { if (bt==NULL) return; /*递归调用的结束条件*/ InOrder（bt->lchild）; /*中序递归遍历bt的左子树*/ Visite（bt->data）; /*访问结点的数据域*/ InOrder（bt->rchild）; /*中序递归遍历bt的右子树*/ }

中序遍历: 中序遍历序列：B D A C L D R L D R A L D R A D B C > L D R B > C

对于上图所示的二叉树，按中序遍历所得到的结点序列为： D G B A E C F

3．后序遍历（LRD） 后序遍历的递归过程为：若二叉树为空，遍历结束。否则， ⑴后序遍历根结点的左子树； ⑵后序遍历根结点的右子树。 ⑶访问根结点； 后序遍历二叉树的递归算法如下： void PostOrder（BiTree bt） /*后序遍历二叉树bt*/ { if (bt==NULL) return; /*递归调用的结束条件*/ PostOrder（bt->lchild）; /*后序递归遍历bt的左子树*/ PostOrder（bt->rchild）; /*后序递归遍历bt的右子树*/ Visite（bt->data）; /*访问结点的数据域*/ }

后序遍历: 后序遍历序列： D B C A L R D A A L R D L R D C B D > B > > C

对于上图所示的二叉树，按后序遍历所得到的结点序列为： G D B E F C A

4. 层次遍历 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对于下图所示的二叉树，按层次遍历所得到的结果序列为： A B C D E F G

由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作： ⑴访问该元素所指结点； ⑵若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。

在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组Queue[MAXNODE]用以实现队列，变量front和rear分别表示当前对首元素和队尾元素在数组中的位置。 void LevelOrder（BiTree bt） /*层次遍历二叉树bt*/ { BiTree Queue[MAXNODE]; int front,rear; if (bt==NULL) return; front=-1; rear=0; queue[rear]=bt;

while(front!=rear) { front++; Visite(queue[front]->data); /*访问队首结点的数据域*/ if (queue[front]->lchild!=NULL) /*将队首结点的左孩子结点入队列*/ { rear++; queue[rear]=queue[front]->lchild; } if (queue[front]->rchild!=NULL) /*将队首结点的右孩子结点入队列*/ queue[rear]=queue[front]->rchild; } }

先序遍历： 中序遍历： 后序遍历： 层次遍历： - + a * b c d / e f - + / a * b e f c d 前缀（波兰式） 中缀表示 后缀（逆波兰式）

二叉树遍历的非递归实现 前面给出的二叉树先序、中序和后序三种遍历算法都是递归算法。当给出二叉树的链式存储结构以后，用具有递归功能的程序设计语言很方便就能实现上述算法。然而，并非所有程序设计语言都允许递归；另一方面，递归程序虽然简洁，但可读性一般不好，执行效率也不高。因此，就存在如何把一个递归算法转化为非递归算法的问题。解决这个问题的方法可以通过对三种遍历方法的实现过程的分析得到。

A B D G C E F D G B A E C F G D B E F C A

这一路线正是从根结点开始沿左子树深入下去，当深入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返回时遇到结点访问，后序遍历是在从右子树返回时遇到结点访问。 在这一过程中，返回结点的顺序与深入结点的顺序相反，即后深入先返回，可以用栈来帮助实现这一遍历路线。其过程如下： 在沿左子树深入时，深入一个结点入栈一个结点，若为先序遍历，则在入栈之前访问之；当沿左分支深入不下去时，则返回，即从堆栈中弹出前面压入的结点，若为中序遍历，则此时访问该结点，然后从该结点的右子树继续深入；若为后序遍历，则将此结点再次入栈，然后从该结点的右子树继续深入，与前面类同，仍为深入一个结点入栈一个结点，深入不下去再返回，直到第二次从栈里弹出该结点，即从右子树返回时，才访问之。

（1）先序遍历的非递归实现 算法思想： ①如果指向根结点的指针非空，则访问根结点；然后将根结点指针进栈；最后将指针指向该结点的左子树根结点，继续遍历； ②如果指向根结点的指针为空，则应该退至上一层 若从左子树返回，则应该将指针指向当前层根结点的右子树根结点，继续遍历。 若从右子树返回，则表明当前层遍历结束，应该继续退栈。 ③当指针为空并且栈为空时，遍历结束。

在下面算法中，二叉树以二叉链表存放，一维数组stack[MAXNODE]用以实现栈，变量top用来表示当前栈顶的位置。 void NRPreOrder（BiTree bt） /*非递归先序遍历二叉树*/ { BiTree stack[MAXNODE],p; int top; if (bt==NULL) return; top=-1; p=bt;

while(!(p==NULL&&top==-1)) { Visite(p->data); /*访问结点的数据域*/ if (top<MAXNODE-1) /*将当前指针p压栈*/ {top++; stack[top]=p;} else { printf(“栈溢出”)；return；} p=p->lchild； /*指针指向p的左孩子*/ } if (top=-1) return; /*栈空时结束*/ { p=stack[top]; top--; /*从栈中弹出栈顶元素*/ p=p->rchild; /*指针指向p的右孩子结点*/

对于下图所示的二叉树，用该算法进行遍历过程中，栈stack和当前指针p的变化情况以及树中各结点的访问次序如下表所示。

（2）中序遍历的非递归实现 算法思想。 ①如果指向根结点的指针非空，则将根结点指针进栈，然后将指针指向该结点的左子树根结点，继续遍历。 ②如果指向根结点的指针为空，则应该退至上一层 若从左子树返回，则应该访问当前层根结点，然后将指针指向该结点的右子树根结点，继续遍历； 若从右子树返回，则表明当前层遍历结束，应该继续退栈。 ③当指针为空并且栈为空时，遍历结束。

中序遍历的非递归算法的实现，只需将先序遍历的非递归算法中的Visite(p->data)移到p=stack[top]和p=p->rchild之间即可。

步骤 栈的内容 指针的指向 初态 空 A 1 B 2 AB C 3 ABC ^（C的左孩子） 4 ^（C的右孩子） 5 D 6 AD 访问数据 栈的内容 指针的指向 初态 空 A 1 B 2 AB C 3 ABC ^（C的左孩子） 4 ^（C的右孩子） 5 D 6 AD ^（D的左孩子） 7 E 8 AE ^（E的左孩子） 9 ^（E的右孩子） 10 ^（A的右孩子）

（3）后序遍历的非递归实现 由前面的讨论可知，后序遍历与先序遍历和中序遍历不同，在后序遍历过程中，结点在第一次出栈后，还需再次入栈，也就是说，结点要入两次栈，出两次栈，而访问结点是在第二次出栈时访问。因此，为了区别同一个结点指针的两次出栈，设置一标志flag，令： flag＝ 当结点指针进、出栈时，其标志flag也同时进、出栈。因此，可将栈中元素的数据类型定义为指针和标志flag合并的结构体类型。定义如下： typedef struct { BiTree link; int flag; } stacktype;

算法思想： ①如果指向根结点的指针不为空，先将flag置1；再将flag和根结点一道送入栈中；然后将指针指向该结点的左子树根结点；继续遍历。 ②如果指向根结点的指针为空，则应该退至上一层， 若flag为1，则改变flag的值，将flag置2；再把flag和弹出的结点重新装入栈中；然后将指针指向该结点的右子树根结点；继续遍历。 若flag为2，则访问弹出的结点，并将弹出的指针置为空。 ③直到栈为空并且指针为空时，遍历结束。

后序遍历二叉树的非递归算法如下。在算法中，一维数组stack[MAXNODE]用于实现栈的结构，指针变量p指向当前要处理的结点，整型变量top用来表示当前栈顶的位置，整型变量flag为结点p的标志量。 void NRPostOrder(BiTree bt) /*非递归后序遍历二叉树bt*/ { stacktype stack[MAXNODE]; BiTree p; int top,flag; if (bt==NULL) return; top=-1 /*栈顶位置初始化*/ p=bt;

while (!(p==NULL && top==-1)) { if (p!=NULL) /*结点第一次进栈*/ { top++; stack[top].link=p; stack[top].flag=1; p=p->lchild; /*找该结点的左孩子*/ } else { p=stack[top].link; flag=stack[top].flag; top--; if (flag==1) /*结点第二次进栈*/ { top++; stack[top].link=p; stack[top].flag=2; /*标记第二次出栈*/ p=p->rchild; } { Visite(p->data); /*访问该结点数据域值*/ p=NULL; }

步骤 访问数据 栈的内容 flag的值 指针的指向 初态 空 A 1 A1 B 2 A1B1 C 3 A1B1C1 ^（C的左孩子） 4 5 A1B1C2 ^（C的右孩子） 6 7 ^ 8 9 A1B2 D 10 A1B2D1 ^（D的左孩子） 11 12 A1B2D2 E 13 A1B2D2E1 ^（E的左孩子） 14 15 A1B2D2E2 ^（E的右孩子） 16 17 18 19 20 21 22 23 A2 ^（A的右孩子） 24 25

由遍历序列恢复二叉树 从前面讨论的二叉树的遍历知道，任意一棵二叉树结点的先序序列和中序序列都是唯一的。反过来，若已知结点的先序序列和中序序列，能否确定这棵二叉树呢？这样确定的二叉树是否是唯一的呢？

由二叉树的先序和中序序列建树 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列 根 左子树 右子树 二叉树的中序序列 左子树 根 右子树

根据定义，二叉树的先序遍历是先访问根结点，其次再按先序遍历方式遍历根结点的左子树，最后按先序遍历方式遍历根结点的右子树。这就是说，在先序序列中，第一个结点一定是二叉树的根结点。另一方面，中序遍历是先遍历左子树，然后访问根结点，最后再遍历右子树。这样，根结点在中序序列中必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。这样，就确定了二叉树的三个结点。同时，左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列，如此递归下去，当取尽先序序列中的结点时，便可以得到一棵二叉树。

同样的道理，由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。因为，依据后序遍历和中序遍历的定义，后序序列的最后一个结点，就如同先序序列的第一个结点一样，可将中序序列分成两个子序列，分别为这个结点的左子树的中序序列和右子树的中序序列，再拿出后序序列的倒数第二个结点，并继续分割中序序列，如此递归下去，当倒着取尽后序序列中的结点时，便可以得到一棵二叉树。

a a b c d e f g a b c d e f g c c b d a e g f b d e g f 例如: ^ ^ ^ ^ ^ 先序序列中序序列 c c b d a e g f b d a e g f a b e ^ c d f ^ ^ ^ ^ ^ g ^ ^

下面通过一个例子，来给出由二叉树的先序序列和中序序列构造唯一的一棵二叉树的实现算法。 已知一棵二叉树的先序序列与中序序列分别为： A B C D E F G H I B C A E D G H F I 试恢复该二叉树。

上述过程是一个递归过程，其递归算法的思想是：先根据先序序列的第一个元素建立根结点；然后在中序序列中找到该元素，确定根结点的左、右子树的中序序列；再在先序序列中确定左、右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树。

void ReBiTree（char preod[ ],char inod[ ],int n,BiTree root） { if (n≤0) 下面给出用C语言描述的该算法。假设二叉树的先序序列和中序序列分别存放在一维数组preod[ ]与inod[ ]中，并假设二叉树各结点的数据值均不相同。 void ReBiTree（char preod[ ],char inod[ ],int n,BiTree root） /*n为二叉树的结点个数，root为二叉树根结点的存储地址*/ { if (n≤0) root=NULL; else PreInOd(preod,inod,1,n,1,n,&root); }

void PreInOd（char preod[ ],char inod[ ],int i,j,k,h,BiTree *t） { *t=(BiTNode *)malloc(sizeof(BiTNode)); *t->data=preod[i]; m=k; while (inod[m]!=preod[i]) m++; if (m==k) *t->lchild=NULL else PreInOd(preod,inod,i+1,i+m-k,k,m-1,&t->lchild); if (m==h) *t->rchild=NULL PreInOd(preod,inod,i+m-k+1,j,m+1,h,&t->rchild); }

五、遍历算法的应用举例 1、统计二叉树中叶子结点的个数 (先序遍历) 2、求二叉树的深度(后序遍历) 3、建立二叉树的存储结构

1、统计二叉树中叶子结点的个数 算法基本思想: 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。

void CountLeaf (BiTree T, int& count){ if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if } // CountLeaf

2、求二叉树的深度(后序遍历) 算法基本思想: 首先分析二叉树的深度和它的左、右子树深度之间的关系。 从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。

int Depth (BiTree T ){ // 返回二叉树的深度 if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight); } return depthval;

不同的定义方法相应有不同的存储结构的建立算法 3、建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法

A(B( ,C( , )),D( , )) 以字符串的形式 根 左子树 右子树 定义一棵二叉树 例如: 以空白字符“ ”表示 空树 以字符串的形式 根 左子树 右子树 定义一棵二叉树 例如: 以空白字符“ ”表示 空树 以字符串“A ”表示 只含一个根结点的二叉树 A 以下列字符串表示 A A(B( ,C( , )),D( , )) B D C

Status CreateBiTree(BiTree &T) { scanf(&ch); if (ch==' ') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; // 生成根结点 CreateBiTree(T->lchild); // 构造左子树 CreateBiTree(T->rchild); // 构造右子树 } return OK; } // CreateBiTree

上页算法执行过程举例如下： A B C D A B C D T A B D ^ ^ ^ C ^ ^

6.5 线索二叉树 何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？

一、何谓线索二叉树？ 遍历二叉树的结果是， 求得结点的一个线性序列。 例如: A 先序序列: A B C D E F G H K B E 中序序列: B D C A H G K F E C F G D 后序序列: D C B H K G F E A H K

线索二叉树将为二叉树的遍历提供许多方便。 1．线索二叉树的定义 按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱结点；除最后一个结点外，每个结点有且仅有一个直接后继结点。但是，二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么，二叉树的存储结构中并没有反映出来，只能在对二叉树遍历的动态过程中得到这些信息。为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，利用二叉树的二叉链表存储结构中的那些空指针域来指示。这些指向直接前驱结点和指向直接后继结点的指针被称为线索（thread），加了线索的二叉树称为线索二叉树。 线索二叉树将为二叉树的遍历提供许多方便。

2．线索二叉树的结构 由于序列可由不同的遍历方法得到，因此，线索树有先序线索二叉树、中序线索二叉树和后序线索二叉树三种。把二叉树改造成线索二叉树的过程称为线索化。 对前图所示的二叉树进行线索化，得到先序线索二叉树、中序线索二叉树和后序线索二叉树分别如图(a)、(b)、(c)所示。图中实线表示指针，虚线表示线索。

包含 “线索” 的存储结构，称作 “线索链表” 指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索” A B C D E F G H K ^ B E ^ 包含 “线索” 的存储结构，称作 “线索链表” C ^ ^ D ^ 与其相应的二叉树，称作 “线索二叉树”

中序遍历序列：DBAEGCHFI t A B ^ C ^ D ^ ^ E F ^ G ^ ^ H ^ ^ I ^

那么，下面的问题是在存储中，如何区别某结点的指针域内存放的是指针还是线索？通常可以采用下面两种方法来实现。 ⑴为每个结点增设两个标志位域ltag和rtag，令： ltag＝ rtag＝ 每个标志位令其只占一个bit，这样就只需增加很少的存储空间。这样结点的结构为： ⑵不改变结点结构，仅在作为线索的地址前加一个负号，即负的地址表示线索，正的地址表示指针。

对线索链表中结点的约定： 在二叉链表的结点中增加两个标志域， 并作如下规定： 若该结点的左子树不空， 则Lchild域的指针指向其左子树， 且左标志域的值为“指针 Link”； 否则，Lchild域的指针指向其“前驱”， 且左标志的值为“线索 Thread” 。

若该结点的右子树不空， 则rchild域的指针指向其右子树， 且右标志域的值为 “指针 Link”； 否则，rchild域的指针指向其“后继”， 且右标志的值为“线索 Thread”。 如此定义的二叉树的存储结构称作“线索链表”。

typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 线索链表的类型描述： typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 typedef struct BiThrNod { TElemType data; struct BiThrNode *lchild, *rchild; // 左右指针 PointerThr LTag, RTag; // 左右标志 } BiThrNode, *BiThrTree;

二、线索链表的遍历算法: 由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。

例如: 对中序线索化链表的遍历算法 ※ 中序遍历的第一个结点 ？ ※ 在中序线索化链表中结点的后继 ？ 左子树上处于“最左下”（没有左子树）的结点。 ※ 在中序线索化链表中结点的后继 ？ 若无右子树，则为后继线索所指结点； 否则为对其右子树进行中序遍历时访问的第一个结点。

void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) { p = T->lchild; // p指向根结点 while (p != T) { // 空树或遍历结束时，p==T while (p->LTag==Link) p = p->lchild; // 第一个结点 while (p->RTag==Thread && p->rchild!=T) { p = p->rchild; Visit(p->data); // 访问后继结点 } p = p->rchild; // p进至其右子树根 } // InOrderTraverse_Thr

三、如何建立线索链表？ 建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚访问过的结点，即若指针p指向当前结点，则pre指向它的前驱，以便增设线索。 另外，在对一棵二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。

void InThreading(BiThrTree p) { if (p) { // 对以p为根的非空二叉树进行线索化 InThreading(p->lchild); // 左子树线索化 if (!p->lchild) // 建前驱线索 { p->LTag = Thread; p->lchild = pre; } if (!pre->rchild) // 建后继线索 { pre->RTag = Thread; pre->rchild = p; } pre = p; // 保持 pre 指向 p 的前驱 InThreading(p->rchild); // 右子树线索化 } // if } // InThreading

Status InOrderThreading(BiThrTree &Thrt, if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode)))) exit (OVERFLOW); Thrt->LTag = Link; Thrt->RTag =Thread; Thrt->rchild = Thrt; // 添加头结点 return OK; } // InOrderThreading … …

if (!T) Thrt->lchild = Thrt; else { Thrt->lchild = T; pre = Thrt; InThreading(T); pre->rchild = Thrt; // 处理最后一个结点 pre->RTag = Thread; Thrt->rchild = pre; }

6.6 树和森林 的表示方法

树的三种存储结构 一、双亲表示法 二、孩子链表表示法 三、树的二叉链表(孩子-兄弟） 存储表示法

一、双亲表示法: 由树的定义可以知道，树中的每个结点都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，其中包括结点本身的信息以及结点的双亲结点在数组中的序号，树的这种存储方法称为双亲表示法。其存储表示可描述为： #define MAXNODE <树中结点的最大个数> typedef struct { elemtype data; int parent; }NodeType; NodeType t[MAXNODE];

双亲表示法 实现：定义结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难

下图所示为树的双亲表示。图中用parent域的值为-1表示该结点无双亲结点，即该结点是一个根结点。 如何找孩子结点

树的双亲表示法对于实现Parent（t，x）操作和Root（x）操作很方便。但若求某结点的孩子结点，即实现Child（t，x，i）操作时，则需查询整个数组。此外，这种存储方式不能够反映各兄弟结点之间的关系，所以实现RightSibling（t，x）操作也比较困难。在实际中，如果需要实现这些操作，可在结点结构中增设存放第一个孩子的域和存放第一个右兄弟的域，就能较方便地实现上述操作了。

二、孩子链表表示法: ⑴多重链表法 由于树中每个结点都有零个或多个孩子结点，因此，可以令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。在这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法又常称为多重链表法。 在一棵树中，各结点的度数各异，因此结点的指针域个数的设置有两种方法： ①每个结点指针域的个数等于该结点的度数； ②每个结点指针域的个数等于树的度数。

⑵孩子链表表示法 孩子链表法是将树按如下图所示的形式存储。其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。 如何找双亲结点

在孩子表示法中查找双亲比较困难，查找孩子却十分方便，故适用于对孩子操作多的应用。 这种存储表示可描述为： #define MAXNODE <树中结点的最大个数> typedef struct ChildNode{ int childcode; struct ChildNode *nextchild; }; typedef struct { elemtype data; struct ChildNode *firstchild; }NodeType; NodeType t[MAXNODE];

三、双亲孩子表示法 双亲孩子表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。下图所示为采用这种方法的存储示意图。

四、树的二叉链表 (孩子-兄弟）存储表示法 这是一种常用的存储结构。其方法是这样的：在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。在这种存储结构下，树中结点的存储表示可描述为： typedef struct TreeNode { elemtype data; struct TreeNode *lchild; struct TreeNode *nextsibling; }NodeType,*CSTree;

特点 下图给出采用孩子兄弟表示法时的存储示意图。 从树的孩子兄弟表示法可以看到，如果设定一定规则，就可用二叉树结构表示树和森林，这样，对树的操作实现就可以借助二叉树存储，利用二叉树上的操作来实现。 特点 操作容易 破坏了树的层次

树、森林与二叉树的转换 树转换为二叉树 森林转换为二叉树 二叉树转换为树和森林

树与二叉树转换 对应 A B C D E 二叉树 A C B E D 树 A ^ ^ B C ^ D ^ ^ E ^ 存储 解释 A ^

1. 树转换为二叉树 将一棵树转换为二叉树的方法是： ⑴树中所有相邻兄弟之间加一条连线。 ⑵对树中的每个结点，只保留它与第一个孩子结点 之间的连线，删去它与其它孩子结点之间的连线。 ⑶以树的根结点为轴心，将整棵树顺时针转动一定 的角度，使之结构层次分明。 由上面的转换可以看出，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。

经过这种方法转换所对应的二叉树是惟一的，并且具有以下特点： ①此二叉树的根结点只有左子树，而没有右子树； ②转换生成的二叉树中各结点的左孩子是它在原来树中的最左边的孩子，右孩子是它在原来树中的下一个兄弟。

抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45° 将树转换成二叉树 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45° A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 树转换成的二叉树其右子树一定为空

由此，树的各种操作均可对应二叉树的操作来完成。 应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为： 左是孩子，右是兄弟。

2. 森林转换为二叉树 由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，森林同样可以用二叉树表示。 森林转换为二叉树的方法如下： ⑴将森林中的每棵树转换成相应的二叉树。 ⑵第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

这一方法可形式化描述为： 如果F＝{ T1，T2，…，Tm }是森林，则可按如下规则转换成一棵二叉树B＝（root，LB，RB）。 ⑴若F为空，即m＝0，则B为空树； ⑵若F非空，即m≠0，则B的根root即为森林中第一棵树的根Root(T1)；B的左子树LB是从T1中根结点的子树森林F1＝{ T11，T12，…，T1m1 }转换而成的二叉树；其右子树RB是从森林F’＝{ T2，T3，…，Tm }转换而成的二叉树。

以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J

经过这种方法转换所对应的二叉树是惟一的，并且它的第一棵树的子树森林转换成二叉树的左子树，剩余树的森林转换成二叉树的右子树。

3. 二叉树转换为树和森林 树和森林都可以转换为二叉树，这一转换过程是可逆的，即可以将一棵二叉树还原为树或森林，具体方法如下： 3. 二叉树转换为树和森林 树和森林都可以转换为二叉树，这一转换过程是可逆的，即可以将一棵二叉树还原为树或森林，具体方法如下： ⑴若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来； ⑵删去原二叉树中所有的双亲结点与右孩子结点的连线； ⑶整理由⑴、⑵两步所得到的树或森林，使之结构层次分明。

这一方法可形式化描述为： 如果B＝（root，LB，RB）是一棵二叉树，则可按如下规则转换成森林F＝{ T1，T2，…，Tm }。 ⑴若B为空，则F为空； ⑵若B非空，则森林中第一棵树T1的根ROOT（T1）即为B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成的森林F’＝{ T2，T3，…，Tm }是由B的右子树RB转换而成的森林。

加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来 将二叉树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构 A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I

抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J

下图给出一棵二叉树还原为森林的过程示意。

6.7 树和森林的遍历

一、树的遍历 二、森林的遍历 三、树的遍历的应用

一、树的遍历 遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列 常用方法(树的遍历可有三条搜索路径): 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点

A B E F C D G 1．先根遍历 先根遍历的定义为： ⑴访问根结点； ⑵按照从左到右的顺序先根遍历根结点的每一棵子树。 按照树的先根遍历的定义，对上图所示的树进行先根遍历，得到的结果序列为： A B E F C D G

E F B C G D A 2．后根遍历 后根遍历的定义为： ⑴按照从左到右的顺序后根遍历根结点的每一棵子树。 ⑵访问根结点； 按照树的后根遍历的定义，对下图所示的树进行后根遍历，得到的结果序列为： E F B C G D A

先序遍历： A B E F I G C D H J K L N O M 后序遍历： E I F G B C J K N O L M H D 层次遍历： A B C D E F G H I J K L M N O

二、森林的遍历 即：依次从左至右对森林中的每一棵树进行先根遍历。 1．先序遍历 先序遍历的定义为：若森林不空，则 ⑴访问森林中第一棵树的根结点； ⑵先序遍历第一棵树的根结点的子树； ⑶先序遍历去掉第一棵树后的子森林。 即：依次从左至右对森林中的每一棵树进行先根遍历。

对于下图所示的森林进行先序遍历，得到的结果序列为： A B C D E F G H J I K

即：依次从左至右对森林中的每一棵树进行中根遍历。 2. 中序遍历 中序遍历的定义为：若森林不空，则 ⑴中序遍历第一棵树的根结点的子树； ⑵访问森林中第一棵树的根结点； ⑶中序遍历去掉第一棵树后的子森林。 即：依次从左至右对森林中的每一棵树进行中根遍历。

对于下图所示的森林进行中序遍历，得到的结果序列为： B A D E F C J H K I G

(3)层次遍历 若森林非空，则可以按照下述规则遍历： ①对第一棵树从根结点起按层从左到右依次访问结点； ②按层访问森林中除第一棵树外剩余的树构成的森林。

树的遍历和二叉树遍历的对应关系 ？ 树 森林 二叉树 先根遍历 先序遍历 先序遍历 后根遍历 中序遍历 中序遍历

6.8 哈 夫 曼 树 与 哈 夫 曼 编 码 最优树的定义 如何构造最优树 前缀编码

1．赫夫曼树的基本概念 最优二叉树，也称赫夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。 路径 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径。 A B C

路径长度 路径上的分支数目称为路径长度。 (a) (b) (c) 树的路径长度 从树根到所有叶结点的路径长度之和称为树的路径长度。 (a)的路径长度是2+2+2+2=8 (b)的路径长度是3+3+1+2=9 (c)的路径长度是1+2+3+3=9 完全二叉树就是这种路径长度最短的二叉树。

结点的带权路径长度 如果二叉树中的叶结点都具有一定的权值，则从该结点到树根之间的路径长度与结点上权的乘积称为结点的带权路径长度。 树的带权路径长度 设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为： WPL＝ Wk·Lk 其中Wk为第k个叶结点的权值，Lk 为第k个叶结点的路径长度。

在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个叶结点，设其权值分别为1，3，5，7，我们可以构造出形状不同的多个二叉树。下图给出了其中5个不同形状的二叉树，其带权路径长度分别为： （a）WPL＝1×2＋3×2＋5×2＋7×2＝32 （b）WPL＝1×3＋3×3＋5×2＋7×1＝29 （c）WPL＝1×2＋3×3＋5×3＋7×1＝33 （d）WPL＝7×3＋5×3＋3×2＋1×1＝43 （e）WPL＝7×1＋5×2＋3×3＋1×3＝29

有4个叶子结点A、B、C、D，分别带权7、5、2、4。 赫夫曼树 假设有n个权值{w1，w2，…，wn}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树或赫夫曼树。 有4个叶子结点A、B、C、D，分别带权7、5、2、4。 具有不同带权路径长度的二叉树

例如，要编制一个将百分制转换为五级分制的程序。显然，此程序很简单，只要利用条件语句便可完成。如： if (a<60) b=”bad”; else if (a<70) b=”pass” else if (a<80) b=”general” else if (a<90) b=”good” else b=”excellent”; 这个判定过程可以下图所示的判定树来表示。

如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如下表所示： 分数 0－59 60－69 70－79 80－89 90－100 比例数 0.05 0.15 0.40 0.30 0.10 则80％以上的数据需进行三次或三次以上的比较才能得出结果。假定以5，15，40，30和10为权构造一棵有五个叶子结点的赫夫曼树，则可得到如图 (b)所示的判定过程，它可使大部分的数据经过较少的比较次数得出结果。

但由于每个判定框都有两次比较，将这两次比较分开，得到如图(c)所示的判定树，按此判定树可写出相应的程序。假设有10000个输入数据，若按图(a)的判定过程进行操作，则总共需进行31500次比较；而若按图(c)的判定过程进行操作，则总共仅需进行22000次比较。 10000*(0.05*1+0.15*2+0.40*3+0.30*4+0.10*4)=31500 10000*(0.05*3+0.15*3+0.40*2+0.30*2+0.10*2)=22000

如何找到带权路径长度最小的二叉树（即赫夫曼树）呢？根据赫夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。赫夫曼（Haffman）依据这一特点提出了一种方法，这种方法的基本思想是： （1）由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}； （2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和； （3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中； （4）重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的赫夫曼树。

赫夫曼算法说明： (1)在选取两棵根结点权值最小的二叉树时，出现权值相同的情况时，可以在相同权值的二叉树中选取一棵； (2)当两棵根结点的权值最小的二叉树组成新的二叉树的左子树和右子树时，谁左谁右没有规定； (3)在赫夫曼树中，权值越大的叶子结点离根越近，这也是WPL最小的实际根据和赫夫曼树的应用依据； (4)在赫夫曼树中没有度为1的结点，根据二叉树性质n0＝n2+1，可以推得n个叶子结点的赫夫曼树共有2n-1个结点。

下图给出前面提到的叶结点权值集合为W＝{1，3，5，7}的赫夫曼树的构造过程。可以计算出其带权路径长度为29，由此可见，对于同一组给定叶结点所构造的赫夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。

2．赫夫曼树的构造算法 在构造赫夫曼树时，可以设置一个结构数组HuffNode保存赫夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的赫夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，数组元素的结构形式如下： 其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的赫夫曼树中，可通过parent域的值来确定。初始时parent的值为-1，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是-1了。

例 w={5, 29, 7, 8, 14, 23, 3, 11} 29 14 8 7 15 11 3 5 19 23 42 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 11 3 5 8 19 23 42 29 14 7 15 58 8 7 15 14 29 23 3 5 11 11 3 5 8 19 14 29 23 7 15 11 3 5 8 19 23 42 29 14 7 15 58 100 11 3 5 8 19 29 23 14 7 15

例如: 已知权值 W={ 5, 6, 2, 9, 7 } 5 6 2 9 7 6 9 7 7 5 2 9 7 13 5 2 6 7

9 7 13 5 2 6 7 29 1 13 16 1 1 6 7 9 7 1 00 01 10 5 2 110 111

假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造赫夫曼树的过程。 第一步：以这8个权值作为根结点的权值构造具有8棵树的森林。 5 29 7 8 14 23 3 11

第二步：从中选择两个根的权值最小的树3，5作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树添加进去 8 29 7 8 14 23 11 3 5

第三步：重复第二步过程，直到森林中只有一棵树为止 选择7，8 8 15 29 14 23 11 3 5 7 8

29 14 23 7 8 15 8 3 5 19 11

选择8，11 选择14，15 选择19，23 29 29 42 19 14 15 23 7 8 11 8 3 5

选择29，29 42 58 23 19 29 29 11 8 14 15 3 5 7 8

WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271 选择42，58 100 42 58 23 19 29 29 11 8 14 15 3 5 7 8

下面给出赫夫曼树的构造算法。 #define MAXVALUE 10000 //定义最大权值 #define MAXLEAF 30 //定义赫夫曼树中叶子结点个数 #define MAXNODE MAXLEAF*2-1 typedef struct { int weight; int parent; int lchild; int rchild; }HNodeType;

HNodeType *HaffmanTree( ) { HNodeType HuffNode[MAXNODE]; int i,j,m1,m2,x1,x2,n; scanf(“%d”,&n); //输入叶子结点个数 for (i=0;i<2*n-1;i++) //数组HuffNode[ ]初始化 { HuffNode[i].weight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; } for (i=0;i<n;i++) //输入n个叶子结点的权值 scanf(“%d”,&HuffNode[i].weight);

for (i=0;i<n-1;i++) //构造赫夫曼树 { m1=m2=MAXVALUE; x1=x2=0; for (j=0;j<n+i;j++) { if(HuffNode[j].weight<m1 && HuffNode[j].parent==-1) { m2=m1; x2=x1; m1=HuffNode[j].weight; x1=j; } else if(HuffNode[j].weight<m2 && HuffNode[j].parent==-1) { m2=HuffNode[j].weight; x2=j; } } //将找出的两棵子树合并为一棵子树 HuffNode[x1].parent=n+i; HuffNode[x2].parent=n+i; HuffNode[n+i].weight= HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[n+i].lchild=x1; HuffNode[n+i].rchild=x2; } return HuffNode;

3．赫夫曼树在编码问题中的应用 前缀编码 （1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样； 在数据通讯中，经常需要将传送的每个字符(文字)转换成由二进制字符0，1组成的二进制串(进行二进制编码)，我们称之为编码。在设计编码时需要遵守两个原则： （1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样； （2）发送的二进制编码尽可能地短。 下面介绍两种编码的方式:

1. 等长编码 这种编码方式的特点是每个字符的编码长度相同(编码长度就是每个编码所含的二进制位数)。例如,假设要传送的电文为ABACCDA，电文中只含有A，B，C，D四种字符，若这四种字符采用右表 (a)所示的编码，则电文的代码为000010000100100111000，长度为21。在传送电文时,我们总是希望传送时间尽可能短,这就要求电文代码尽可能短，显然，这种编码方案产生的电文代码不够短。右表 (b)所示为另一种编码方案，用此编码对上述电文进行编码所建立的代码为00010010101100，长度为14。在这种编码方案中，四种字符的编码均为两位，是一种等长编码。当接收方接收到这段电文后,将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。 字符 编码 A 000 B 010 C 100 D 111 (a) 字符 编码 A 00 B 01 C 10 D 11 (b)

2. 不等长编码 在传送电文时，为了使其二进制位数尽可能地少，如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码。 字符 编码 A B 110 C 10 D 111 (c) 例如，可以为A,B,C,D四个字符分别分配0,00,1,01，并可将电文ABACCDA用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，还是1个B、2个A，或是2个B，即译码不唯一，因此这种编码方法不可使用。如当字符A，B，C，D采用右表(c)所示的编码时，上述电文的代码为0110010101110，长度仅为13。

在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性，例如，右表(d)所示的编码方案，字符A是字符B的编码010的前缀部分，这样对于代码串0101001，既是AAC的代码，也是ABA和BDA的代码，因此，这样的编码不能保证译码的唯一性，称为具有二义性的译码。 字符 编码 A 01 B 010 C 001 D 10 (d)

前缀编码：如果要设计长短不等的字符编码，那么必须保证任何一个字符的编码都不是另一个字符的编码的前缀。 按前缀编码翻译电文，一定能够惟一地被翻译成原文。

赫夫曼树可用于构造使电文的编码总长最短的编码方案。具体做法如下：设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现的次数或频率集合为{w1，w2，…，wn}，以d1，d2，…，dn作为叶结点，w1，w2，…，wn作为它们的权值，构造一棵赫夫曼树，规定赫夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为赫夫曼编码。 在赫夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用赫夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。

W={1，3，5，7} 权值越大编码长度越短，权值越小编码长度越长。

下面讨论实现赫夫曼编码的算法。实现赫夫曼编码的算法可分为两大部分： （1）构造赫夫曼树； （2）在赫夫曼树上求叶结点的编码。 求赫夫曼编码，实质上就是在已建立的赫夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了赫夫曼树的一个分支，从而得到一位赫夫曼码值，由于一个字符的赫夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码是所求编码的低位码，后得到的分支代码是所求编码的高位码。我们可以设置一结构数组HuffCode用来存放各字符的赫夫曼编码信息，数组元素的结构如下： 其中，分量bit为一维数组，用来保存字符的赫夫曼编码，start表示该编码在数组bit中的开始位置。所以，对于第i个字符，它的赫夫曼编码存放在HuffCode[i].bit中的从HuffCode[i].start到n的分量上。

赫夫曼编码算法描述如下。 #define MAXBIT 10 /*定义赫夫曼编码的最大长度*/ typedef struct { int bit[MAXBIT]; int start; }HCodeType; void HaffmanCode ( ) { HNodeType HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF],cd; int i,j, c,p; HuffNode=HuffmanTree ( ); /*建立赫夫曼树*/

for (i=0;i<n;i++) /*求每个叶子结点的赫夫曼编码*/ { cd.start=n-1; c=i; p=HuffNode[c].parent; while(p!=0) /*由叶结点向上直到树根*/ { if (HuffNode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=HuffNode[c].parent; } for (j=cd.start+1;j<n;j++) //保存求出的每个叶结点的赫夫曼编码和编码的起始位 HuffCode[i].bit[j]=cd.bit[j]; HuffCode[i].start=cd.start;} for (i=0;i<n;i++) /*输出每个叶子结点的赫夫曼编码*/ { for (j=HuffCode[i].start+1;j<n;j++) printf(“%ld”,HuffCode[i].bit[j]); printf(“\n”); } }

利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。

　1. 熟练掌握二叉树的结构特性，了解相应的证明方法。 　2. 熟悉二叉树的各种存储结构的特点及适用范围。 　3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。

　　4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。

　5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。 　6. 学会编写实现树的各种操作的算法。 　7. 了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。