,数据结构,
第六章 树和二叉树
（重点）
第六章 树和二叉树第 2页第六章 树和二叉树
内容 树、二叉树、森林的概念和性质，树与二叉树的转换，树形结构的存储，遍历，哈夫曼树的概念及应用。
要求 通过学习和上机，深刻理解树形结构的递归特性，为应用它解决实际问题奠定理论基础并获得实践经验。理解并准确叙述 树,二叉树,
森林 及其有关概念并熟悉它们的基本性质，熟悉树形结构的 存储结构 和 中序线索二叉树,熟悉树的 遍历方法,尤其是二叉树的 前序,中序 和 后序遍历的递归与应用，知道树形结构的若干应用。
第六章 树和二叉树第 3页
重点
1,树、二叉树的概念和性质
2,树结构的存储
3,树和二叉树的遍历算法以及树的前序、
中序和后序遍历算法
难点
1,树形结构的存储方法
2,中序线索树
3,二叉树遍历的非递归算法
4,树的应用第六章 树和二叉树第六章 树和二叉树第 4页树的逻辑结构 ——它定义一类重要的 非线性结构 。
树结构在计算机科学的很多领域都得到了广泛的应用。
树结构可应用于诸如
编译程序中表示源程序的语法结构
数据库系统中的信息组织
文件目录
电路分析
社会各个组织和管理机构
家谱
书的章节编目
军队编制树型结构是结点之间有分支、层次关系的结构，它非常类似于自然界中的树。树型结构在客观世界中大量存在。
树的结构定义第六章 树和二叉树第 5页定义 1 树 Tree=(D,R)是一种 层次数据结构,其中 D是具有相同特性的数据元素（称为树结点）的有限集合,R是定义在 D上的二元关系。在这种关系中,有且仅有一个特定的无前趋的结点（称为树的根，记作 root），其余的每一个结点有且仅有一个直接前趋。
注,树的这种结构对 每一个结点的后继不加限制,任何一个结点都可以有 0至多个后继结点 。
定义 2 （ 树的递归定义）树是 n(n≥1)个结点的有限集合，
其中
(1) 有且仅有一个特定的称之为根（ root）的结点；
(2) 其余的结点可分为 m(m ≥0)个互不相交的集合 T1,T2,…
,Tm，而每一个集合本身又是一棵树，并且称为根的子树（
sub tree）。
为了讨论方便，有时也将结点数为 0的空集合也看成树，并称之为空树。
树的结构定义第六章 树和二叉树第 6页树的表示示例
A
B
C
A
C DB
E F
－
/+
a? e f
b －
c d
A
仅有根结点的树一般树
A
C DB
E F H J
K L
G I
M
二叉树树的结点：一个个的记录树的枝或边：指向其他结点的指针
树 的 表 示第六章 树和二叉树第 7页非树表示示例不是树，因为它没有一个 根 结点不是树，因为其中的一个结点有 两个前趋 结点不是树，因为它是不相交的两棵树的集合。它是 森林
树 的 表 示第六章 树和二叉树第 8页树的其它三种表示方法
文氏图表示法用集合的嵌套即包含关系来表示
广义表表示法用嵌套括号表示。
根作为由子树森林组成的表的名字写在表的左边
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
A
E
K L
F
B H
M
I
J
D
G
C
树 的 表 示第六章 树和二叉树第 9页
凹入表示法类似于书的编目，即分成章节、小节，分别缩进表示
A
B
E
K
L
F
C
G
D
H
M
I
J
树 的 表 示第六章 树和二叉树第 10页以如图所示的一棵树为范例结点 （ node） 树中的的一个独立单元。它包括一个信息项和若干个指示其他树结点的位置信息。结点的信息项可包含一个关键字和其他的数据项。常用圆圈内的一个字母或数字表示该结点的信息项或关键字，并用来标识该结点，如结点 A,结点
B。
根 （ root） 树唯一无前趋（前件）的结点，如结点 A。 有时也用根结点标记整棵树，称其为树 A。
结点的度 （ degree of node） 结点拥有的 子树（或后件）数 。
如结点 A的度为 3,B的度为 2,C的度为 1,D的度为 3,E的度为 2
,F的度为 0，等等。
A
C DB
E F H J
K L
G I
M
树 的 基 本 术 语树的度 （ degree of tree）树内各 结点度的 最大值,如示例树的度为 3。
第六章 树和二叉树第 11页叶结点 （ leaf node） 或称终端结点，
系指树中度为 0（或没有后件）的结点。
如 K,L,G,M,I,J都是叶结点。
双亲 （ parent） 树中各结点的直接前趋称为该结点的双亲。如结点 A是结点 D的双亲，结点 H是结点 M的双亲等等。
祖先 （ ancestor） 从根结点到该结点所经分支上的所有结点。
如结点 K的祖先分别为 A,B,E。
分支结点 （ branch node） 亦称非终端结点，系指度不为 0的结点，包括根结点。
孩子 （ children） 一个 树结点的直接后继 均是该树结点的孩子
。如结点 B,C,D均是结点 A的孩子。
兄弟 （ Sibling） 同一个双亲的孩子之间互称兄弟。如结点 E,F
互为兄弟,H,I,J互为兄弟，等等。
树 的 基 本 术 语
A
C DB
E F H J
K L
G I
M
第六章 树和二叉树第 12页子孙 （ descendant） 以某结点为根的子树中的任一结点都称为该结点的子孙。比如，除根结点 A之外的所有结点都是 A的子孙树枝 （ branch） 亦称为树边，系指连接两个结点的有向线段。
一般是由父结点指向子结点。为了画图方便，一般将箭头方向省略树的深度 （ depth of tree） 亦称树的高度，系指树中各结点层次的最大值。如树 A的深度为 4。
堂兄弟 （ brother-in-law） 其双亲在同一层的结点。如结点 E,G和 H均为堂兄弟。
结点的层次 （ level of node） 结点所位于的层数（以根结点为第一层）。如结点 B的层次为 2。树中任一结点的层次等于它的双亲结点的层次加 1。
结点的枝长 （ length of branch） 亦称该结点的路径长度，系指由根结点至该结点所经过的树枝数,它应等于该结点的层次数减 1
。如结点 B的枝长为 1。
树 的 基 本 术 语
A
C DB
E F H J
K L
G I
M
第六章 树和二叉树第 13页有序树 （ ordered tree） 规定了树中所有结点的每一棵子树或后件的次序（从左至右，且不能互换）的树。比如，以下两棵树是互不相同的有序树。
完全树 （ Complete tree） 亦称正则树，系指在 n阶树中，它的每一个结点，要末有 n个后件，要末一个后件也没有。比如，下列三棵树无序树 （ unorded tree） 凡不是有序树的树。
A
B C
A
C B
中,(a),(b)均为完全树，而 (c)则不是完全树。
(a) (b) (c)
树 的 基 本 术 语第六章 树和二叉树第 14页定义 3 m(m ≥0)棵互不相交树的集合称为 森林 。森林与树的概念非常相近，比如将范例树中的根结点 A删去，该树就分解成由原树的三棵子树 B,C,D组成的森林。反之，可以用一个新的树根结点将若干棵互不相交的树 (即森林 )组合成一棵新树。
定义 4 任何一棵树是一个二元组 Tree=(root,F)，其中
root是数据元素，称做树的根结点； F是 m(m≥0)棵树的森林,F=(T1,T2,…,Tm)，其中 Ti=(ri,Fi)称做树根 root的第 i
棵子树；当 m≠0时，在树根和其子树森林之间存在下列关系
RT={<root,ri>|1≤i≤m,m>0}
此定义有助于得到森林和树与二叉树之间转换的递归定义。
树 的 基 本 术 语
A
C DB
E F H J
K L
G I
M
第六章 树和二叉树第 15页
(1) 初始化操作 Initiate(T)
置 T为空树。
(2)要求根结点函数 Root(T)或 Root(x)
返回树 T的根结点或结点 x所在的树的根结点。若 T是空树或 x
不在任何一棵树上，则返回空函数值 NULL。
(3)求双亲结点函数 Parent(T,x)
返回树 T中的根结点或结点 x不在树 T中，则返回空函数值
NULL。
(4)求孩子结点函数 Child(T,x,i)
返回树 T中结点 x的第 i个孩子结点。若结点 x是树 T中的叶结点或无第 i个孩子结点，或者结点 x不在树 T中，则返回空函数值 NULL。
(5)求右兄弟结点函数 Right_Sibling (T,x)
返回树 T中结点 x右边的兄弟结点。若结点 x是其双亲的最右边的孩子结点或结点 x不在树 T中，则返回空函数值 NULL。
树 的 基 本 操 作第六章 树和二叉树第 16页
(6) 建树函数 CreateTree(x,F)
生成一棵以 x结点为根，以森林 F为子树森林的树。
(7) 插入子树操作 InsChild(y,i,x)
置以结点 x为根的树 为结点 y的第 i棵子树。若原树中无结点 y，
或结点 y的子树个数小于 i-1，则为空操作。
(8) 删除子树操作 DelChild(x,i)
删除结点 x的第 i棵子树。若无结点 x或结点 x的子树个数小于 i，
则为空操作。
(9) 树的遍历操作 Traverse(T)
按某个次序依次访问树中各个结点，并使每个结点只被访问一次。
(10) 清除树的结构操作 Clear(T)
将树置为空树。
注,树的抽象数据类型可随需要而设定。
树 的 基 本 操 作第六章 树和二叉树第 17页二叉树是树型结构的另一个 重要类型,许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此，二叉树显得特别重要。
二叉树的定义定义 （二叉树的递归定义）二叉树 (binary tree)是结点的一个有限集合，这个集合或是空集，或是由一个根结点及两棵分别称为根结点的左子树和右子树的互不相交的二叉树组成。
二叉树的定义与基本操作第六章 树和二叉树第 18页由于二叉树递归定义中的两棵子树亦都是二叉树，则它们亦可为空树。故二叉树可有下列五种基本形态：
(a) (b) (c) (d) (e)
(a) 空二叉树
(b) 仅有根结点的二叉树
(c) 有根结点及左子树，右子树为空的二叉树
(d) 有根结点及左、右子树的二叉树
(e) 有根结点及右子树，左子树为空的二叉树二叉树中，每个结点最多只能有 两棵 子树,并且有左、右之分 。
两棵不同的二叉树 一棵普通树
A
B
C D
E
A
B
C
E
D
A
B
DC
E
二叉树的五种基本形态第六章 树和二叉树第 19页二叉树示例深度为 4 深度为 5
A
B C
D E
G H
F
A
B
C
D
E
二叉树的定义与基本操作第六章 树和二叉树第 20页二叉树的基本操作与树的基本操作相类似，不同的是在求孩子结点、兄弟结点以及插入、删除等操作时，均有左、右之分。
(1) Initiate(BT)
初始化操作，置 BT为空树。
(2) Root(BT) 或 Root(x)
求根结点函数
(3) Parent(BT,x)
求双亲结点函数。
(4) LChild(BT,x) 和 RChild(BT,x)
求孩子结点函数。分别返回二叉树 BT中结点 x的左孩子结点和右孩子结点。若结点 x是二叉树 BT的叶结点或 x不在二叉树 BT中，
则返回空函数值 NULL。
(5) LSibling(BT,x) 和 RSibling(BT,x)
求兄弟结点函数。分别返回二叉树 BT中结点 x的左兄弟结点和右兄弟结点。若结点 x是根结点或 x不在 BT中或 x是其双亲的左 /右子树根，则返回空函数值 NULL。
第六章 树和二叉树第 21页二叉树的基本操作
(6) Create (x,LBT,RBT)
建树操作。生成一棵以结点 x为根，二叉树 LBT和 RBT分别为左、右子树的二叉树。
(7) InsLChild(BT,y,x) 和 InsRChild(BT,y,x)
插入子树操作。将以结点 x为根且右子树为空的二叉树分别置为二叉树 BT中结点 y的左子树和右子树。若结点 y有左子树 /右子树
，则插入后是结点 x的右子树。
(8) DelLChild(BT,x) 和 DelRChild(BT,x)
删除子树操作。分别删除二叉树 BT中以结点 x为根的左子树或右子树。若结点 x无左子树或右子树，则为空操作。
(9) Traverse (BT)
树的遍历操作。按某个次序依次访问二叉树 BT中各个结点，
并使每个结点只被访问一次。
(10) Clear(BT)
清除二叉树的结构操作。
注,与树类似，用户可根据操作需要设定二叉树的抽象数据类型。
第六章 树和二叉树第 22页
二叉树的性质二叉树与一般树既有联系，又有区别，它是有序树的一个特例
。用于一般树上的术语也可用于二叉树。二叉树有若干重要性质。
性质 1 在二叉树的第 i层上至多有 2i-1个结点 (i≥1)。
[证 ] 用归纳法。
i=1，只有一个根结点。 2i-1=20=1。正确。
设命题对 j成立，即有第 j层上至多有 2j-1个结点。由于二叉树每个结点的度至多为 2，故在最大结点数的 2倍，即
2j-1.2=2j=2(j+1)-1。故命题对 j+1亦成立。证毕。
性质 2 深度为 k的二叉树至多有 2k-1个结点 (k ≥1)。
[证 ] 由性质 1，深度为 k的二叉树的最大结点数为
（第 i层上的最大结点数）
第六章 树和二叉树第 23页性质 3 二叉树 T的叶结点数等于度为 2的结点数加 1。
[证 ] 若记二叉树 T的终端结点数为 n0，度为 2的结点数为
n2，则欲证 n0=n2+1。
设 n1为二叉树 T中度为 1的结点数,n为二叉树 T中的总结点数。由于二叉树中所有结点的度均小于或等于 2，故有
n=n0+n1+n2 (1)
再看二叉树的分支数。除根结点外，其余结点都有一个分支进入。设 B为分支总数，则
n=B+1 (2)
由于这些分支是由度为 1或 2的结点射出的，所以又有
B=n1+2n2 (3)
由 (2)和 (3)知
n=n1+2n2+1 (4)
由 (1)和 (4)可得
n0=n2+1.
二叉树的性质第六章 树和二叉树第 24页定义 5 一棵深度为 k且具有 2k-1个结点的二叉树称为满二叉树。
注,完全二叉树的另一种定义：深度为 k的完全二叉树，其 k-1
层是一棵满二叉树，最后第 k层结点都尽量排在靠左的位置上
（即第 k层的所有叶子结点占据树的最左边的位置）。
二叉树的性质定义 6 深度为 k有 n个结点的二叉树，当且仅当该二叉树的 n个结点与深度为 k的满二叉树中编号从 1至 n的结点位置一一对应时，则称为 亚满二叉树或完全二叉树 。
示例 1
2 3
4 5
8 9 10 11
6 7
12 13 14 15
(a) 满二叉树
1
2 3
4 5
8 9 10
6 7
(b)完全二叉树第六章 树和二叉树第 25页对完全二叉树的几点说明：
(1) 度小于 2的结点（包括度等于 0的叶结点）只可能在最下两个层次上出现；
(2) 对任一结点，其左子树的层次 ≥右子树的层次。以下两个二叉树都非完全二叉树
(3) 有的书中定义只有度为 0或 2的二叉树称为完全二叉树。则上页 (b)就为非完全二叉树；但若去掉结点 10或增加结点 11，则为完全二叉树；
(4) 满二叉树亦是完全二叉树，但反之不然。
1
2 3
4 5
6 7
1
2 3
4 5 6
二叉树的性质第六章 树和二叉树第 26页
[证 ] 对于满二叉树,n=2k-1，或 n+1=2k，得 k=log2(n+1),
由于 k是整数，故?log2n?+1
对于完全二叉树，根据性质 2和完全二叉树的定义知
2k-1-1<n≤2k-1
其中 2k-1-1与 2k-1分别表示深度为 k-1与 k的最大结点数。于是
2k-1 ≤ n<2k
或有
k-1≤log2n<k
由于 k是整数，故
k=?log2n?+1
示例 如右图，对于 n=8,9,10,···,14的完全二叉树，以及 n=15的满二叉树，均有
k=?log2n?+1 =3+1=4.
1
2 3
4 5
8 9 10 11
6 7
12
性质 4 具有 n个结点的满二叉树或完全二叉树的深度为?log2n?+1.
符号含义：
x? 表示不大于 x的最大整数。
表示不小于 x的最小整数。
例如,5.8
5.8? = 5
= 6
x
8.5
第六章 树和二叉树第 27页性质 5 如果对一棵有 n个结点的 完全二叉树 （其深度为?log2n?+1 ）的结点按层序编号（从第 1层到第
log2n?+1层，每层从左到右），则对任一结点 i(1 ≤
i≤n)，有
(1) 如果 i=1，则结点 i是二叉树的根，无双亲；
如果 i>1，则其双亲 Parent(i)是? i/2?
(2) 如果 2 *i>n。则结点 i无左孩子（结点 i为叶子结点）；如果 2i ≤n，则其左孩子 LChild(i)是结点 2i;
(3) 如果 2i+1>n，则结点 i无右孩子（但 i不一定是叶结点）； 如果 2i+1 ≤n，则其右孩子 RChild(i)是结点 2i+1。
二叉树的性质第六章 树和二叉树第 28页
[证 ] 用归纳法证明 (2),(3)，由 (2),(3)再导出 (1).
记 j为层次。
j=1：按完全二叉树定义，其左、右孩子应为结点 2,3。
若 2·1>n，则无左孩子；
若 2·1+1>n，则无右孩子。
设 j=i时结论成立，即有左孩子为结点 2i(2i≤n)，右孩子为结点 2i+1(2i+1 ≤n),现欲证 j=i+1时结论亦成立，即有左孩子为结点 2(i+1) (2(i+1) ≤n).
根据完全二叉树的特点，与结点 i+1的左孩子相邻的前两个结点分别是结点 i的左、右孩子。由归纳法假定,i的左孩子是 2i
，右孩子是 2i+1，因此,i+1的左孩子应为 2i+1+1=2(i+1)，如
2(i+1)>n，则说明 i+1无左孩子；而 i+1的右孩子为
2i+1+3=2(i+1)+1 (2(i+1)+1 ≤n),因此 j=i+1时 (2),(3)成立。
对任一结点 i(i ≤i ≤n)，除 i=1即结点外，若 i=偶数，则必是左孩子，其双亲是 i/2=? i/2?；若 i=奇数，则必是右孩子，其双亲是 i-i/2=? i/2?,故 (1)成立。
二叉树的性质第六章 树和二叉树第 29页下图展开了完全二叉树中结点 i和 i+1与其左、右孩子之间的关系
LChild(i) RChild(i) LChild(i+1) RChild(i+1)
结点 i和 i+1在 同一层次 （ i必为偶数）
[i/2]
i+1i
2i 2i+1 2i+2 2i+3
结点 i和 i+1不 在同一层次 （结点 i必在上一层最后,i+1必为此层最左； i必为奇数）
i
2i 2i+1
LChild(i) RChild(i)
i+1
2i+2 2i+3
LChild(i+1)
RChild(i+1)
第六章 树和二叉树第 30页二叉树的顺序存储结构可使用一组连续的存储单元 (向量，即一维数组 )来存储二叉树的数据元素。必须把二叉树中的所有结点安排成一个适当的线性序列,使得结点在这个序列中的相互位置能够反映出结点之间的逻辑关系。
示例
1
2 3
6 74 5
8 109 11 12
1 2 3 4 5 6 7 8 9 10 11 12
2i
↑
i
↑
2i
↑
2i+1
bt(1:12)
二叉树的存储结构第六章 树和二叉树第 31页非完全二叉树
1
2 3
0 04 5
0 60 7
1 2 3 4 5 0 0 0 0 6 7
bt(1:11)
(0表示不存在此结点 )
一般二叉树也必须以完全二叉树的形式来确定。
无结点的补 0，造成了存储空间的浪费。
1 0 2 3 0 0 0 0 0 4
bt(1:15)
0 0 0 0 0
1
0 2
0 30 0
0 00 0 0 0 40
最坏情况
二叉树的存储结构第六章 树和二叉树第 32页由于二叉树的 度数小,在所有存储方法中最主要、最方便的一种是二叉树的 标准存储形式，或称为二重链存储形式 。
一个结点 k由一个数据元素和分别指向其左、右子树的两个指针域组成当有必要时，可在每一个结点中再加上一个指向其父结点的指针域 parent。这就是二叉树的扩充标准存储形式注,利用上述两种结点结构所得二叉树的存储结构分别称为 二叉链表 和 三叉链表 。
lchild data rchild
k
lchild data parent
k
rchild
二叉树的链式存储结构第六章 树和二叉树第 33页
typedef struct BiNode{
datatype data;
BiNode *lchild,*rchild;
} BiNode,*BiTree; A
B
C
D
单支树的二叉链表的存储结构
A
B
C D
E F
G
A ^
B ^
C ^
D ^^
head
A ^
B
C ^^ D
E^ F ^^
G ^^
head
一般二叉链表的存储结构
二叉树的链式存储结构示例第六章 树和二叉树第 34页
A
B
C D
E F
G
一般三叉链表的存储结构
A ^
B
C ^^ D
E^ F ^^
G ^^
head
^
注,在含有 n个结点的二叉链表中有 n+1个空链域 。这是因为
n个结点总共有 n-1个边；
n个结点总共有 2n个链域（包括左、右链域）；
每个边需使用一个链域；
故应有 n+1个空链域。
应设法有效地利用这些空闲着的链域。
二叉树的链式存储结构第六章 树和二叉树第 35页问题的提出以上采用标准形式（左、右链接）存储二叉树时,n
个结点的 2n个链域中有 n+1个空链域，故链域的存储空间利用率 ≈1/2。但对于一个度为 d(d≥2)的树,n个结点总共需要 nd个链域，但除根结点外，有 n-1个结点被某个链域指示
，空链域的个数为
nd-(n-1)=n(d-1)+1,
故 d度树的链域利用率为
d越小，链域利用率越高，故 2度树存储空间利用率最高。如果能将一般树转化成一棵二叉树，那么不但存储代价小，很多对树的操作也会简单得多。
).2(11 ddndn
有序树和二叉树间的转化第六章 树和二叉树第 36页有序树和二叉树间的转化规则一棵有序树可以唯一地转化为根结点没有右子树的二叉树。反之，一棵根结点没有右子树的二叉树也能转化为唯一的一棵有序树。
有序树转化成其对应二叉树的规则
(1) 二叉树具有与有序树相同的结点；
(2) 如果在有序树中,n是 m的最左儿子，那么在二叉树中,n将是 m的左儿子；
(3) 如果在有序树中,n是 m的右边一个同胞兄弟
，那么在二叉树中 n将是 m的右儿子。
下面用图示形式来展现如何把一棵有序树转化成相应的二叉树。
有序树和二叉树间的转化第六章 树和二叉树第 37页有序树转化为二叉树的图示化方法步骤：
1,在树的所有同胞兄弟之间添加一水平连线；
2,删去父结点到除最左孩子之外的所有其它孩子之间的树枝；
3,再将新添加的水平连线按顺时针方向旋转 450。
显然，由树转换成的二叉树，其根结点的右子树总是空的，
因为原树根结点是没有兄弟的。
A
B
E G H
D
I J
C
F
K
A
B
E
FK
C
DH
I
J
G
步骤 3A
B
E G H
D
I J
C
F
K
XX
XXX?
步骤 2
步骤 1 A
B
E G H
D
I J
C
F
K
加连线
有序树和二叉树间的转化第六章 树和二叉树第 38页设已设定
typedef struct BiNode{
datatype data;
BiNode *lchild,*rchild;
} BiNode,*BiNodePtr,*BiTree;
Specification,binary_tree
Elements,树由结点和有向树边组成，结点的类型为 datatype，每一个结点具有一个唯一的键值 data。
Structure,二叉树或为空，或由一个根结点及其两棵互不相交的左
、右二叉树构成。二叉树是一个层次结构，即在三元组表示形式
L=（ P,R,V）中,P是 BiTree的有限子集,R是 P上的一个层次关系，除根以外的每一个结点都有且仅有一个前趋。 V是由
BiTree到 datatype的函数。
Operation,binary_tree包括下列基本操作，这些操作除了
Create外，都假定二叉树已存在。
二叉树的抽象数据类型第六章 树和二叉树第 39页
(1) Create ( BiTree t )；
生成一棵空二叉树。
(2) BiNodePtr root ( BiTree t )；
若树为空，则返回空函数值 NULL，否则，返回树 t的根结点位置。
(3) BiNodePtr leftchild ( BiNodePtr p,BiTree t );
设 p是 t中的一个结点。若结点 p有左子树，则返回其左子树根结点位置，否则，返回空函数值 NULL。
(4) BiNodePtr rightchild ( BiNodePtr p,BiTree t );
设 p是 t中的一个结点。若结点 p有右子树，则返回其右子树根结点位置，否则，返回空函数值 NULL。
(5) BiNodePtr parent ( BiNodePtr p,BiTree t);
设 p是 t中的一个结点。若结点 p是非根结点，则返回 p的父结点位置，否则，返回空函数值 NULL。
二叉树的抽象数据类型第六章 树和二叉树第 40页
(6) datatype retrieve( BiNodePtr p,BiTree t);
设 p是 t中的一个结点。返回位置为 p的结点的数据元素值。
(7) updata(BiNodePtr p,datatype d,BiTree &t);
设 p是 t中的一个结点。 用新的数据元素值 d取代位置为 p的结点的原先数据元素值 。
(8) BiNodePtr find ( datatype d,BiTree t);
设树中各结点的数据元素值各不相同。若树 t中存在一个数据元素值为 d的结点，则返回该结点的位置，否则，返回空函数值。
(9) Insert ( datatype d,BiTree &t );
在树 t中插入一个数据值为 d的新结点，如在树中已经存在这样一个结点，则不执行插入操作。
二叉树的抽象数据类型第六章 树和二叉树第 41页
(10) deletesub (BiNodePtr &p,BiTree &t );
在树 t中删去以 p为根的整棵子树。如在树 t中不存在这样的结点，则不执行该操作。
(11) Status empty (BiTree t );
若树 t为空则返回 true，否则，返回 false。
(12) preorder(BiNodePtr p,BiTree t )；
对树 t进行前序遍历。
(13) postorder (BiNodePtr p,BiTree t )；
对树 t进行后序遍历。
二叉树的抽象数据类型第六章 树和二叉树第 42页遍历二叉树的概念按一定规律和次序，依照某条搜索路径巡访二叉树中的每一结点,且只访问一次 。在访问每个结点时，可对结点中的数据进行处理，比如打印结点的有关信息，或者做其它指定工作等。
由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因此需要寻找一种规律，以一种合适的方法，使能获得二叉树中各结点信息的 一个线性排列 。
在对二叉树的一些操作中，遍历是一种基本的操作，并且有很多实际的应用。
二叉树的遍历第六章 树和二叉树第 43页已知二叉树是由三个基本单元组成,根结点,左子树 和右子树 。若能依次遍历这三部分，便是遍历了整个二叉树。
D
RL
L(Left)：遍历左子树
D(Directory)：访问根结点
R(Right)：遍历右子树则，总共有 6种遍历方法
DLR,LDR,LRD,DRL,RDL,RLD
二叉树的遍历常用的遍历二叉树的方法（限定,先左后右 ）
先 (根 )序遍历,DLR
中 (根 )序遍历,LDR
后 (根 )序遍历,LRD
第六章 树和二叉树第 44页
D
RL
先 (根 )序遍历,DLR
访问根结点 -> 先序遍历左子树 ->先序遍历右子树中 (根 )序遍历,LDR
中序遍历左子树 -> 访问根结点 -> ->中序遍历右子树后 (根 )序遍历,LRD
后序遍历左子树 -> 后序遍历左子树 -> 访问根结点
A
B
D E
C
F G
H I
先序遍历,ABDHECFGI
中序遍历,DHBEAFCIG
后序遍历,HDEBFIGCA
根
二叉树的遍历第六章 树和二叉树第 45页算法思想,若二叉树为空，则遍历结束，否则首先遍历左子树，接着访问根结点，最后遍历右子树。
算法描述
inorder( BiTree bt )
{ //中序遍历根结点指针为 bt的二叉树
if( bt≠NULL )
{ inorder( bt->lchild );
visit( bt ); //访问根结点 (打印等 )
inorder( bt->rchild );
}
} //inorder
二叉树遍历的递归算法第六章 树和二叉树第 46页栈是实现递归的最常用的结构，所以对于递归定义的二叉树遍历算法，最自然的实现方法是利用一个栈来记下尚待遍历的结点或子树，以备以后访问。
按中序遍历二叉树时，每当遇到一个结点，就将它压入栈中，然后遍历左子树，遍历完这个结点的左子树后，从栈顶弹出这个结点并访问之，然后按照它的
rchild指示的地址，再去遍历这个结点的右子树。
下面先给出用类 C编写的二叉树中序遍历的非递归算法。
二叉树遍历的非递归算法
1) 中序遍历二叉树第六章 树和二叉树第 47页
inorder(btree bt)
//中序遍历 bt所指二叉树,S为存储二叉树结点指针的工作栈
{ InitStack(s); Push(s,bt);
while( !Empty(s))
{ while( GetTop(s) ≠ NULL )
Push(S,GetTop(s)->lchild );
p = Pop(s);
if( !Empty(s))
{ visite(GetTop(s)); //printf(s->data)
P=Pop(s);
Push(s,p->rchild);
}
}
} //inorder 算 法 6.2
二叉树遍历的非递归算法第六章 树和二叉树第 48页如果把关于中序遍历的非递归算法中那个
printf（表示访问根结点并输出有关信息的语句
）移至 p进栈的前面，则可实现二叉树的先序遍历。按先序遍历二叉树时，每当遇到一个结点
，首先访问它，然后将指向该结点的指针压入栈中，再去遍历它的左子树。当整个左子树遍历完毕，就将这个结点从栈中弹出，再去遍历它的右子树。
2) 先序遍历二叉树
二叉树遍历的非递归算法第六章 树和二叉树第 49页问题的提出在对二叉树的一些操作中，遍历是一种基本的操作，并且有很多实际的应用。
遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列
，得到二叉树中结点的先序序列或中序序列或后序序列。这实际上是对一个 非线性结构进行线性化操作,使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个（直接）前趋和（直接
）后继。
当用二叉链表作为二叉树的存储结构时，因为每个结点中只有两个指向其左、右孩子结点的指针域，所以从任一结点出发只能直接找到该结点的左、右孩子信息，而不能直接得到该结点在任一序列中的前趋和后继信息。 某结点在线性序列（先根序列、中根序列或后根序列）中的前趋的后继信息，只有在遍历的动态过程中才能得到。
线索二叉树的基本思想第六章 树和二叉树第 50页在标准形式存储的 n个结点的二叉树中，共有 2n个指针域，除根结点以外的 n-1个结点，每一个结点被一个指针单元指示，故尚有 n+1个指针域的值是 NULL。
存储空间的得用率不够充分。
设想能否得用这些空闲的指针链域来存放结点的前驱的后继的信息。
比如，一棵中序线索二叉树（或称中序穿线树）
就是得用标准形式的二叉树结构中原指针域为 NULL的单元，指向本结点的中序前驱或中序后继，这样，当进行中序遍历二叉树时就不必使用栈了。
线索二叉树的基本思想第六章 树和二叉树第 51页一棵中序线索二叉树
● 实践表示二叉树的树边
● 带箭头的虚线表示线索
● 中序遍历序列 BGDAECF
上图所示为 中序全线索化二叉树
A
B
D
G
C
E F
NULL NULL
线索二叉树的基本思想第六章 树和二叉树第 52页规定：若结点有左（右）子树；则该结点的 lchild(rchild)域指示其左（右）孩子；否则，令 lchild(rchild)域指示其前驱（后继）。为此，
特增加两个标志域 。
线索二叉树的结点结构其中
0,lchild域指示结点的左孩子
1,lchild域指示结点的前驱
0,rchild域指示结点的右孩子
1,rchild域指示结点的后继表示
typedef enum{Link,Thread} PointTag;
typedef struct BiTrNode{
ElemType data;
struct BiTrNode *lchild,*rchild;
PointTag LTag,Rtag;
} *BiTrNodePtr,*BiTrTree;
lchild ltag data rtag rchild
Ltag=
rtag=
线索二叉树的结点结构第六章 树和二叉树第 53页
● 线索链表以上述 加上两个标志域结点结构 作为二叉树的存储结构所构成的二叉链表
● 线索指向结点前驱和后继的指针
●线索二叉树 (threaded binary tree)
加上线索的二叉树
● 二叉树的线索化对二叉树以 某种次序 遍历使其变为线索二叉树的过程
● 遍历线索二叉树在线索二叉树上进行遍历，只要找到序列中的第一个结点，然后依次找结点后继，直至其后继为空时为止。
线索二叉树的几个术语第六章 树和二叉树第 54页以中序线索二叉树 为例示例,表达式 a+b? (c－ d) － (e/f) 的中序线索二叉树示意如下实线：表示树边，实为指向左、右子树的指针虚线：指向前驱的后继的线索中序遍历结果,a+b? c－ d － e/f （中缀表达式）
先序,－ +a?b－ cd/ef （前缀表达式）
后序,abcd －?+ef/ － （后缀表达式）
线索二叉树及其存储结构
－
/
e f
NULL
NULL
＋
a?
b －
c d
中序线索二叉树第六章 树和二叉树第 55页在二叉树的中序线索链表上添加一个 头结点,
线索二叉树及其存储结构
0 1
0 － 0
0 + 0 0 / 0
^ 1 a 1 0? 0 1 e 1 1 f 1 ^
1 b 1 0 － 0
1 c 1 1 d 1
参见图 6.11
lchild指向二叉树的根结点
rchild指向中序遍历访问的最后一个结点令二叉树中序序列中的第一个结点的 lchild
域指针指向头结点令二叉树中序序列中的 最后 一个结点的 rchild
域指针指向头结点第六章 树和二叉树第 56页以中序线索二叉树为例，假定二叉树已按中序线索化，如上页中序线索链表的结构示意图所示。
求结点 n的后继
[分析 ] 设给定结点 n，求其后继结点，送入 x。
(1) 若给定结点 n无右子树 (n->rtag==1),则 n->rchild即为 n的后继
(2) 若给定结点 n有右子树 (n->rtag==0),则其右子树的最左下结点即为其后继 (其 lchild指向结点 n)。
inorder_next (BiTrNodePtr n,BiTrNodePtr &x)
//给定结点 n，求其后继结点，送入 x
{ t = n->rchild;
if( n->rtag==0 )
while( t->ltag==0 ) t = t->lchild;
x=t
} //inorder_next
时间复杂度：在 (1)时，为 O(1)；在 (2)时，为 O(k),k为 n的右子树的最大层次。
在线索二叉树中寻找结点的前趋与后继第六章 树和二叉树第 57页求结点的前驱
[分析 ] 设给定结点 n，求其前趋结点，送入 x。
(1) 若给定结点 n无左子树 (n->ltag==1),则 n->lchild即为 n的前趋
(2) 若给定结点 n有左子树 (n->ltag==0),则其左子树的最后右下结点即为其前驱。
算法描述
inorder_prior(BiTrNodePtr n,BiTrNodePtr &x )
//给定结点 n，求其前趋结点，送入 x
{ t=n->lchild;
if( n->ltag==0 )
while( t->rtag == 0 ) t= t->rchild;
x=t
} //inorder_prior 时间复杂度：同上。
结论,求中序线索二叉树中某结点的后继结点和前驱结点均无困难。
思考,对于先序、后序线索二叉树，求结点的后继结点和前驱结点其困难程度如何？
在线索二叉树中寻找结点的前趋与后继第六章 树和二叉树第 58页
在线索二叉树中寻找结点的前趋与后继
－
/
e f
＋
a?
b －
c d 先序线索二叉树
NULL
找结点的后继结点无困难；
找有左子树结点的前驱结点有困难
（要是无左子树，则 lc hil d 指向其前驱）
为此，须添加指向双亲的指针先序,－ +a?b－ cd/ef
第六章 树和二叉树第 59页二叉树求结点的后继结点及前驱结点的困难程度，
列表如下：
排序类型 无线索表示 线索表示先序
( 1) 找叶结点的后继结点有困难；
( 2) 找所有结点的前驱结点有困难
( 1) 找结点的后继结点无困难；
( 2) 找有些结点的前驱结点有困难中序
( 1) 找无右子树结点的后继结点有困难；
( 2) 找无左子树结点的前驱结点有困难找任何结点的后继结点和前趋结点均无困难后序
( 1) 找所有结点的后继结点有困难；
( 2) 找叶结点的前驱结点有困难
( 1) 找结点的前趋结点无困难；
( 2) 找有右子树结点的后继结点有困难
在线索二叉树中寻找结点的前趋与后继第六章 树和二叉树第 60页
inorder_thlinked(BiTrNodePtr thrt )
//已知 thrt为指向中序双向线索链表中头结点的指针，中序遍历该二叉树
{ p=thrt->lchild；
//指针 p初始化，指向非空二叉树的根结点，二叉树为空时 p=thrt
while(p≠thrt )
{ while( p->ltag==0 ) p=p->lchild; //子树
visite(p)； //访问左子树为空的结点
while (p->rtag==1) && (p->rchild ≠thrt)) //线索
{ p=p->rchild; visite(p); //访问后继结点
}；
p=p->rchild;
}
} //inorder_thinked 算法 6.4
线索二叉树的遍历算法第六章 树和二叉树第 61页二叉树线索化的含义对二叉树以某种次序（比如按中序）遍历使其变成线索二叉树的过程叫做二叉树的线索化。
二叉树线索化的过程是,将二叉树链表每一个结点中原指针域值为 NULL的指针改为指向该结点的前趋结点或后继结点的线索 。然而，
寻找某结点的前驱结点或后继结点的信息只有在对二叉树进行遍历时才能得到,因此线索化的过程即为在对二叉树进行遍历的过程中修改
NULL指针的过程。
二叉树的线索化第六章 树和二叉树第 62页链表生成。对于右二叉树
A
B
D
G
C
E F
设已生成如下之二叉树链表结构
A
∧ B C
D ∧ ∧ E ∧ ∧ F ∧
∧ G ∧
bt
线索二叉树的遍历算法中序遍历生成中序线索链表第六章 树和二叉树第 63页
crt-inthlinked (BiTrNodePtr &thrt,BiTrNodePtr bt )
//已知 bt指向二叉树的根结点，中序遍历生成中序线索链表，
thrt为指向头结点的指针
{ thrt = new(BiTrNode); thrt->ltag=0; thrt->rtag=1;
thrt->rchild=thrt; //建头结点
if( bt==NULL ) thrt->lchild=thrt // 空树
else
{ thrt->lchild=bt; pre=thrt;
inthread(bt); //中序遍历线索化
pre->rchild=thrt;
pre->rtag=1; //最后一个结点线索化
thrt->rchild=pre;
thrt->rtag=1;
}
} //crt_inthlinked 算法 6.5
线索二叉树的遍历算法第六章 树和二叉树第 64页
[分析 ] 这实际上是一个递归的二叉树中序遍历过程，在遍历的过程中建立具有 NULL指针的结点的前驱线索与后继线索 (全线索化 )
算法描述
inthread(BiTrNodePtr p)
//中序线索化以 p为根指针的二叉树
{ if( p==NULL ) return;
inthread (p->lchild)； //左子树线索化
if( p->lchild==NULL )
{ p->ltag=1; p->lchild=pre } //建立前驱线索
if( pre->rchild==NULL )
{ pre->rtag=1; pre->rchild=p }； //建立后继线索
pre=p； //保持 pre指向刚刚访问的结点
inthread(p->rchild)； //右子树线索化
} //inthread 算法 6.6
线索二叉树的遍历算法中序线索化以 p为根指针的二叉树第六章 树和二叉树第 65页一般二叉树的插入、删除操作较为简单，只需解决所插入子树的位置问题，并调整有关结点的链域。然而，若欲在一棵线索二叉树上插入或删除一棵子树，则都会破坏线索。因此，
在修改结点指向孩子结点的指针时,还必须修复线索 。
示例 下面是一棵后序（全）线索二叉树（图中点划线表示省略部分）
A
B
D
G
C
E F
线索二叉树的插入、删除操作第六章 树和二叉树第 66页后序线索二叉树 的插入操作示例 ——AddLChild(BT,y,x)
功能,将以 x为根的子树 （后序线索二叉树）插入到 y所在的二叉树 BT（后序线索二树）中，成为 y结点的左子树 。
约定,(1) x原没有右子树 ； (2) 若 y原有左子树，则该左子树在插入操作之后成为 x的右子树。
算法思想,分四种情况来逐个讨论指针变化的情形，以确保在插入一棵子树之后仍是一棵 后序 线索二叉树。
这四种情况分别为：
(1) y结点是叶结点（终端结点），其左、右链域均为线索；
(2) y结点有左子树而无右子树；
(3) y结点无左子树而有右子树；
(4) y结点既有左子树亦有右子树。
整个算法可以综合以上四种情况而写成。
线索二叉树的插入、删除操作第六章 树和二叉树第 67页情况 1,y结点是叶结点（终端结点），
其左、右链域均为线索 。
现象,在插入以 x为根的子树后，
对后序序列而言，恰好在 y结点和它的前驱结点 pre之间插入了 x的左子树 XL的后序序列和 x结点，使插入后以 y为根的后序序列成为 pre→XL→x→y.
设 rt为指向后序线索链表头结点的指针,函数 first(p)返回以 p为根的二叉树后序序列中的第一个结点的指针 。
链域指针修改状况：
1) p=first(x->lchild); //p指向 x的左子树 XL的后序序列中的第一个结点
2) p->lchild=y->lchild; //XL的前驱指向 y的前驱
3) if( y->lchild->rtag==1 ) y->lchild->rchild=p;
//若 y的前驱有后继线索，则改为指向 XL
4) y->ltag=0; y->lchild=x; //x成为 y的左孩子
5) x->rtag=1; x->rchild=y; //y成为 x的后继
E F
E F
p
pre
pre y
y
x
1)
2)
3)
4)
5)
XL
第六章 树和二叉树第 68页情况 2,y结点有左子树而无右子树现象,按此插入操作的定义，在插入以 x为根的子树作为 y的左子树之前，令 y的左子树为 x的右子树
。则在插入之后，后序遍历 y的左子树应得到的后序序列为 (pre)→XL→YL→x→(y),G
D
D
pre y
y
x
q
G
pre
XL
p1)
1) p=first(x->lchild); //p指向 XL的后序序列中的第一个结点链域指针修改状况：
q 2)
2) q=first(y->lchild); //q指向 YL的后序序列中的第一个结点
3)
3) p->lchild=q->lchild; //XL的前驱指向 YL的前驱
4)
4) if( q->lchild->rtag==1) q->lchild->rchild=p;
//若 YL的前驱有后继线索，则改为指向 XL
5)5) q->lchild=x->lchild; //YL的前驱改为 x的左孩子
6)
6) if( x->lchild->rtag==1) x->lchild->rchild=q;
//若 x的左孩子有后继线索，则改为指向 YL
7)
7) if( y->lchild->rtag==1) y->lchild->rchild=x;
//若 y的左孩子有后继线索，则改为指向 x
9)
8)
8) x->rtag=0; x->rchild=y->lchild; //y的左子树成为 x的右子树
9) y->lchild=x; //x成为 y的左孩子第六章 树和二叉树第 69页情况 3,y结点无左子树而有右子树现象,后序遍历插入之后的以 y为根的子树所得后序序列为 (pre)→XL→x→YR→y,
链域指针修改状况：
1) p=first(x->lchild);
2) q=first(y->rchild);
//p和 q分别指向 XL和 YR的后序序列中的第一个结点
3) p->lchild=q->lchild;
//XL的前驱指向 YR的前驱
4) if( q->lchild->rtag==1)
q->lchild->rchild=p;
//若 YR的前驱有后继线索，
则改为指向 XL
5) q->lchild=x; //x是 YR的前驱
6) x->rchild=q; x->rtag=1; //x的后继是 YR
7) y->ltag=0; y->lchild=x; //x是 y的左孩子
B
D
G
y
pre
q
B
D
G
y
pre
qXL
x
p
3)4)
1)
6)
5)
2)
7)
第六章 树和二叉树第 70页情况 4,y结点既有左子树又有右子树现象,后序遍历插入之后的以 y为根的子树所得后序序列为 (pre)→XL→YL → x→YR→y,
链域指针修改状况：
1) p=first(x->lchild);
2) q=first(y->lchild);
3) r=first(y->rchild);
4) p->lchild=q->lchild;
5) if( q->lchild->rtag==1)
q->lchild->rchild=p;
6) q->lchild=x->lchild;
7) if( x->lchild->rtag==1)
x->lchild->rchild=q;
8) if( y->lchild->rtag==1)
y->lchild->rchild=x;
9) x->rtag=0;
x->rchild=y->lchild;
10) y->lchild=x;
11) r->lchild=x;
B
D
G
y
pre
q
B
D
G
XL
x
4)
5)
p1)
q2)
A
C
E F
r
A
C
E F
y
10)
11)
r
3)
pre
6)
7)
9)
第六章 树和二叉树第 71页注 1,时间 复杂度 O(n),n为插入后的线索化树上的结点数。这是因为从上述对指针变化的描述可见，其时间主要消耗在寻找 y的子树和 x的左树中最左下的叶子结点，在最坏的情况下几乎要遍历整棵树。
注 2,上述耗时最坏情况下和对二叉树进行线索化的时间相当。因此，有时可以先作单纯的插入，即修改孩子指针，然后对插入后的整棵二叉树重新进行线索化。
注 3,关于在线索二叉树上的删除操作，亦同样有修改结点指针的同时需修复线索的问题。
注 4,本课程的重点在于怎样进行二叉树的线索化（以中序线索化为示例），以及如何在一棵线索二叉树中寻找结点的前驱结点与后继结点。
第六章 树和二叉树第 72页
1、双亲链表表示法有多种形式的存储来表示 树 (一般树 )。下面介绍树的三种常用表示法。
在树中，每个结点的双亲是唯一的。利用这一性质，可在存储结点信息的同时，为每个结点附设一个指向其双亲的指针 parent，
就可唯一地表示任何一棵树。
尽管可以用动态链表来实现这种表示法，然而用静态链表更为方便。可使用向量（数组）来存储一棵树的信息。
#define maxnode 1000 //结点数目的最大值
typedef struct tnode{
datatype data; //数据域
int parent; //游标域，指示双亲结点在数组中的下标
} tnode;
typedef struct tree{
tnode nodes[maxnode] ;
int n; //结点数
} ptree;
树 的 存 储 结 构第六章 树和二叉树第 73页示例 1 下图展示一棵树及其双亲表示的静态链表存储结构优点,存储简单，存储密度大，找双亲结点操作
Parent(T,x)容易，亦不难利用反复调用 Parent操作，寻找结点 x的根结点。
缺点,求结点的孩子结点或其他后代结点可能要遍历整个向量。
注,Parent(T,x) 操作可以在常量时间内实现。
A
B C
D E
G IH
F
1
2 3
4 5 6
987
A 0
B 1
C 1
D 2
E 2
F 3
G
H
I
5
5
5
1
2
3
4
5
6
7
8
9
结点序号 data parent
图 6.15 树的双亲链表表示法示例
树 的 存 储 结 构第六章 树和二叉树第 74页为了减少求指定结点的孩子结点时的遍历时间，可以规定孩子结点的下标大于双亲结点的下标，兄弟结点之间的下标从左向右递增。在这样的规定下，求结点 T[i]
的长子结点（最左直接后代结点）的算法描述如下：
int firstchild( ptree t; int i )
//求双亲链表 T中结点 T[i]的长子结点，返回它的位置
{ for( j=i+1; j<= maxnode; j++ )
if( t[j].parent==i )
return(j); //找到 T(i)的长子结点 T[j]
return(0) //未找到
} //firstchild
树 的 存 储 结 构第六章 树和二叉树第 75页
2、孩子链表表示法由于树中每个结点的孩子个数没有限制，若采用多重链表来表示结点及孩子之间的关系时，每个结点内要设置多少个指向其孩子的指针是难以确定的。
设采用多重链表，即每个结点有多个指针域，其中每个指针域指向一棵子树的根结点。
(1) 固定链域格式设树的度为 d，则结点形式为此时，多重链表中的结点是同构的。 由于树中可能有很多结点的度均小于 d，所以链表中有很多空链域 。在一棵有 n个结点且度为 k的树中，其空指针域的数目是
kn-(n-1)=n(k-1)+1
这将造成极大的空间浪费。
data child1 child2 · · · childd
树 的 存 储 结 构第六章 树和二叉树第 76页
(2) 非固定链域格式每个结点按其实际的孩子数设置指针，并在结点内设置度数域
degree，以指出该结点所包含的指针数，结点形式为其中 d为该结点的度。此时，多重链表中的结点是不同构的，各结点不等长。这虽然节省了存储空间,但是给操作带来不便。
(3) 向量 ——链表格式为树中的每一个结点建立一个孩子链表。为了便于查找，可将树中各结点的孩子链表的头结点存放在一个向量中。
degree child1 child2 · · · childddata
树 的 存 储 结 构第六章 树和二叉树第 77页
typedef struct CTNode{
int child;
struct CTNode *Next;
} *ChildPtr;
typedef struct{
ElemType data;
ChildPtr firstchild;
} CTBox;
typedef struct{
CTBox nodes[Max_Node];
int n,r;
}
A
B C
D E
G IH
F
1
2 3
4 5 6
987
树的孩子链表表示法示例
树 的 存 储 结 构
A
B
C
D ∧
E
F ∧
G
H
I
∧
∧
∧
1
2
3
4
5
6
7
8
9
data headptr Child next
2
4
3 ∧
5 ∧
∧6
7 8 9 ∧
优点,存储简单，节省空间，找孩子结点容易。
缺点,求双亲结点困难，
不适用于求
Parent(T,x)操作。
第六章 树和二叉树第 78页
(4) 双亲孩子链表表示法把双亲链表表示法和孩子链表表示法相结合，即将双亲向量和孩子表头指针向量合在一起。
示例 2 承上例树的双亲孩子链表表示法示例
A
B
C
D ∧
E
F ∧
G
H
I
∧
∧
∧
1
2
3
4
5
6
7
8
9
data parent headptr Child next
2
4
6
7
3 ∧
5 ∧
8 9 ∧
0
1
1
2
2
3
5
5
5
树 的 存 储 结 构第六章 树和二叉树第 79页
3,孩子兄弟链表表示法 亦称二叉树表示法或二叉链表示法。
A
B C
D E
G IH
F
1
2 3
4 5 6
987
图 6.15 树的双亲链表表示法示例以二叉树表作树的存储结构。在存储结点信息的同时，附加两个分别指向该结点的第一个孩子和下一个兄弟的指针域
fch (firstchild)和 nsib (next sibling).
typedef struct tnodetp{
elemtype data;
tnodetp *fch,*nsib;
} *forest;
A ∧
B
D∧
C ∧
F∧ ∧
H∧
E ∧
G∧ I∧ ∧
树 的 存 储 结 构第六章 树和二叉树第 80页优点,它和二叉树的二叉链表表示完全一样，
因此可以利用二叉树的算法来实现对树的各种操作
，比如易于实现找孩子结点等的操作。若为每个结点增设一个 parent域，则同样能方便地实现
Parent(T,x)操作。
树 的 存 储 结 构第六章 树和二叉树第 81页结点大小可变
data degree child1 · · · childd
树的存储结构总结：
树 的 存 储 结 构
1、双亲链表表示方法
2、孩子链表表示方法
3、孩子兄弟链表表示方法
1）固定链域格式
2）非固定链域格式
3）向量 -链表格式
4）双亲孩子链表表示法
A 0
B 1
C 1
D 2
E 2
F 3
G
H
I
5
5
5
1
2
3
4
5
6
7
8
9
结点序号 data parent
结点大小固定
data child1 child2 · · · childd
A
B
C
D ∧
E
F ∧
G
H
I
∧
∧
∧
1
2
3
4
5
6
7
8
9
data headptr Child next
2
4
3 ∧
5 ∧
∧6
7 8 9 ∧
A ∧
B
D∧
C ∧
F∧ ∧
H∧
E ∧
G∧ I∧ ∧
A
B
C
D ∧
E
F ∧
G
H
I
∧
∧
∧
1
2
3
4
5
6
7
8
9
data parent headptr Child
next
2
4
6
7
3 ∧
5 ∧
8 9 ∧
0
1
1
2
2
3
5
5
5
第六章 树和二叉树第 82页在树或森林与二叉树之间有一个自然的一一对应关系 。任何一个森林或一棵树可唯一地对应到一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。
1）树与二叉树的转换树中每个结点可能有多个孩子，但二叉树中每个结点至多只能有两个孩子。要把树转换为二叉树，就必须找到一种结点与结点之间至多用两个量说明的关系。
找关系,树中的每个结点最多只有一个最左边的孩子（长子）和一个右邻的兄弟，这就是我们要找的关系。按照这种关系很自然地就能将一棵树转换成与其相对应的二叉树 。
树,森林与二叉树的转换第六章 树和二叉树第 83页树转换成其对应二叉树的方法：
(1) 在所有兄弟结点之间加一连线；
(2) 对每一个结点，除了保留其长子结点的连线外，去掉该结点与其他孩子结点的连线；
(3) 按顺时针方向将树旋转 450。
示例 3
树与二叉树的对应关系示例
A
B C E
D
(1)
A
B C E
D
(2) A
B C E
D
(3) A
B
C
D E
树,森林与二叉树的转换第六章 树和二叉树第 84页注,任何一棵和树对应的二叉树，其右子树必为空示例 4 将下述一棵树转换成其对应的二叉树
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
AB
E
F G
C
D
H I J
(1)
(3)(2)
树,森林与二叉树的转换第六章 树和二叉树第 85页从树的二叉链表表示的定义可知，任何一棵和树相对应的二叉树，
由于树根没有兄弟，故当将要转换为其对应二叉树后，该二叉树的根结点的右子树必为空。 对于森林，若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟,则同样可以导出森林和二叉树之间的对应关系示例 5 将下述森林转换成其对应的二叉树：
图 6.19 森林与二叉树的对应关系示例
2）森林与二叉树的对应关系
A
B C D F
E G
H
J
I A
B
G
H
I
C
D
E
F
J
树,森林与二叉树的转换
J
A
B C D
E
F
G
H I
=>
第六章 树和二叉树第 86页二叉树转换成其对应的树或森林的方法：
(1) 若结点 x是其双亲 y的左孩子,则把 x的右孩子、右孩子的右孩子,…
都与 y用连线连起来；
(2) 去掉所有双亲到右孩子的连线。
示例 6
A
B C
E F
E G
H
J
I
A
B
G
H
I
C
D
E
F
J
A
B
G
H
I
C
D
E
F
J
树,森林与二叉树的转换
A
B
G
H
I
C
D
E
F
J
第六章 树和二叉树第 87页
3）森林与二叉树相互转换的形式定义森林转换成二叉树设 F={T1,T2,···,Tm}表示由树 T1,T2,···,Tm组成的森林，则与森林 F
相对应的二叉树 B(root,LB,RB)
(1) 若 F为空 (m=0)，则 B(F)为空的二叉树；
(2) 若 F非空 (m>0)，则 B(F)的根 root就是 F中第一棵树 T1的根
Root(T1)； B(F)的左子树 LB是 B(T11,T12,···,T1m1)，其中 T11,T12,··,T1m1
是 Root(T1)的子树森林； B(F)的右子树 RB是 B(T2,T3,···,Tm)。
由于上述定义中 B(T11,T12,···,T1m1)和 B(T2,T3,··,Tm)分别是森林
{T11,T12,···,T1m1}和 {T2,T3,··,Tm}所对应的二叉树，故可 递归 地应用 (1)
和 (2)来将其转换为二叉树。
树,森林与二叉树的转换第六章 树和二叉树第 88页二叉树转换成森林设 B=(root,LB,RB)是一棵二叉树，则可按如下规则转换成森林 F={T1,T2,···,Tm}：
(1) 若 B为空，则 F亦为空；
(2) 若 B非空，则 F中第一棵树 T1的根 Root(T1)即为二叉树 B
的根 root； T1为根结点的子树森林 F1是由 B的左子树 LB转换而成的森林 ； F中除 T1之外其余树组成的森林 F`=(T2,T3,···,Tm)是 由 B
的右子树 RB转换而成的森林。
这亦是一个递归定义。
由上述森林转换成二叉树以及二叉树转换成森林的递归定义，可以写出相应的递归算法。同时,森林和树的操作可通过将其转换成二叉树，籍助于二叉树的操作来实现 。
树,森林与二叉树的转换第六章 树和二叉树第 89页
1）树的遍历先根遍历树 T
若树 T非空，则
(1) 访问树 T的根结点 R；
(2) 依次先根遍历根 R的每棵子树 T1,T2,···,Tm。
对上述的树进行先根遍历，可得该树的先根序列为
ABCDE
在 二叉树 中，可以有先根（序）遍历、中根（序）遍历后根（序）遍历，而在树和森林中，由于一个结点可以有两棵以上的子树,不便讨论它们的中根次序遍历,因为无法明确给出根与这些子女间的次序。但仍然可以研究先根次序和后根次序的遍历。
A
C
D
EB
树和森林的遍历第六章 树和二叉树第 90页后根遍历树 T
若树 T非空，则
(1) 依次后根遍历根 R的每颗子树 T1,T2,···,Tm； (2) 访问根结点。
对上述的树进行后根遍历,可得该树的后根序列为 BDCEA
先根遍历树 T,ABCDE
后根遍历树 T,BDCEA
先根 遍历二叉树 T`,ABCDE
中根 遍历二叉树 T`,BDCEA
A
C
D
EB
A
B
C
D E
转换成对应的二叉树
树和森林的遍历值得注意的是,先根遍历一棵树，恰好等价于先根遍历该树所对应的二叉树；后根遍历一棵树，恰好等价于中根遍历该树所对应的二叉树。
树的遍历与二叉树遍历之间的关系第六章 树和二叉树第 91页按照森林和树相互递归的定义，可以推出森林的两种遍历方法。以如下一次森林为示例来进行说明。
先根遍历森林若森林非空，则
(1) 访问森林中第一棵树的根结点；
(2) 先根遍历第一棵树中根结点的子树森林 （递归） ；
(3) 先根遍历除第一棵树外其他树构成的森林 （递归） 。
对上述的森林进行先根遍历，可得该森林的先根序列为？
A
B C D F
E G
H
J
I
2）森林的遍历
树和森林的遍历
A B C D E F G H I J
问题,后根遍历森林任何描述？后根序列？ B C D A F E H J I G
第六章 树和二叉树第 92页后根遍历森林若森林非空，则
(1) 后根遍历森林中第一棵树的根结点的子树森林；
(2) 访问第一棵树的根结点；
(3) 后根遍历除第一棵树外其它树构成的森林。
简言之,先根遍历森林是从左到右依次按先根次序遍历森林中的每一棵树，后根遍历森林则是从左到右依次按后根次序遍历森林中的每一棵树 。
与遍历树相类似，先根遍历森林等同于先根遍历森林所对应的二叉树；后根遍历森林等同于中根遍历该森林所对应的二叉树。
这主要是由森林到二叉树的转换方法所决定的，因为森林中第一棵树对应到二叉树的根和左子树，其它树构成的森林对应到二叉树的右子树。
树和森林的遍历第六章 树和二叉树第 93页示例 7 设有如下森林 F E
F G H
I
A
B
D
C
1,将它转换成对应的二叉树；
2,写出该森林按先根遍历和后根遍历所得的先根序列和后根序列
。
解：
J
E
F G H
I
A
B
D
C
J
A
B
F
I
C
D
E
G
J H先根序列 ABCDEFIGJH
后根序列 BDCAIFJGHE
树和森林的遍历第六章 树和二叉树第 94页结论：两个结论结论一,先根遍历森林是从左到右依次按先根效率遍历森林中的每一棵树，后根遍历森林则是从左到右依次按后根次序遍历森林中的每一棵树。
结论二,当用二叉链表作为树和森林的存储结构时，树和森林的先根遍历和后根遍历可分别用与该树和森林相对应的二叉树的先根遍历和中根遍历算法实现。
树和森林的遍历第六章 树和二叉树第 95页
1）基本术语树中两结点之间的路径从树中一个结点到另一个结点之间的分支。
树中两结点之间的路径长度从树中一个结点到另一个结点之间的路径上的分支数目。
树的路径长度从树 根 到树中每一结点的路径长度之和。
最优二叉树（哈夫曼树）
A
B
D E
C
F G
H I
第六章 树和二叉树第 96页示例 8 求下列四棵二叉树的路径长度
1
2
4
3
5
6 7
1
2
4
3
5 6 7
1
2 3
4 5
6 7
1
2
3
4
5
6
7
(1) (2) (3) (4)
[解 ] (1) 1+1+2+2+3+3=12
(2) 1+1+2+2+2+2=10
(3) 1+1+2+2+3+3=12
(4) 1+2+3+4+5+6=21
注,结点数目相同的二叉树,完全二叉树 的路径长度最短。
最优二叉树（哈夫曼树）
第六章 树和二叉树第 97页在许多应用中，常常将树中结点赋予一个有某种意义的实数，称为该结点的 权 。
结点带权的路径长度该点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度树中所有 叶结点 的带权路径长度之和，记作其中 n表示该树中 叶结点 的数目,wk和
lk(k=1,2,··,n)分别表示叶结点 ik的权值和从树根到叶结点 ik之间的路径长度。
最优二叉树（哈夫曼树）
第六章 树和二叉树第 98页示例 9 求下列三棵二叉树的带权路径长度，设它已知叶结点 a,b,c,d的权值分别为 7,5,2,4.
图 6.24具有不同带权路径长度的二叉树
[解 ] (1) WPL=7× 2+5× 2+2× 2+4× 2=36
(2) WPL=4× 2+7× 3+5× 3+2× 1=46
(3) WPL=7× 1+5× 2+2× 3+4× 3=35
问：具有 a,b,c,d4个叶结点的二叉树中，哪一种树其带权路径长度为最小？又，带权路径长度为最小的二叉树是否唯一？
a b c d7 5 2 4 d 4
a b
7 5
c
2 a 7
b
5
c d
2 4
(2) (3)(1)
最优二叉树（哈夫曼树）
第六章 树和二叉树第 99页定义 在权为 w1,w2,··,wn的 n个 叶结点 的所有二叉树中，带权路径长度最小的二叉树称为 最优二叉树或哈夫曼 (Huffman)树 。
上述三棵具有 4个叶结点 a,b,c,d且 分别带权 7,5,2,4的二叉树中，第三棵二叉树的 MPL最小。它是否一棵哈夫曼树呢？可以验证，它就是一棵哈夫曼树。
由上例可看出，在叶结点数目及权值相同的二叉树中,完全二叉树不一定是最优二叉树 。一般情况下
,在最优二叉树中，权值越大的叶结点离根结点越近
。
示例 哈夫曼树的简单应用 ——获得最佳判定算法。
问题：编制一个将百分制转换成五级分制的程序。
最优二叉树（哈夫曼树）
第六章 树和二叉树第 100页可用如下语句实现：
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`;
判定树
a
a<60
a<70
a<80
a<90
不及格中 等优 秀 良 好及 格
Y
Y
Y
Y
N
N
N
N
设学生成绩在五个等级的分布规律如下：
分 数 0~59 60~69 70~79 80~89 90~100
比例数 5% 15% 40% 30% 10%
80%以上的数据（ 70~100分）需进行三次或三次以上的比较才能得出结果。
第六章 树和二叉树第 101页在判定树 b中，每个判定框都有两次比较。今将这两次比较分开，
即可进一步得如下所示的判定树今尝试构造一棵有五个叶结点的哈夫曼树，即 按权值高者靠近根结点,以便使得大部分的数据经过 较少的比较次数 即可得出结果。得到如下之判定树
70≤a<80
80≤a<90
60≤a<70
a<60
中 等良 好及 格不及格 优 秀
Y
Y
Y
Y
N
N
N
N
判定树
b
第六章 树和二叉树第 102页
a<80
a<70 a<90
a<60
不及格 及 格 中 等 良 好 优 秀
Y
Y
Y N
NN Y
N
判定树 C计算 WPL
判定树 a
5× 1+15× 2+40× 3+30× 4+10× 4=315
判定树 b
40× 1+30× 2+15× 3+5× 4+10× 4=205（但每个判定框有两次比较）
判定树 c
5× 3+15× 3+40× 2+30× 2+10× 2=220
最优二叉树（哈夫曼树）
第六章 树和二叉树第 103页哈夫曼算法思想哈夫曼给出了一个精巧和、构造最优二叉树的方法，称为哈夫曼算法。其算法思想是：
(1) 根据给定的 n个权值 {w1,w2,···,wn}构成 n棵二叉树的集合
F={T1,T2,···Tn}，其中每棵二叉树 Ti(i=1,2,···,n)中只有一个带权为
wi的根结点，其左、右子树均为空；
(2) 在 F中选取两棵根 结点的权值最小的树作为左、右子树构造一棵新的二叉树，新树的根结点的权值为其左、右子树上根结点的权值之和；（进一步规定轻的在左边）
(3) 在 F中删除这两棵树，同时将新得到的二叉树加入 F中；
(4) 重复 (2)和 (3)，直到 F只含一棵树为止。这棵树便是哈夫曼树。
构造最优二叉树第六章 树和二叉树第 104页示例 1 构造一棵叶结点为 a,b,c,d且其权值分别为 7,5，
2,4的哈夫曼树。
a b c d
7 5 2 4步骤 1
a b
7 5步骤 2
d
6
4
c
2
a
7步骤 3 11
6
b
5
d
4
c
2
步骤 4 18
11
a
7
6
b
5
dc
2 4
图 6.26 哈夫曼树的构造过程
构造最优二叉树第六章 树和二叉树第 105页由哈夫曼算法可知，
(1)初始森林中共有 n棵二叉树，每棵树中都有仅有一个孤立的结点，它们既是根结点，又是叶结点。
(2)算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树。每合并一次，森林中就减少一棵树。
(3)显然，总共要进行 n-1次合并，才能使森林中的二叉树的数目，由 n棵减少到只剩下一棵最终的哈夫曼树。并且每次合并，都要产生一个新结点，显然它们都是具有两个孩子结点的分支结点。
(4)由此可知,最终求得的哈夫曼树中共有 2n-1个结点,其中 n
个叶结点是初始森林中的 n个孤立结点，并且哈夫曼树中 没有度数为 1的分支结点 。称这类树为 严格和（或正则的）二叉树 。
哈夫曼树的存储结构第六章 树和二叉树第 106页设哈夫曼树共有 n个叶结点。哈夫曼树中任一结点的度为 0或 2。
由 二叉树性质 3，二叉树的终端结点数等于度为 2的结点数加 1，即
n0=n2+1，
故有
n2=n0-1=n-1；
而总结点数为总结点数 =n0+n2 =n+(n-1) =2n-1.
哈夫曼树的存储结构：由于哈夫曼树的结点数据固定，
故可使用向量来存储并模拟一棵哈夫曼树 。
哈夫曼树的存储结构第六章 树和二叉树第 107页
typedef struct nodetype{
int weight； //或 float
int parent,lch,rch;
} *htnodeptr;
typedef nodetype[maxnode] huftree;
其中,weight：结点的权值,lch,rch：结点的左、右孩子在向量中的下标。若是叶结点，则这两个指针值均为 0
parent：结点双亲在向量中的下标。若 parent的值为 0，则表示该结点是无双亲的根结点，否则是非根结点。
哈夫曼树的存储结构第六章 树和二叉树第 108页构造哈夫曼树的算法可粗略描述如下：
(1) 将哈夫曼树向量（类型为 huftree）中的 2n-1个结点初始化，即将各结点中的三个指针和权值均置为 0；
(2) 将 n个权值 w[i](i=1,2,··,n)放入向量 ht的前 n个分量中
，它们是初始森林中的 n个孤立的根结点上的权值；
(3) 对森林中的树进行 n-1次合并，共产生 n-1个新结点
，依次放入向量 ht的第 i(n+1≤i≤m)个分量中。
哈夫曼算法描述第六章 树和二叉树第 109页
huffman( huftree ht,int *w,int n )
//构造哈夫曼树。 W中存放 n个叶结点的权值,ht表示哈夫曼树
{ for( i=1; i <= m; i++ )
{ ht[i].parent=0;
ht[i].lch=0;
ht[i].rch=0
}; //初始化
for( i=1; i <= n; i++ )
ht[i].weight = w[i]; //初始化
for( i=n+1; i <= m; i++ )
//构造哈夫曼树，共进行 n-1次合并，产生 n-1个新结点
{ s1 = s2 = 0; sm1 = max; sm2 = max;
//以上是为找两个权值最小的根结点作初始化,max是机器允许的最大数
for( j=1; j <= i-1; j++ )
//在当前森林的所有 i-1个结点中选出两个最小权值的根结点
哈夫曼算法描述第六章 树和二叉树第 110页
if( ht[j].parent == 0 ) //第 j个结点是根结点
if( ht[j].weight < sm1 )
//改变最小权 sm1和次小权 sm2及它们所对应的位置 s1和 s2
{ sm2 = sm1; sm1 = ht[j].weight;
s2 = s1; s1 = j;
}
else //ht[j].weight≥sm1
if( ht[j].weight < sm2 ) //改变次小权 sm2及位置 s2
{ sm2 = ht[j].weight; s2 = j };
//以下是合并
ht[s1].parent = i; ht[s2].parent = i;
ht[i].lch = s1; //最小权的根结点是新结点的左孩子
ht[i].rch = s2; //次小权的根结点是新结点的右孩子
ht[i].weight = ht[s1].weight + ht[s2].weight
} //FOR i
} //huffman
哈夫曼算法描述第六章 树和二叉树第 111页什么是哈夫曼编码哈夫曼算法的应用很广泛，联系到不同的计算机算法，可以赋予带权路径长度不同的含义。例如，外部排序中常使用哈夫曼算法来确定一个最佳合并次序。
哈夫曼算法的一个重要应用是哈夫曼编码，即应用于数据通信的二进制编码中。
在电报通信中，电文是以二进制的 0,1序列传送的。在发送端，
需要将电文中的字符转换成二进制的 0,1序列（编码），在接收端，
则要将收到的 0,1串转化为对应的字符序列（译码）。
哈夫曼编码第六章 树和二叉树第 112页问题,字符集中的字符被使用的频率是非均匀的，如
E,T较 Q,Z的使用频率要高得多。
如何能让使用频率高的字符的编码尽可能地短，从而使传送电文的总长度亦尽可能地短
？
哈夫曼编码最简单的编码方式是等长编码。
例如，设电文是由英文大写字母组成，其编码集合为 {A,B
,···,Z},等长二进制编码可采用每个字符用 5位二进制位串表示
(25>26),而可获得对应的文字。
第六章 树和二叉树第 113页什么是哈夫曼编码
哈夫曼编码
A – 00
B – 01
C – 10
D – 11
ABACCDA 00010010101100
ABACCDA 000011010
BBCCDA BADDA
示例：编码方式第一种
A – 0
B – 00
C – 1
D – 01
第二种
A – 0
B – 10
C – 110
D – 111
第三种
ABACCDA 01001101101110
能正确译出不能正确译出能正确译出第六章 树和二叉树第 114页可以使用二叉树来设计二进制的前缀编码。
示例 3 对于下述一棵二叉树，其四个叶结点分别表示
A,B,C,D四个字符,且约定左分支表示字符 `0`，右分支表示字符 `1`。 则可以从根结点到叶结点的路径上分支字符组成的字符串作为该叶结点字符的编码：
前缀编码：
A,0
B,10
C,110
D,111
A
D
1
B
C
1
1
0
0
0
哈夫曼编码若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。称这种编码为 前缀编码 或简称 前缀码 。
显然,等长编码是前缀码 。
什么是哈夫曼编码第六章 树和二叉树第 115页设计电文总长最短的二进制前缀编码即为以 n种字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码便称为 哈夫曼编码 。
struct nodetype{
int weight;
int parent,lch,rch; //0..m
};
struct codetype{ //字符的编码
char bits[n+1];
int start;
};
nodetype huftree[m];
codetype hufcode[n];
什么样的前缀码才能使得电文总长为最短？
哈夫曼编码的算法描述第六章 树和二叉树第 116页
huffman_code ( int w[n],huftree &ht,hufcode &hcd )
//w中存放 n个字符的权值,ht表示哈夫曼树,hcd存放 n个字符的哈夫曼编码
for( i=1; i<=n; i++ ) //求哈夫曼编码
{ cd.start = n;
//cd为 codetype型的变量； start表示编码开始的前一位置
c = i; f = ht[c].parent;
while( f ≠ 0 )
{ if( ht[f].lch == c )
cd.bits[cd.start] = 0
else cd.bits[cd.start] = 1;
cd.start--;
c = f; f = ht[f].parent;
};
hcd[i].bits[1..n-start] = cd[start+1...n]
}
} //huffman_code
{ huffman (ht,w); //建哈夫曼树
哈夫曼编码的算法描述
A
D
1
B
C
1
1
0
0
0
011
start
C
第六章 树和二叉树第 117页例 6-2 已知某系统在通信联络中只可能出现八种字符，其频率分别为 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，
试设计哈夫曼编码。
[分析 ] 设权值 w=(5,29,7,8,14,23,3,11).
n=8,m=2n-1=15,初始森林
哈夫曼编码的算法描述第六章 树和二叉树第 118页
w e i g h t p a r e n t l c h r c h
1 5 0 0
2 29 0 0
3 7 0 0
4 8 0 0
5 14 0 0
6 23 0 0
7 3 0 0
8 11 0 0
9
10
11
12
13
14
15
构建哈夫曼树
(b) ht的终态
d2
d1
d4
d3
d6
d5
d7
d8
哈夫曼编码的算法描述
(a) ht的初态
8 7 1
9
9
14
58 2 12
14
15 3 4
10
10
19 9 8
11
11
29 5 10
12
12
42 11 6
13
13
100 13 14
15
15
第六章 树和二叉树第 119页
d2
d4
1
d5
d3
1
1
0
0
1
d7
d6
d8
d1
1
0
0
0
0 1
100
42
19
8
35
7 8
15
29
58
29
14
f=0
f=15
f=13
f=11
f=9
c=1
哈夫曼树例 6-2 的哈夫曼树
23
11
0
1
2
3
4
5
6
7
8
0110
10
1110
1111
110
01111
010
00
1
第六章 树和二叉树第 120页可将编码表列表表示如下用累加各个代码的长度乘以字符出现的频率，求得平均代码长度为
AVG=4× 0.05＋ 2× 0.29＋ 4× 0.07
＋ 4× 0.08＋ 3× 0.14＋ 2× 0.23＋ 4× 0.03＋ 3× 0.11
=2.71
故它比固定长度的代码要好些。它具有的另一个重要优点是：当收到前缀码的一个序列后，仅仅只有一种译码的方法，从而不会因码的多义性而不知所措。
字 符 频 率 前缀编码
d 1 0,0 5 0 1 1 0
d 2 0,2 9 1 0
d 3 0,0 7 1 1 1 0
d 4 0,0 8 1111
d 5 0,1 4 1 1 0
d 6 0,2 3 0 0
d 7 0,0 3 0 111
d 8 0,1 1 0 10
固定代码 23=8.
AVG=3 但若有 9个值，则需 AVG=4而哈夫曼编码仍可能在小于 3之列第六章 树和二叉树第 121页一棵哈夫曼树编码树同时也是一棵 译码树 。收到的任一长度的码序列，可以被翻译成唯一的字符序列。可以让收到的二进制位信息序列从树根开始“流”下去，
每一位选择一条树的分枝，若位为 0时流向左分枝，为
1时流向右分枝。每到达一个叶结点时，就截取一个代码组，并译出一个相应字母，然后再回到根结点，重复译码过程，直至信息流变空为止。
哈夫曼编码的算法描述有什么缺点？
当在传送过程中若有一位发生了差错，那么其后的所有内容是否还能正常译出？
第六章 树和二叉树第 122页示例 2 （八枚硬币问题） 假定有八枚硬币 a,b,c,d,e,f,g,h，其中有一枚硬币是伪造的。真伪硬币的区别仅在于重量上有所不同，伪币可能比真币重，亦可能比真币轻。但真币均一般重。
今要求以天 平 为工具，用最少的比较次数挑出伪造硬币，并确定它比真币重或是轻。
[分析 ] 可经过三次用天平称重比较，即能获得所需结果。其方法可以用如下页之判定树来表示。
树的应用判定树第六章 树和二叉树第 123页
a+b+c? d+e+f
a+d? b+e a+d? b+eg? h
b?a c?a b?a g?a h?a b?a c?a b?a
> = <
< < <> > >= =
======
= =>
> > > ><<<
今仅分析其中一类情况。
设第一次称重有 a+b+c<d+e+f。可知伪币应在这六枚之中，即 g,h必是真币。
设第二次称重有 a+d<b+e。此时，由于交换了 b和 d的位置，而不等式仍然成立，故知,1,c,f均是真币； 2,b,d均是真币。从而可知,a,e中必有一枚是伪币。
设第三次称重有 b=a，则知 e是伪币，且 a较真币为重。
若第三次称重有 b>a，则知 a是伪币，且 a较真币为轻。
同理可以获得各种结论。
a-H e-L
c-H f-L
b-H d-L g-H h-L h-H g-L d-H b-L f-H c-Le-H a-L
注,H–Heavy L–Light
第六章 树和二叉树第 124页博弈树树形结构的另一个有趣的应用是在人机对奕的下棋程序中。
如象棋、跳棋的二人游戏等。今举一个示例以说明什么是博亦树
（比赛树）。
示例 3 （取牙签比赛）假定有 n根牙签，由 A,B两人交替地把这些牙签拿走，并规定：每次只能拿 1根或 2根或 3根牙签，不允许 1根也不拿，亦不允许多拿。拿最后一根牙签者判输。
[分析 ] A,B两个轮流拿牙签可以比拟成两个人轮流下棋，
棋盘即为游戏板。在任何时候游戏板的状态，由这堆牙签中所剩下的牙签数确定。
一个游戏板的状态序列 C1,C2,···,Cm 是有效的，需满足下列诸条件：
1) C1是游戏开始状态；
2) Ci(o<i<m)是非结束状态；
3) 如果 i是奇数，则由 A作合法移动，状态从 Ci 到 Ci+1；若 i是偶数，则由 B作合法移动，状态亦由 Ci 到 Ci+1。
如果 Cm是终结状态，则 C1,C2,···,Cm就构成一局比赛游戏
。
二叉树的应用第六章 树和二叉树第 125页一个有限的游戏
（比赛），可由博弈树（比赛树）来表示各种可能的情况。
为确定 A从某个状态拿几根牙签，使用估值函数 E(x)
+1，当 x是 A的一个获胜状态时
–1，当 x是 A的一个失败状态时应用这个估值函数，当 A移动到下一个状态（三种,b,c
或 d）时，应当选择
{V(b),V(c),V(d)}
中之最大值，其中 V(x)为状态 x的值。
注,剩余牙签树就是状态。
根到叶子的路径就是一局比赛。
E(x)=
| | | |
| | || | |
| | | |B B B
| AAA
B
1 2 3
a
b c d
1 2 3 1 2
21
-1 -1 +1
-1-1+1 -1
,B移动前状态
,A移动前状态
二叉树的应用第六章 树和二叉树第 126页问题：具有 n个结点的不同形态的树共有多少棵？
以讨论二叉树为示例，然后可将结论推广到一般树
。
定义 1 若已知两棵二叉树 T 和 T` 皆为空树，或皆不空且 T 的左、右子树和 T` 的左、右子树分别相似，
则称二叉树 T 和 T` 相似。
定义 2 若已知两棵二叉树 T 和 T` 相似，而且所有对应结点上的数据元素均相同，则称二叉树 T 和 T` 等价。
二叉树的计数问题就是讨论具有 n个结点、互不相似的二叉树的数目 bn。
树的计数第六章 树和二叉树第 127页
n=0,b0=1 （空树）
n=1,b1=1,只有一个根结点的树
n=2,b2=2,其形态分别为
n=3,b3=5,其形态分别为
n>3,bn=?
一般情况下，一棵具有 n(n>1)个结点的二叉树可以看成是由一个根结点、一棵具有 i个结点的左子树，和一棵具有 n-i-1个结点的右子树所组成，如下图所示根
(0≤i≤n-1)
第六章 树和二叉树第 128页结论
1,具有 n个结点、互不相似的二叉树的数目 bn可由下列之递推公式求得
2,具有 n个结点、互不相似的二叉树的数目 bn为注,
1,
1
1
0
1
0
nbbb
b
n
i
inin
.11 2n nn Cnb
14
)!48(!4
!8
5
1
5
1
,4
5
)!36(!3
!6
4
1
4
1
,3
2
)!24(!2
!4
3
1
3
1
,2
1
)!12(!1
!2
2
1
2
1
,1
1
1
1
,0
4
84
3
63
2
42
1
21
0
00
Cbn
Cbn
Cbn
Cbn
Cbn
第六章 树和二叉树第 129页从二叉树的遍历可知，任意一棵二叉树结点的前序遍历序列和中序遍历序列均是唯一的。现问：
若给定结点的前序遍历序列和中序遍历序列，能否据此唯一地确定一棵二叉树？
有如下之结论结论 由一棵二叉树的前序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。
还有下列两个推论推论 1 由一棵二叉树的后序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。
推论 2 由一棵二叉树的前序遍历序列和后序遍历序列，不能唯一确定这棵二叉树。
关于二叉树的确定第六章 树和二叉树第 130页为推论 2举一示例设已知某二叉树的前序遍历序列和后序遍历序列分别为前序遍历序列,AB
后序遍历序列,BA
则有可能是下述两棵二叉树中之一前序遍历序历,AB 前序遍历序列,AB
后序遍历序列,BA 后序遍历序列,BA
A
B
A
B
关于二叉树的确定第六章 树和二叉树第 131页例 6-5 已知结点的前序遍历序列和中序遍历序列分别为前序遍历序列,ABCDEFG
中序遍历序列,CBEDAFG
试构造据此唯一确定的二叉树。
[解 ] 第一步：由前序遍历序列知，二叉树的根为 A，而由中序遍历序列知，该二叉树的左子树的中序遍历序列为 CBED，又右子树的中序遍历序列为 FG。从而可推知其左子树的前序遍历序列必为 BCDE，而右子树的前序遍历序列必为 FG。故可得第二步：类似地处理左子树部分，可分解出根 B，以及其左子树
、右子树部分
A
关于二叉树的确定
C
B
E
D
F
G
第六章 树和二叉树第 132页
A
B
C
第三步：进一步分解出根结点 D及其左、右树部分
A
B
C D
E
第四步：最后分解出 A的右子树中的根 F及其左、右子树部分
A
B
C D
E
F
G
第六章 树和二叉树第 133页递归过程算法描述
preinorder (bt,P,M);
//P——先序遍历序列 M——中序遍历序列
{ bt=P[1];
i=1;
while( M[i]≠P[1] ) i++;
bt->lchild = M[1..i-1];
bt->rchild = M[i+1..n];
if( bt->lchild≠NULL )
preinorder (bt->lchild,P[2..i],M[1..i-1]);
if( bt->rchild≠NULL )
preinorder (bt->rchild,P[i+1..n],M[i-1..n])
} //preinorder
关于二叉树的确定第六章 树和二叉树第 134页第六章 树和二叉树小结这一章是本门课程内容中的一个重点内容提要
● 树的结构定义和基本操作
● 二叉树的定义、基本操作、性质和存储结构
● 二叉树的遍历和线索化
● 树、森林与二叉树的转换
● 树和森林的遍历
● 哈夫曼树与哈夫曼编码
● 树的其他应用 —— 表达式求值、判定树、博奕树、树的计数、二叉树的确定等第六章 树和二叉树第 135页学习要点
● 熟悉树和二叉树的递归定义、有关的术语及基本概念
● 熟练掌握二叉树的结构特性，了解其相应的证明方法
● 熟悉二叉树的各种存储结构的特点及适用范围
● 熟练掌握二叉树各种次序的遍历算法，了解遍历过程中栈的状态
● 了解二叉树的线索化及其实现，掌握在中序线索化树上寻找给定的前驱和后继的方法
● 熟练掌握树、森林与二叉树之间的转换方法
● 了解最优二叉树即哈夫曼树的特性，掌握建立最优二叉树和哈夫曼编码的方法
● 了解树的其他各种应用
第六章 树和二叉树
（重点）
第六章 树和二叉树第 2页第六章 树和二叉树
内容 树、二叉树、森林的概念和性质，树与二叉树的转换，树形结构的存储，遍历，哈夫曼树的概念及应用。
要求 通过学习和上机，深刻理解树形结构的递归特性，为应用它解决实际问题奠定理论基础并获得实践经验。理解并准确叙述 树,二叉树,
森林 及其有关概念并熟悉它们的基本性质，熟悉树形结构的 存储结构 和 中序线索二叉树,熟悉树的 遍历方法,尤其是二叉树的 前序,中序 和 后序遍历的递归与应用，知道树形结构的若干应用。
第六章 树和二叉树第 3页
重点
1,树、二叉树的概念和性质
2,树结构的存储
3,树和二叉树的遍历算法以及树的前序、
中序和后序遍历算法
难点
1,树形结构的存储方法
2,中序线索树
3,二叉树遍历的非递归算法
4,树的应用第六章 树和二叉树第六章 树和二叉树第 4页树的逻辑结构 ——它定义一类重要的 非线性结构 。
树结构在计算机科学的很多领域都得到了广泛的应用。
树结构可应用于诸如
编译程序中表示源程序的语法结构
数据库系统中的信息组织
文件目录
电路分析
社会各个组织和管理机构
家谱
书的章节编目
军队编制树型结构是结点之间有分支、层次关系的结构，它非常类似于自然界中的树。树型结构在客观世界中大量存在。
树的结构定义第六章 树和二叉树第 5页定义 1 树 Tree=(D,R)是一种 层次数据结构,其中 D是具有相同特性的数据元素（称为树结点）的有限集合,R是定义在 D上的二元关系。在这种关系中,有且仅有一个特定的无前趋的结点（称为树的根，记作 root），其余的每一个结点有且仅有一个直接前趋。
注,树的这种结构对 每一个结点的后继不加限制,任何一个结点都可以有 0至多个后继结点 。
定义 2 （ 树的递归定义）树是 n(n≥1)个结点的有限集合，
其中
(1) 有且仅有一个特定的称之为根（ root）的结点；
(2) 其余的结点可分为 m(m ≥0)个互不相交的集合 T1,T2,…
,Tm，而每一个集合本身又是一棵树，并且称为根的子树（
sub tree）。
为了讨论方便，有时也将结点数为 0的空集合也看成树，并称之为空树。
树的结构定义第六章 树和二叉树第 6页树的表示示例
A
B
C
A
C DB
E F
－
/+
a? e f
b －
c d
A
仅有根结点的树一般树
A
C DB
E F H J
K L
G I
M
二叉树树的结点：一个个的记录树的枝或边：指向其他结点的指针
树 的 表 示第六章 树和二叉树第 7页非树表示示例不是树，因为它没有一个 根 结点不是树，因为其中的一个结点有 两个前趋 结点不是树，因为它是不相交的两棵树的集合。它是 森林
树 的 表 示第六章 树和二叉树第 8页树的其它三种表示方法
文氏图表示法用集合的嵌套即包含关系来表示
广义表表示法用嵌套括号表示。
根作为由子树森林组成的表的名字写在表的左边
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
A
E
K L
F
B H
M
I
J
D
G
C
树 的 表 示第六章 树和二叉树第 9页
凹入表示法类似于书的编目，即分成章节、小节，分别缩进表示
A
B
E
K
L
F
C
G
D
H
M
I
J
树 的 表 示第六章 树和二叉树第 10页以如图所示的一棵树为范例结点 （ node） 树中的的一个独立单元。它包括一个信息项和若干个指示其他树结点的位置信息。结点的信息项可包含一个关键字和其他的数据项。常用圆圈内的一个字母或数字表示该结点的信息项或关键字，并用来标识该结点，如结点 A,结点
B。
根 （ root） 树唯一无前趋（前件）的结点，如结点 A。 有时也用根结点标记整棵树，称其为树 A。
结点的度 （ degree of node） 结点拥有的 子树（或后件）数 。
如结点 A的度为 3,B的度为 2,C的度为 1,D的度为 3,E的度为 2
,F的度为 0，等等。
A
C DB
E F H J
K L
G I
M
树 的 基 本 术 语树的度 （ degree of tree）树内各 结点度的 最大值,如示例树的度为 3。
第六章 树和二叉树第 11页叶结点 （ leaf node） 或称终端结点，
系指树中度为 0（或没有后件）的结点。
如 K,L,G,M,I,J都是叶结点。
双亲 （ parent） 树中各结点的直接前趋称为该结点的双亲。如结点 A是结点 D的双亲，结点 H是结点 M的双亲等等。
祖先 （ ancestor） 从根结点到该结点所经分支上的所有结点。
如结点 K的祖先分别为 A,B,E。
分支结点 （ branch node） 亦称非终端结点，系指度不为 0的结点，包括根结点。
孩子 （ children） 一个 树结点的直接后继 均是该树结点的孩子
。如结点 B,C,D均是结点 A的孩子。
兄弟 （ Sibling） 同一个双亲的孩子之间互称兄弟。如结点 E,F
互为兄弟,H,I,J互为兄弟，等等。
树 的 基 本 术 语
A
C DB
E F H J
K L
G I
M
第六章 树和二叉树第 12页子孙 （ descendant） 以某结点为根的子树中的任一结点都称为该结点的子孙。比如，除根结点 A之外的所有结点都是 A的子孙树枝 （ branch） 亦称为树边，系指连接两个结点的有向线段。
一般是由父结点指向子结点。为了画图方便，一般将箭头方向省略树的深度 （ depth of tree） 亦称树的高度，系指树中各结点层次的最大值。如树 A的深度为 4。
堂兄弟 （ brother-in-law） 其双亲在同一层的结点。如结点 E,G和 H均为堂兄弟。
结点的层次 （ level of node） 结点所位于的层数（以根结点为第一层）。如结点 B的层次为 2。树中任一结点的层次等于它的双亲结点的层次加 1。
结点的枝长 （ length of branch） 亦称该结点的路径长度，系指由根结点至该结点所经过的树枝数,它应等于该结点的层次数减 1
。如结点 B的枝长为 1。
树 的 基 本 术 语
A
C DB
E F H J
K L
G I
M
第六章 树和二叉树第 13页有序树 （ ordered tree） 规定了树中所有结点的每一棵子树或后件的次序（从左至右，且不能互换）的树。比如，以下两棵树是互不相同的有序树。
完全树 （ Complete tree） 亦称正则树，系指在 n阶树中，它的每一个结点，要末有 n个后件，要末一个后件也没有。比如，下列三棵树无序树 （ unorded tree） 凡不是有序树的树。
A
B C
A
C B
中,(a),(b)均为完全树，而 (c)则不是完全树。
(a) (b) (c)
树 的 基 本 术 语第六章 树和二叉树第 14页定义 3 m(m ≥0)棵互不相交树的集合称为 森林 。森林与树的概念非常相近，比如将范例树中的根结点 A删去，该树就分解成由原树的三棵子树 B,C,D组成的森林。反之，可以用一个新的树根结点将若干棵互不相交的树 (即森林 )组合成一棵新树。
定义 4 任何一棵树是一个二元组 Tree=(root,F)，其中
root是数据元素，称做树的根结点； F是 m(m≥0)棵树的森林,F=(T1,T2,…,Tm)，其中 Ti=(ri,Fi)称做树根 root的第 i
棵子树；当 m≠0时，在树根和其子树森林之间存在下列关系
RT={<root,ri>|1≤i≤m,m>0}
此定义有助于得到森林和树与二叉树之间转换的递归定义。
树 的 基 本 术 语
A
C DB
E F H J
K L
G I
M
第六章 树和二叉树第 15页
(1) 初始化操作 Initiate(T)
置 T为空树。
(2)要求根结点函数 Root(T)或 Root(x)
返回树 T的根结点或结点 x所在的树的根结点。若 T是空树或 x
不在任何一棵树上，则返回空函数值 NULL。
(3)求双亲结点函数 Parent(T,x)
返回树 T中的根结点或结点 x不在树 T中，则返回空函数值
NULL。
(4)求孩子结点函数 Child(T,x,i)
返回树 T中结点 x的第 i个孩子结点。若结点 x是树 T中的叶结点或无第 i个孩子结点，或者结点 x不在树 T中，则返回空函数值 NULL。
(5)求右兄弟结点函数 Right_Sibling (T,x)
返回树 T中结点 x右边的兄弟结点。若结点 x是其双亲的最右边的孩子结点或结点 x不在树 T中，则返回空函数值 NULL。
树 的 基 本 操 作第六章 树和二叉树第 16页
(6) 建树函数 CreateTree(x,F)
生成一棵以 x结点为根，以森林 F为子树森林的树。
(7) 插入子树操作 InsChild(y,i,x)
置以结点 x为根的树 为结点 y的第 i棵子树。若原树中无结点 y，
或结点 y的子树个数小于 i-1，则为空操作。
(8) 删除子树操作 DelChild(x,i)
删除结点 x的第 i棵子树。若无结点 x或结点 x的子树个数小于 i，
则为空操作。
(9) 树的遍历操作 Traverse(T)
按某个次序依次访问树中各个结点，并使每个结点只被访问一次。
(10) 清除树的结构操作 Clear(T)
将树置为空树。
注,树的抽象数据类型可随需要而设定。
树 的 基 本 操 作第六章 树和二叉树第 17页二叉树是树型结构的另一个 重要类型,许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此，二叉树显得特别重要。
二叉树的定义定义 （二叉树的递归定义）二叉树 (binary tree)是结点的一个有限集合，这个集合或是空集，或是由一个根结点及两棵分别称为根结点的左子树和右子树的互不相交的二叉树组成。
二叉树的定义与基本操作第六章 树和二叉树第 18页由于二叉树递归定义中的两棵子树亦都是二叉树，则它们亦可为空树。故二叉树可有下列五种基本形态：
(a) (b) (c) (d) (e)
(a) 空二叉树
(b) 仅有根结点的二叉树
(c) 有根结点及左子树，右子树为空的二叉树
(d) 有根结点及左、右子树的二叉树
(e) 有根结点及右子树，左子树为空的二叉树二叉树中，每个结点最多只能有 两棵 子树,并且有左、右之分 。
两棵不同的二叉树 一棵普通树
A
B
C D
E
A
B
C
E
D
A
B
DC
E
二叉树的五种基本形态第六章 树和二叉树第 19页二叉树示例深度为 4 深度为 5
A
B C
D E
G H
F
A
B
C
D
E
二叉树的定义与基本操作第六章 树和二叉树第 20页二叉树的基本操作与树的基本操作相类似，不同的是在求孩子结点、兄弟结点以及插入、删除等操作时，均有左、右之分。
(1) Initiate(BT)
初始化操作，置 BT为空树。
(2) Root(BT) 或 Root(x)
求根结点函数
(3) Parent(BT,x)
求双亲结点函数。
(4) LChild(BT,x) 和 RChild(BT,x)
求孩子结点函数。分别返回二叉树 BT中结点 x的左孩子结点和右孩子结点。若结点 x是二叉树 BT的叶结点或 x不在二叉树 BT中，
则返回空函数值 NULL。
(5) LSibling(BT,x) 和 RSibling(BT,x)
求兄弟结点函数。分别返回二叉树 BT中结点 x的左兄弟结点和右兄弟结点。若结点 x是根结点或 x不在 BT中或 x是其双亲的左 /右子树根，则返回空函数值 NULL。
第六章 树和二叉树第 21页二叉树的基本操作
(6) Create (x,LBT,RBT)
建树操作。生成一棵以结点 x为根，二叉树 LBT和 RBT分别为左、右子树的二叉树。
(7) InsLChild(BT,y,x) 和 InsRChild(BT,y,x)
插入子树操作。将以结点 x为根且右子树为空的二叉树分别置为二叉树 BT中结点 y的左子树和右子树。若结点 y有左子树 /右子树
，则插入后是结点 x的右子树。
(8) DelLChild(BT,x) 和 DelRChild(BT,x)
删除子树操作。分别删除二叉树 BT中以结点 x为根的左子树或右子树。若结点 x无左子树或右子树，则为空操作。
(9) Traverse (BT)
树的遍历操作。按某个次序依次访问二叉树 BT中各个结点，
并使每个结点只被访问一次。
(10) Clear(BT)
清除二叉树的结构操作。
注,与树类似，用户可根据操作需要设定二叉树的抽象数据类型。
第六章 树和二叉树第 22页
二叉树的性质二叉树与一般树既有联系，又有区别，它是有序树的一个特例
。用于一般树上的术语也可用于二叉树。二叉树有若干重要性质。
性质 1 在二叉树的第 i层上至多有 2i-1个结点 (i≥1)。
[证 ] 用归纳法。
i=1，只有一个根结点。 2i-1=20=1。正确。
设命题对 j成立，即有第 j层上至多有 2j-1个结点。由于二叉树每个结点的度至多为 2，故在最大结点数的 2倍，即
2j-1.2=2j=2(j+1)-1。故命题对 j+1亦成立。证毕。
性质 2 深度为 k的二叉树至多有 2k-1个结点 (k ≥1)。
[证 ] 由性质 1，深度为 k的二叉树的最大结点数为
（第 i层上的最大结点数）
第六章 树和二叉树第 23页性质 3 二叉树 T的叶结点数等于度为 2的结点数加 1。
[证 ] 若记二叉树 T的终端结点数为 n0，度为 2的结点数为
n2，则欲证 n0=n2+1。
设 n1为二叉树 T中度为 1的结点数,n为二叉树 T中的总结点数。由于二叉树中所有结点的度均小于或等于 2，故有
n=n0+n1+n2 (1)
再看二叉树的分支数。除根结点外，其余结点都有一个分支进入。设 B为分支总数，则
n=B+1 (2)
由于这些分支是由度为 1或 2的结点射出的，所以又有
B=n1+2n2 (3)
由 (2)和 (3)知
n=n1+2n2+1 (4)
由 (1)和 (4)可得
n0=n2+1.
二叉树的性质第六章 树和二叉树第 24页定义 5 一棵深度为 k且具有 2k-1个结点的二叉树称为满二叉树。
注,完全二叉树的另一种定义：深度为 k的完全二叉树，其 k-1
层是一棵满二叉树，最后第 k层结点都尽量排在靠左的位置上
（即第 k层的所有叶子结点占据树的最左边的位置）。
二叉树的性质定义 6 深度为 k有 n个结点的二叉树，当且仅当该二叉树的 n个结点与深度为 k的满二叉树中编号从 1至 n的结点位置一一对应时，则称为 亚满二叉树或完全二叉树 。
示例 1
2 3
4 5
8 9 10 11
6 7
12 13 14 15
(a) 满二叉树
1
2 3
4 5
8 9 10
6 7
(b)完全二叉树第六章 树和二叉树第 25页对完全二叉树的几点说明：
(1) 度小于 2的结点（包括度等于 0的叶结点）只可能在最下两个层次上出现；
(2) 对任一结点，其左子树的层次 ≥右子树的层次。以下两个二叉树都非完全二叉树
(3) 有的书中定义只有度为 0或 2的二叉树称为完全二叉树。则上页 (b)就为非完全二叉树；但若去掉结点 10或增加结点 11，则为完全二叉树；
(4) 满二叉树亦是完全二叉树，但反之不然。
1
2 3
4 5
6 7
1
2 3
4 5 6
二叉树的性质第六章 树和二叉树第 26页
[证 ] 对于满二叉树,n=2k-1，或 n+1=2k，得 k=log2(n+1),
由于 k是整数，故?log2n?+1
对于完全二叉树，根据性质 2和完全二叉树的定义知
2k-1-1<n≤2k-1
其中 2k-1-1与 2k-1分别表示深度为 k-1与 k的最大结点数。于是
2k-1 ≤ n<2k
或有
k-1≤log2n<k
由于 k是整数，故
k=?log2n?+1
示例 如右图，对于 n=8,9,10,···,14的完全二叉树，以及 n=15的满二叉树，均有
k=?log2n?+1 =3+1=4.
1
2 3
4 5
8 9 10 11
6 7
12
性质 4 具有 n个结点的满二叉树或完全二叉树的深度为?log2n?+1.
符号含义：
x? 表示不大于 x的最大整数。
表示不小于 x的最小整数。
例如,5.8
5.8? = 5
= 6
x
8.5
第六章 树和二叉树第 27页性质 5 如果对一棵有 n个结点的 完全二叉树 （其深度为?log2n?+1 ）的结点按层序编号（从第 1层到第
log2n?+1层，每层从左到右），则对任一结点 i(1 ≤
i≤n)，有
(1) 如果 i=1，则结点 i是二叉树的根，无双亲；
如果 i>1，则其双亲 Parent(i)是? i/2?
(2) 如果 2 *i>n。则结点 i无左孩子（结点 i为叶子结点）；如果 2i ≤n，则其左孩子 LChild(i)是结点 2i;
(3) 如果 2i+1>n，则结点 i无右孩子（但 i不一定是叶结点）； 如果 2i+1 ≤n，则其右孩子 RChild(i)是结点 2i+1。
二叉树的性质第六章 树和二叉树第 28页
[证 ] 用归纳法证明 (2),(3)，由 (2),(3)再导出 (1).
记 j为层次。
j=1：按完全二叉树定义，其左、右孩子应为结点 2,3。
若 2·1>n，则无左孩子；
若 2·1+1>n，则无右孩子。
设 j=i时结论成立，即有左孩子为结点 2i(2i≤n)，右孩子为结点 2i+1(2i+1 ≤n),现欲证 j=i+1时结论亦成立，即有左孩子为结点 2(i+1) (2(i+1) ≤n).
根据完全二叉树的特点，与结点 i+1的左孩子相邻的前两个结点分别是结点 i的左、右孩子。由归纳法假定,i的左孩子是 2i
，右孩子是 2i+1，因此,i+1的左孩子应为 2i+1+1=2(i+1)，如
2(i+1)>n，则说明 i+1无左孩子；而 i+1的右孩子为
2i+1+3=2(i+1)+1 (2(i+1)+1 ≤n),因此 j=i+1时 (2),(3)成立。
对任一结点 i(i ≤i ≤n)，除 i=1即结点外，若 i=偶数，则必是左孩子，其双亲是 i/2=? i/2?；若 i=奇数，则必是右孩子，其双亲是 i-i/2=? i/2?,故 (1)成立。
二叉树的性质第六章 树和二叉树第 29页下图展开了完全二叉树中结点 i和 i+1与其左、右孩子之间的关系
LChild(i) RChild(i) LChild(i+1) RChild(i+1)
结点 i和 i+1在 同一层次 （ i必为偶数）
[i/2]
i+1i
2i 2i+1 2i+2 2i+3
结点 i和 i+1不 在同一层次 （结点 i必在上一层最后,i+1必为此层最左； i必为奇数）
i
2i 2i+1
LChild(i) RChild(i)
i+1
2i+2 2i+3
LChild(i+1)
RChild(i+1)
第六章 树和二叉树第 30页二叉树的顺序存储结构可使用一组连续的存储单元 (向量，即一维数组 )来存储二叉树的数据元素。必须把二叉树中的所有结点安排成一个适当的线性序列,使得结点在这个序列中的相互位置能够反映出结点之间的逻辑关系。
示例
1
2 3
6 74 5
8 109 11 12
1 2 3 4 5 6 7 8 9 10 11 12
2i
↑
i
↑
2i
↑
2i+1
bt(1:12)
二叉树的存储结构第六章 树和二叉树第 31页非完全二叉树
1
2 3
0 04 5
0 60 7
1 2 3 4 5 0 0 0 0 6 7
bt(1:11)
(0表示不存在此结点 )
一般二叉树也必须以完全二叉树的形式来确定。
无结点的补 0，造成了存储空间的浪费。
1 0 2 3 0 0 0 0 0 4
bt(1:15)
0 0 0 0 0
1
0 2
0 30 0
0 00 0 0 0 40
最坏情况
二叉树的存储结构第六章 树和二叉树第 32页由于二叉树的 度数小,在所有存储方法中最主要、最方便的一种是二叉树的 标准存储形式，或称为二重链存储形式 。
一个结点 k由一个数据元素和分别指向其左、右子树的两个指针域组成当有必要时，可在每一个结点中再加上一个指向其父结点的指针域 parent。这就是二叉树的扩充标准存储形式注,利用上述两种结点结构所得二叉树的存储结构分别称为 二叉链表 和 三叉链表 。
lchild data rchild
k
lchild data parent
k
rchild
二叉树的链式存储结构第六章 树和二叉树第 33页
typedef struct BiNode{
datatype data;
BiNode *lchild,*rchild;
} BiNode,*BiTree; A
B
C
D
单支树的二叉链表的存储结构
A
B
C D
E F
G
A ^
B ^
C ^
D ^^
head
A ^
B
C ^^ D
E^ F ^^
G ^^
head
一般二叉链表的存储结构
二叉树的链式存储结构示例第六章 树和二叉树第 34页
A
B
C D
E F
G
一般三叉链表的存储结构
A ^
B
C ^^ D
E^ F ^^
G ^^
head
^
注,在含有 n个结点的二叉链表中有 n+1个空链域 。这是因为
n个结点总共有 n-1个边；
n个结点总共有 2n个链域（包括左、右链域）；
每个边需使用一个链域；
故应有 n+1个空链域。
应设法有效地利用这些空闲着的链域。
二叉树的链式存储结构第六章 树和二叉树第 35页问题的提出以上采用标准形式（左、右链接）存储二叉树时,n
个结点的 2n个链域中有 n+1个空链域，故链域的存储空间利用率 ≈1/2。但对于一个度为 d(d≥2)的树,n个结点总共需要 nd个链域，但除根结点外，有 n-1个结点被某个链域指示
，空链域的个数为
nd-(n-1)=n(d-1)+1,
故 d度树的链域利用率为
d越小，链域利用率越高，故 2度树存储空间利用率最高。如果能将一般树转化成一棵二叉树，那么不但存储代价小，很多对树的操作也会简单得多。
).2(11 ddndn
有序树和二叉树间的转化第六章 树和二叉树第 36页有序树和二叉树间的转化规则一棵有序树可以唯一地转化为根结点没有右子树的二叉树。反之，一棵根结点没有右子树的二叉树也能转化为唯一的一棵有序树。
有序树转化成其对应二叉树的规则
(1) 二叉树具有与有序树相同的结点；
(2) 如果在有序树中,n是 m的最左儿子，那么在二叉树中,n将是 m的左儿子；
(3) 如果在有序树中,n是 m的右边一个同胞兄弟
，那么在二叉树中 n将是 m的右儿子。
下面用图示形式来展现如何把一棵有序树转化成相应的二叉树。
有序树和二叉树间的转化第六章 树和二叉树第 37页有序树转化为二叉树的图示化方法步骤：
1,在树的所有同胞兄弟之间添加一水平连线；
2,删去父结点到除最左孩子之外的所有其它孩子之间的树枝；
3,再将新添加的水平连线按顺时针方向旋转 450。
显然，由树转换成的二叉树，其根结点的右子树总是空的，
因为原树根结点是没有兄弟的。
A
B
E G H
D
I J
C
F
K
A
B
E
FK
C
DH
I
J
G
步骤 3A
B
E G H
D
I J
C
F
K
XX
XXX?
步骤 2
步骤 1 A
B
E G H
D
I J
C
F
K
加连线
有序树和二叉树间的转化第六章 树和二叉树第 38页设已设定
typedef struct BiNode{
datatype data;
BiNode *lchild,*rchild;
} BiNode,*BiNodePtr,*BiTree;
Specification,binary_tree
Elements,树由结点和有向树边组成，结点的类型为 datatype，每一个结点具有一个唯一的键值 data。
Structure,二叉树或为空，或由一个根结点及其两棵互不相交的左
、右二叉树构成。二叉树是一个层次结构，即在三元组表示形式
L=（ P,R,V）中,P是 BiTree的有限子集,R是 P上的一个层次关系，除根以外的每一个结点都有且仅有一个前趋。 V是由
BiTree到 datatype的函数。
Operation,binary_tree包括下列基本操作，这些操作除了
Create外，都假定二叉树已存在。
二叉树的抽象数据类型第六章 树和二叉树第 39页
(1) Create ( BiTree t )；
生成一棵空二叉树。
(2) BiNodePtr root ( BiTree t )；
若树为空，则返回空函数值 NULL，否则，返回树 t的根结点位置。
(3) BiNodePtr leftchild ( BiNodePtr p,BiTree t );
设 p是 t中的一个结点。若结点 p有左子树，则返回其左子树根结点位置，否则，返回空函数值 NULL。
(4) BiNodePtr rightchild ( BiNodePtr p,BiTree t );
设 p是 t中的一个结点。若结点 p有右子树，则返回其右子树根结点位置，否则，返回空函数值 NULL。
(5) BiNodePtr parent ( BiNodePtr p,BiTree t);
设 p是 t中的一个结点。若结点 p是非根结点，则返回 p的父结点位置，否则，返回空函数值 NULL。
二叉树的抽象数据类型第六章 树和二叉树第 40页
(6) datatype retrieve( BiNodePtr p,BiTree t);
设 p是 t中的一个结点。返回位置为 p的结点的数据元素值。
(7) updata(BiNodePtr p,datatype d,BiTree &t);
设 p是 t中的一个结点。 用新的数据元素值 d取代位置为 p的结点的原先数据元素值 。
(8) BiNodePtr find ( datatype d,BiTree t);
设树中各结点的数据元素值各不相同。若树 t中存在一个数据元素值为 d的结点，则返回该结点的位置，否则，返回空函数值。
(9) Insert ( datatype d,BiTree &t );
在树 t中插入一个数据值为 d的新结点，如在树中已经存在这样一个结点，则不执行插入操作。
二叉树的抽象数据类型第六章 树和二叉树第 41页
(10) deletesub (BiNodePtr &p,BiTree &t );
在树 t中删去以 p为根的整棵子树。如在树 t中不存在这样的结点，则不执行该操作。
(11) Status empty (BiTree t );
若树 t为空则返回 true，否则，返回 false。
(12) preorder(BiNodePtr p,BiTree t )；
对树 t进行前序遍历。
(13) postorder (BiNodePtr p,BiTree t )；
对树 t进行后序遍历。
二叉树的抽象数据类型第六章 树和二叉树第 42页遍历二叉树的概念按一定规律和次序，依照某条搜索路径巡访二叉树中的每一结点,且只访问一次 。在访问每个结点时，可对结点中的数据进行处理，比如打印结点的有关信息，或者做其它指定工作等。
由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因此需要寻找一种规律，以一种合适的方法，使能获得二叉树中各结点信息的 一个线性排列 。
在对二叉树的一些操作中，遍历是一种基本的操作，并且有很多实际的应用。
二叉树的遍历第六章 树和二叉树第 43页已知二叉树是由三个基本单元组成,根结点,左子树 和右子树 。若能依次遍历这三部分，便是遍历了整个二叉树。
D
RL
L(Left)：遍历左子树
D(Directory)：访问根结点
R(Right)：遍历右子树则，总共有 6种遍历方法
DLR,LDR,LRD,DRL,RDL,RLD
二叉树的遍历常用的遍历二叉树的方法（限定,先左后右 ）
先 (根 )序遍历,DLR
中 (根 )序遍历,LDR
后 (根 )序遍历,LRD
第六章 树和二叉树第 44页
D
RL
先 (根 )序遍历,DLR
访问根结点 -> 先序遍历左子树 ->先序遍历右子树中 (根 )序遍历,LDR
中序遍历左子树 -> 访问根结点 -> ->中序遍历右子树后 (根 )序遍历,LRD
后序遍历左子树 -> 后序遍历左子树 -> 访问根结点
A
B
D E
C
F G
H I
先序遍历,ABDHECFGI
中序遍历,DHBEAFCIG
后序遍历,HDEBFIGCA
根
二叉树的遍历第六章 树和二叉树第 45页算法思想,若二叉树为空，则遍历结束，否则首先遍历左子树，接着访问根结点，最后遍历右子树。
算法描述
inorder( BiTree bt )
{ //中序遍历根结点指针为 bt的二叉树
if( bt≠NULL )
{ inorder( bt->lchild );
visit( bt ); //访问根结点 (打印等 )
inorder( bt->rchild );
}
} //inorder
二叉树遍历的递归算法第六章 树和二叉树第 46页栈是实现递归的最常用的结构，所以对于递归定义的二叉树遍历算法，最自然的实现方法是利用一个栈来记下尚待遍历的结点或子树，以备以后访问。
按中序遍历二叉树时，每当遇到一个结点，就将它压入栈中，然后遍历左子树，遍历完这个结点的左子树后，从栈顶弹出这个结点并访问之，然后按照它的
rchild指示的地址，再去遍历这个结点的右子树。
下面先给出用类 C编写的二叉树中序遍历的非递归算法。
二叉树遍历的非递归算法
1) 中序遍历二叉树第六章 树和二叉树第 47页
inorder(btree bt)
//中序遍历 bt所指二叉树,S为存储二叉树结点指针的工作栈
{ InitStack(s); Push(s,bt);
while( !Empty(s))
{ while( GetTop(s) ≠ NULL )
Push(S,GetTop(s)->lchild );
p = Pop(s);
if( !Empty(s))
{ visite(GetTop(s)); //printf(s->data)
P=Pop(s);
Push(s,p->rchild);
}
}
} //inorder 算 法 6.2
二叉树遍历的非递归算法第六章 树和二叉树第 48页如果把关于中序遍历的非递归算法中那个
printf（表示访问根结点并输出有关信息的语句
）移至 p进栈的前面，则可实现二叉树的先序遍历。按先序遍历二叉树时，每当遇到一个结点
，首先访问它，然后将指向该结点的指针压入栈中，再去遍历它的左子树。当整个左子树遍历完毕，就将这个结点从栈中弹出，再去遍历它的右子树。
2) 先序遍历二叉树
二叉树遍历的非递归算法第六章 树和二叉树第 49页问题的提出在对二叉树的一些操作中，遍历是一种基本的操作，并且有很多实际的应用。
遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列
，得到二叉树中结点的先序序列或中序序列或后序序列。这实际上是对一个 非线性结构进行线性化操作,使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个（直接）前趋和（直接
）后继。
当用二叉链表作为二叉树的存储结构时，因为每个结点中只有两个指向其左、右孩子结点的指针域，所以从任一结点出发只能直接找到该结点的左、右孩子信息，而不能直接得到该结点在任一序列中的前趋和后继信息。 某结点在线性序列（先根序列、中根序列或后根序列）中的前趋的后继信息，只有在遍历的动态过程中才能得到。
线索二叉树的基本思想第六章 树和二叉树第 50页在标准形式存储的 n个结点的二叉树中，共有 2n个指针域，除根结点以外的 n-1个结点，每一个结点被一个指针单元指示，故尚有 n+1个指针域的值是 NULL。
存储空间的得用率不够充分。
设想能否得用这些空闲的指针链域来存放结点的前驱的后继的信息。
比如，一棵中序线索二叉树（或称中序穿线树）
就是得用标准形式的二叉树结构中原指针域为 NULL的单元，指向本结点的中序前驱或中序后继，这样，当进行中序遍历二叉树时就不必使用栈了。
线索二叉树的基本思想第六章 树和二叉树第 51页一棵中序线索二叉树
● 实践表示二叉树的树边
● 带箭头的虚线表示线索
● 中序遍历序列 BGDAECF
上图所示为 中序全线索化二叉树
A
B
D
G
C
E F
NULL NULL
线索二叉树的基本思想第六章 树和二叉树第 52页规定：若结点有左（右）子树；则该结点的 lchild(rchild)域指示其左（右）孩子；否则，令 lchild(rchild)域指示其前驱（后继）。为此，
特增加两个标志域 。
线索二叉树的结点结构其中
0,lchild域指示结点的左孩子
1,lchild域指示结点的前驱
0,rchild域指示结点的右孩子
1,rchild域指示结点的后继表示
typedef enum{Link,Thread} PointTag;
typedef struct BiTrNode{
ElemType data;
struct BiTrNode *lchild,*rchild;
PointTag LTag,Rtag;
} *BiTrNodePtr,*BiTrTree;
lchild ltag data rtag rchild
Ltag=
rtag=
线索二叉树的结点结构第六章 树和二叉树第 53页
● 线索链表以上述 加上两个标志域结点结构 作为二叉树的存储结构所构成的二叉链表
● 线索指向结点前驱和后继的指针
●线索二叉树 (threaded binary tree)
加上线索的二叉树
● 二叉树的线索化对二叉树以 某种次序 遍历使其变为线索二叉树的过程
● 遍历线索二叉树在线索二叉树上进行遍历，只要找到序列中的第一个结点，然后依次找结点后继，直至其后继为空时为止。
线索二叉树的几个术语第六章 树和二叉树第 54页以中序线索二叉树 为例示例,表达式 a+b? (c－ d) － (e/f) 的中序线索二叉树示意如下实线：表示树边，实为指向左、右子树的指针虚线：指向前驱的后继的线索中序遍历结果,a+b? c－ d － e/f （中缀表达式）
先序,－ +a?b－ cd/ef （前缀表达式）
后序,abcd －?+ef/ － （后缀表达式）
线索二叉树及其存储结构
－
/
e f
NULL
NULL
＋
a?
b －
c d
中序线索二叉树第六章 树和二叉树第 55页在二叉树的中序线索链表上添加一个 头结点,
线索二叉树及其存储结构
0 1
0 － 0
0 + 0 0 / 0
^ 1 a 1 0? 0 1 e 1 1 f 1 ^
1 b 1 0 － 0
1 c 1 1 d 1
参见图 6.11
lchild指向二叉树的根结点
rchild指向中序遍历访问的最后一个结点令二叉树中序序列中的第一个结点的 lchild
域指针指向头结点令二叉树中序序列中的 最后 一个结点的 rchild
域指针指向头结点第六章 树和二叉树第 56页以中序线索二叉树为例，假定二叉树已按中序线索化，如上页中序线索链表的结构示意图所示。
求结点 n的后继
[分析 ] 设给定结点 n，求其后继结点，送入 x。
(1) 若给定结点 n无右子树 (n->rtag==1),则 n->rchild即为 n的后继
(2) 若给定结点 n有右子树 (n->rtag==0),则其右子树的最左下结点即为其后继 (其 lchild指向结点 n)。
inorder_next (BiTrNodePtr n,BiTrNodePtr &x)
//给定结点 n，求其后继结点，送入 x
{ t = n->rchild;
if( n->rtag==0 )
while( t->ltag==0 ) t = t->lchild;
x=t
} //inorder_next
时间复杂度：在 (1)时，为 O(1)；在 (2)时，为 O(k),k为 n的右子树的最大层次。
在线索二叉树中寻找结点的前趋与后继第六章 树和二叉树第 57页求结点的前驱
[分析 ] 设给定结点 n，求其前趋结点，送入 x。
(1) 若给定结点 n无左子树 (n->ltag==1),则 n->lchild即为 n的前趋
(2) 若给定结点 n有左子树 (n->ltag==0),则其左子树的最后右下结点即为其前驱。
算法描述
inorder_prior(BiTrNodePtr n,BiTrNodePtr &x )
//给定结点 n，求其前趋结点，送入 x
{ t=n->lchild;
if( n->ltag==0 )
while( t->rtag == 0 ) t= t->rchild;
x=t
} //inorder_prior 时间复杂度：同上。
结论,求中序线索二叉树中某结点的后继结点和前驱结点均无困难。
思考,对于先序、后序线索二叉树，求结点的后继结点和前驱结点其困难程度如何？
在线索二叉树中寻找结点的前趋与后继第六章 树和二叉树第 58页
在线索二叉树中寻找结点的前趋与后继
－
/
e f
＋
a?
b －
c d 先序线索二叉树
NULL
找结点的后继结点无困难；
找有左子树结点的前驱结点有困难
（要是无左子树，则 lc hil d 指向其前驱）
为此，须添加指向双亲的指针先序,－ +a?b－ cd/ef
第六章 树和二叉树第 59页二叉树求结点的后继结点及前驱结点的困难程度，
列表如下：
排序类型 无线索表示 线索表示先序
( 1) 找叶结点的后继结点有困难；
( 2) 找所有结点的前驱结点有困难
( 1) 找结点的后继结点无困难；
( 2) 找有些结点的前驱结点有困难中序
( 1) 找无右子树结点的后继结点有困难；
( 2) 找无左子树结点的前驱结点有困难找任何结点的后继结点和前趋结点均无困难后序
( 1) 找所有结点的后继结点有困难；
( 2) 找叶结点的前驱结点有困难
( 1) 找结点的前趋结点无困难；
( 2) 找有右子树结点的后继结点有困难
在线索二叉树中寻找结点的前趋与后继第六章 树和二叉树第 60页
inorder_thlinked(BiTrNodePtr thrt )
//已知 thrt为指向中序双向线索链表中头结点的指针，中序遍历该二叉树
{ p=thrt->lchild；
//指针 p初始化，指向非空二叉树的根结点，二叉树为空时 p=thrt
while(p≠thrt )
{ while( p->ltag==0 ) p=p->lchild; //子树
visite(p)； //访问左子树为空的结点
while (p->rtag==1) && (p->rchild ≠thrt)) //线索
{ p=p->rchild; visite(p); //访问后继结点
}；
p=p->rchild;
}
} //inorder_thinked 算法 6.4
线索二叉树的遍历算法第六章 树和二叉树第 61页二叉树线索化的含义对二叉树以某种次序（比如按中序）遍历使其变成线索二叉树的过程叫做二叉树的线索化。
二叉树线索化的过程是,将二叉树链表每一个结点中原指针域值为 NULL的指针改为指向该结点的前趋结点或后继结点的线索 。然而，
寻找某结点的前驱结点或后继结点的信息只有在对二叉树进行遍历时才能得到,因此线索化的过程即为在对二叉树进行遍历的过程中修改
NULL指针的过程。
二叉树的线索化第六章 树和二叉树第 62页链表生成。对于右二叉树
A
B
D
G
C
E F
设已生成如下之二叉树链表结构
A
∧ B C
D ∧ ∧ E ∧ ∧ F ∧
∧ G ∧
bt
线索二叉树的遍历算法中序遍历生成中序线索链表第六章 树和二叉树第 63页
crt-inthlinked (BiTrNodePtr &thrt,BiTrNodePtr bt )
//已知 bt指向二叉树的根结点，中序遍历生成中序线索链表，
thrt为指向头结点的指针
{ thrt = new(BiTrNode); thrt->ltag=0; thrt->rtag=1;
thrt->rchild=thrt; //建头结点
if( bt==NULL ) thrt->lchild=thrt // 空树
else
{ thrt->lchild=bt; pre=thrt;
inthread(bt); //中序遍历线索化
pre->rchild=thrt;
pre->rtag=1; //最后一个结点线索化
thrt->rchild=pre;
thrt->rtag=1;
}
} //crt_inthlinked 算法 6.5
线索二叉树的遍历算法第六章 树和二叉树第 64页
[分析 ] 这实际上是一个递归的二叉树中序遍历过程，在遍历的过程中建立具有 NULL指针的结点的前驱线索与后继线索 (全线索化 )
算法描述
inthread(BiTrNodePtr p)
//中序线索化以 p为根指针的二叉树
{ if( p==NULL ) return;
inthread (p->lchild)； //左子树线索化
if( p->lchild==NULL )
{ p->ltag=1; p->lchild=pre } //建立前驱线索
if( pre->rchild==NULL )
{ pre->rtag=1; pre->rchild=p }； //建立后继线索
pre=p； //保持 pre指向刚刚访问的结点
inthread(p->rchild)； //右子树线索化
} //inthread 算法 6.6
线索二叉树的遍历算法中序线索化以 p为根指针的二叉树第六章 树和二叉树第 65页一般二叉树的插入、删除操作较为简单，只需解决所插入子树的位置问题，并调整有关结点的链域。然而，若欲在一棵线索二叉树上插入或删除一棵子树，则都会破坏线索。因此，
在修改结点指向孩子结点的指针时,还必须修复线索 。
示例 下面是一棵后序（全）线索二叉树（图中点划线表示省略部分）
A
B
D
G
C
E F
线索二叉树的插入、删除操作第六章 树和二叉树第 66页后序线索二叉树 的插入操作示例 ——AddLChild(BT,y,x)
功能,将以 x为根的子树 （后序线索二叉树）插入到 y所在的二叉树 BT（后序线索二树）中，成为 y结点的左子树 。
约定,(1) x原没有右子树 ； (2) 若 y原有左子树，则该左子树在插入操作之后成为 x的右子树。
算法思想,分四种情况来逐个讨论指针变化的情形，以确保在插入一棵子树之后仍是一棵 后序 线索二叉树。
这四种情况分别为：
(1) y结点是叶结点（终端结点），其左、右链域均为线索；
(2) y结点有左子树而无右子树；
(3) y结点无左子树而有右子树；
(4) y结点既有左子树亦有右子树。
整个算法可以综合以上四种情况而写成。
线索二叉树的插入、删除操作第六章 树和二叉树第 67页情况 1,y结点是叶结点（终端结点），
其左、右链域均为线索 。
现象,在插入以 x为根的子树后，
对后序序列而言，恰好在 y结点和它的前驱结点 pre之间插入了 x的左子树 XL的后序序列和 x结点，使插入后以 y为根的后序序列成为 pre→XL→x→y.
设 rt为指向后序线索链表头结点的指针,函数 first(p)返回以 p为根的二叉树后序序列中的第一个结点的指针 。
链域指针修改状况：
1) p=first(x->lchild); //p指向 x的左子树 XL的后序序列中的第一个结点
2) p->lchild=y->lchild; //XL的前驱指向 y的前驱
3) if( y->lchild->rtag==1 ) y->lchild->rchild=p;
//若 y的前驱有后继线索，则改为指向 XL
4) y->ltag=0; y->lchild=x; //x成为 y的左孩子
5) x->rtag=1; x->rchild=y; //y成为 x的后继
E F
E F
p
pre
pre y
y
x
1)
2)
3)
4)
5)
XL
第六章 树和二叉树第 68页情况 2,y结点有左子树而无右子树现象,按此插入操作的定义，在插入以 x为根的子树作为 y的左子树之前，令 y的左子树为 x的右子树
。则在插入之后，后序遍历 y的左子树应得到的后序序列为 (pre)→XL→YL→x→(y),G
D
D
pre y
y
x
q
G
pre
XL
p1)
1) p=first(x->lchild); //p指向 XL的后序序列中的第一个结点链域指针修改状况：
q 2)
2) q=first(y->lchild); //q指向 YL的后序序列中的第一个结点
3)
3) p->lchild=q->lchild; //XL的前驱指向 YL的前驱
4)
4) if( q->lchild->rtag==1) q->lchild->rchild=p;
//若 YL的前驱有后继线索，则改为指向 XL
5)5) q->lchild=x->lchild; //YL的前驱改为 x的左孩子
6)
6) if( x->lchild->rtag==1) x->lchild->rchild=q;
//若 x的左孩子有后继线索，则改为指向 YL
7)
7) if( y->lchild->rtag==1) y->lchild->rchild=x;
//若 y的左孩子有后继线索，则改为指向 x
9)
8)
8) x->rtag=0; x->rchild=y->lchild; //y的左子树成为 x的右子树
9) y->lchild=x; //x成为 y的左孩子第六章 树和二叉树第 69页情况 3,y结点无左子树而有右子树现象,后序遍历插入之后的以 y为根的子树所得后序序列为 (pre)→XL→x→YR→y,
链域指针修改状况：
1) p=first(x->lchild);
2) q=first(y->rchild);
//p和 q分别指向 XL和 YR的后序序列中的第一个结点
3) p->lchild=q->lchild;
//XL的前驱指向 YR的前驱
4) if( q->lchild->rtag==1)
q->lchild->rchild=p;
//若 YR的前驱有后继线索，
则改为指向 XL
5) q->lchild=x; //x是 YR的前驱
6) x->rchild=q; x->rtag=1; //x的后继是 YR
7) y->ltag=0; y->lchild=x; //x是 y的左孩子
B
D
G
y
pre
q
B
D
G
y
pre
qXL
x
p
3)4)
1)
6)
5)
2)
7)
第六章 树和二叉树第 70页情况 4,y结点既有左子树又有右子树现象,后序遍历插入之后的以 y为根的子树所得后序序列为 (pre)→XL→YL → x→YR→y,
链域指针修改状况：
1) p=first(x->lchild);
2) q=first(y->lchild);
3) r=first(y->rchild);
4) p->lchild=q->lchild;
5) if( q->lchild->rtag==1)
q->lchild->rchild=p;
6) q->lchild=x->lchild;
7) if( x->lchild->rtag==1)
x->lchild->rchild=q;
8) if( y->lchild->rtag==1)
y->lchild->rchild=x;
9) x->rtag=0;
x->rchild=y->lchild;
10) y->lchild=x;
11) r->lchild=x;
B
D
G
y
pre
q
B
D
G
XL
x
4)
5)
p1)
q2)
A
C
E F
r
A
C
E F
y
10)
11)
r
3)
pre
6)
7)
9)
第六章 树和二叉树第 71页注 1,时间 复杂度 O(n),n为插入后的线索化树上的结点数。这是因为从上述对指针变化的描述可见，其时间主要消耗在寻找 y的子树和 x的左树中最左下的叶子结点，在最坏的情况下几乎要遍历整棵树。
注 2,上述耗时最坏情况下和对二叉树进行线索化的时间相当。因此，有时可以先作单纯的插入，即修改孩子指针，然后对插入后的整棵二叉树重新进行线索化。
注 3,关于在线索二叉树上的删除操作，亦同样有修改结点指针的同时需修复线索的问题。
注 4,本课程的重点在于怎样进行二叉树的线索化（以中序线索化为示例），以及如何在一棵线索二叉树中寻找结点的前驱结点与后继结点。
第六章 树和二叉树第 72页
1、双亲链表表示法有多种形式的存储来表示 树 (一般树 )。下面介绍树的三种常用表示法。
在树中，每个结点的双亲是唯一的。利用这一性质，可在存储结点信息的同时，为每个结点附设一个指向其双亲的指针 parent，
就可唯一地表示任何一棵树。
尽管可以用动态链表来实现这种表示法，然而用静态链表更为方便。可使用向量（数组）来存储一棵树的信息。
#define maxnode 1000 //结点数目的最大值
typedef struct tnode{
datatype data; //数据域
int parent; //游标域，指示双亲结点在数组中的下标
} tnode;
typedef struct tree{
tnode nodes[maxnode] ;
int n; //结点数
} ptree;
树 的 存 储 结 构第六章 树和二叉树第 73页示例 1 下图展示一棵树及其双亲表示的静态链表存储结构优点,存储简单，存储密度大，找双亲结点操作
Parent(T,x)容易，亦不难利用反复调用 Parent操作，寻找结点 x的根结点。
缺点,求结点的孩子结点或其他后代结点可能要遍历整个向量。
注,Parent(T,x) 操作可以在常量时间内实现。
A
B C
D E
G IH
F
1
2 3
4 5 6
987
A 0
B 1
C 1
D 2
E 2
F 3
G
H
I
5
5
5
1
2
3
4
5
6
7
8
9
结点序号 data parent
图 6.15 树的双亲链表表示法示例
树 的 存 储 结 构第六章 树和二叉树第 74页为了减少求指定结点的孩子结点时的遍历时间，可以规定孩子结点的下标大于双亲结点的下标，兄弟结点之间的下标从左向右递增。在这样的规定下，求结点 T[i]
的长子结点（最左直接后代结点）的算法描述如下：
int firstchild( ptree t; int i )
//求双亲链表 T中结点 T[i]的长子结点，返回它的位置
{ for( j=i+1; j<= maxnode; j++ )
if( t[j].parent==i )
return(j); //找到 T(i)的长子结点 T[j]
return(0) //未找到
} //firstchild
树 的 存 储 结 构第六章 树和二叉树第 75页
2、孩子链表表示法由于树中每个结点的孩子个数没有限制，若采用多重链表来表示结点及孩子之间的关系时，每个结点内要设置多少个指向其孩子的指针是难以确定的。
设采用多重链表，即每个结点有多个指针域，其中每个指针域指向一棵子树的根结点。
(1) 固定链域格式设树的度为 d，则结点形式为此时，多重链表中的结点是同构的。 由于树中可能有很多结点的度均小于 d，所以链表中有很多空链域 。在一棵有 n个结点且度为 k的树中，其空指针域的数目是
kn-(n-1)=n(k-1)+1
这将造成极大的空间浪费。
data child1 child2 · · · childd
树 的 存 储 结 构第六章 树和二叉树第 76页
(2) 非固定链域格式每个结点按其实际的孩子数设置指针，并在结点内设置度数域
degree，以指出该结点所包含的指针数，结点形式为其中 d为该结点的度。此时，多重链表中的结点是不同构的，各结点不等长。这虽然节省了存储空间,但是给操作带来不便。
(3) 向量 ——链表格式为树中的每一个结点建立一个孩子链表。为了便于查找，可将树中各结点的孩子链表的头结点存放在一个向量中。
degree child1 child2 · · · childddata
树 的 存 储 结 构第六章 树和二叉树第 77页
typedef struct CTNode{
int child;
struct CTNode *Next;
} *ChildPtr;
typedef struct{
ElemType data;
ChildPtr firstchild;
} CTBox;
typedef struct{
CTBox nodes[Max_Node];
int n,r;
}
A
B C
D E
G IH
F
1
2 3
4 5 6
987
树的孩子链表表示法示例
树 的 存 储 结 构
A
B
C
D ∧
E
F ∧
G
H
I
∧
∧
∧
1
2
3
4
5
6
7
8
9
data headptr Child next
2
4
3 ∧
5 ∧
∧6
7 8 9 ∧
优点,存储简单，节省空间，找孩子结点容易。
缺点,求双亲结点困难，
不适用于求
Parent(T,x)操作。
第六章 树和二叉树第 78页
(4) 双亲孩子链表表示法把双亲链表表示法和孩子链表表示法相结合，即将双亲向量和孩子表头指针向量合在一起。
示例 2 承上例树的双亲孩子链表表示法示例
A
B
C
D ∧
E
F ∧
G
H
I
∧
∧
∧
1
2
3
4
5
6
7
8
9
data parent headptr Child next
2
4
6
7
3 ∧
5 ∧
8 9 ∧
0
1
1
2
2
3
5
5
5
树 的 存 储 结 构第六章 树和二叉树第 79页
3,孩子兄弟链表表示法 亦称二叉树表示法或二叉链表示法。
A
B C
D E
G IH
F
1
2 3
4 5 6
987
图 6.15 树的双亲链表表示法示例以二叉树表作树的存储结构。在存储结点信息的同时，附加两个分别指向该结点的第一个孩子和下一个兄弟的指针域
fch (firstchild)和 nsib (next sibling).
typedef struct tnodetp{
elemtype data;
tnodetp *fch,*nsib;
} *forest;
A ∧
B
D∧
C ∧
F∧ ∧
H∧
E ∧
G∧ I∧ ∧
树 的 存 储 结 构第六章 树和二叉树第 80页优点,它和二叉树的二叉链表表示完全一样，
因此可以利用二叉树的算法来实现对树的各种操作
，比如易于实现找孩子结点等的操作。若为每个结点增设一个 parent域，则同样能方便地实现
Parent(T,x)操作。
树 的 存 储 结 构第六章 树和二叉树第 81页结点大小可变
data degree child1 · · · childd
树的存储结构总结：
树 的 存 储 结 构
1、双亲链表表示方法
2、孩子链表表示方法
3、孩子兄弟链表表示方法
1）固定链域格式
2）非固定链域格式
3）向量 -链表格式
4）双亲孩子链表表示法
A 0
B 1
C 1
D 2
E 2
F 3
G
H
I
5
5
5
1
2
3
4
5
6
7
8
9
结点序号 data parent
结点大小固定
data child1 child2 · · · childd
A
B
C
D ∧
E
F ∧
G
H
I
∧
∧
∧
1
2
3
4
5
6
7
8
9
data headptr Child next
2
4
3 ∧
5 ∧
∧6
7 8 9 ∧
A ∧
B
D∧
C ∧
F∧ ∧
H∧
E ∧
G∧ I∧ ∧
A
B
C
D ∧
E
F ∧
G
H
I
∧
∧
∧
1
2
3
4
5
6
7
8
9
data parent headptr Child
next
2
4
6
7
3 ∧
5 ∧
8 9 ∧
0
1
1
2
2
3
5
5
5
第六章 树和二叉树第 82页在树或森林与二叉树之间有一个自然的一一对应关系 。任何一个森林或一棵树可唯一地对应到一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。
1）树与二叉树的转换树中每个结点可能有多个孩子，但二叉树中每个结点至多只能有两个孩子。要把树转换为二叉树，就必须找到一种结点与结点之间至多用两个量说明的关系。
找关系,树中的每个结点最多只有一个最左边的孩子（长子）和一个右邻的兄弟，这就是我们要找的关系。按照这种关系很自然地就能将一棵树转换成与其相对应的二叉树 。
树,森林与二叉树的转换第六章 树和二叉树第 83页树转换成其对应二叉树的方法：
(1) 在所有兄弟结点之间加一连线；
(2) 对每一个结点，除了保留其长子结点的连线外，去掉该结点与其他孩子结点的连线；
(3) 按顺时针方向将树旋转 450。
示例 3
树与二叉树的对应关系示例
A
B C E
D
(1)
A
B C E
D
(2) A
B C E
D
(3) A
B
C
D E
树,森林与二叉树的转换第六章 树和二叉树第 84页注,任何一棵和树对应的二叉树，其右子树必为空示例 4 将下述一棵树转换成其对应的二叉树
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
AB
E
F G
C
D
H I J
(1)
(3)(2)
树,森林与二叉树的转换第六章 树和二叉树第 85页从树的二叉链表表示的定义可知，任何一棵和树相对应的二叉树，
由于树根没有兄弟，故当将要转换为其对应二叉树后，该二叉树的根结点的右子树必为空。 对于森林，若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟,则同样可以导出森林和二叉树之间的对应关系示例 5 将下述森林转换成其对应的二叉树：
图 6.19 森林与二叉树的对应关系示例
2）森林与二叉树的对应关系
A
B C D F
E G
H
J
I A
B
G
H
I
C
D
E
F
J
树,森林与二叉树的转换
J
A
B C D
E
F
G
H I
=>
第六章 树和二叉树第 86页二叉树转换成其对应的树或森林的方法：
(1) 若结点 x是其双亲 y的左孩子,则把 x的右孩子、右孩子的右孩子,…
都与 y用连线连起来；
(2) 去掉所有双亲到右孩子的连线。
示例 6
A
B C
E F
E G
H
J
I
A
B
G
H
I
C
D
E
F
J
A
B
G
H
I
C
D
E
F
J
树,森林与二叉树的转换
A
B
G
H
I
C
D
E
F
J
第六章 树和二叉树第 87页
3）森林与二叉树相互转换的形式定义森林转换成二叉树设 F={T1,T2,···,Tm}表示由树 T1,T2,···,Tm组成的森林，则与森林 F
相对应的二叉树 B(root,LB,RB)
(1) 若 F为空 (m=0)，则 B(F)为空的二叉树；
(2) 若 F非空 (m>0)，则 B(F)的根 root就是 F中第一棵树 T1的根
Root(T1)； B(F)的左子树 LB是 B(T11,T12,···,T1m1)，其中 T11,T12,··,T1m1
是 Root(T1)的子树森林； B(F)的右子树 RB是 B(T2,T3,···,Tm)。
由于上述定义中 B(T11,T12,···,T1m1)和 B(T2,T3,··,Tm)分别是森林
{T11,T12,···,T1m1}和 {T2,T3,··,Tm}所对应的二叉树，故可 递归 地应用 (1)
和 (2)来将其转换为二叉树。
树,森林与二叉树的转换第六章 树和二叉树第 88页二叉树转换成森林设 B=(root,LB,RB)是一棵二叉树，则可按如下规则转换成森林 F={T1,T2,···,Tm}：
(1) 若 B为空，则 F亦为空；
(2) 若 B非空，则 F中第一棵树 T1的根 Root(T1)即为二叉树 B
的根 root； T1为根结点的子树森林 F1是由 B的左子树 LB转换而成的森林 ； F中除 T1之外其余树组成的森林 F`=(T2,T3,···,Tm)是 由 B
的右子树 RB转换而成的森林。
这亦是一个递归定义。
由上述森林转换成二叉树以及二叉树转换成森林的递归定义，可以写出相应的递归算法。同时,森林和树的操作可通过将其转换成二叉树，籍助于二叉树的操作来实现 。
树,森林与二叉树的转换第六章 树和二叉树第 89页
1）树的遍历先根遍历树 T
若树 T非空，则
(1) 访问树 T的根结点 R；
(2) 依次先根遍历根 R的每棵子树 T1,T2,···,Tm。
对上述的树进行先根遍历，可得该树的先根序列为
ABCDE
在 二叉树 中，可以有先根（序）遍历、中根（序）遍历后根（序）遍历，而在树和森林中，由于一个结点可以有两棵以上的子树,不便讨论它们的中根次序遍历,因为无法明确给出根与这些子女间的次序。但仍然可以研究先根次序和后根次序的遍历。
A
C
D
EB
树和森林的遍历第六章 树和二叉树第 90页后根遍历树 T
若树 T非空，则
(1) 依次后根遍历根 R的每颗子树 T1,T2,···,Tm； (2) 访问根结点。
对上述的树进行后根遍历,可得该树的后根序列为 BDCEA
先根遍历树 T,ABCDE
后根遍历树 T,BDCEA
先根 遍历二叉树 T`,ABCDE
中根 遍历二叉树 T`,BDCEA
A
C
D
EB
A
B
C
D E
转换成对应的二叉树
树和森林的遍历值得注意的是,先根遍历一棵树，恰好等价于先根遍历该树所对应的二叉树；后根遍历一棵树，恰好等价于中根遍历该树所对应的二叉树。
树的遍历与二叉树遍历之间的关系第六章 树和二叉树第 91页按照森林和树相互递归的定义，可以推出森林的两种遍历方法。以如下一次森林为示例来进行说明。
先根遍历森林若森林非空，则
(1) 访问森林中第一棵树的根结点；
(2) 先根遍历第一棵树中根结点的子树森林 （递归） ；
(3) 先根遍历除第一棵树外其他树构成的森林 （递归） 。
对上述的森林进行先根遍历，可得该森林的先根序列为？
A
B C D F
E G
H
J
I
2）森林的遍历
树和森林的遍历
A B C D E F G H I J
问题,后根遍历森林任何描述？后根序列？ B C D A F E H J I G
第六章 树和二叉树第 92页后根遍历森林若森林非空，则
(1) 后根遍历森林中第一棵树的根结点的子树森林；
(2) 访问第一棵树的根结点；
(3) 后根遍历除第一棵树外其它树构成的森林。
简言之,先根遍历森林是从左到右依次按先根次序遍历森林中的每一棵树，后根遍历森林则是从左到右依次按后根次序遍历森林中的每一棵树 。
与遍历树相类似，先根遍历森林等同于先根遍历森林所对应的二叉树；后根遍历森林等同于中根遍历该森林所对应的二叉树。
这主要是由森林到二叉树的转换方法所决定的，因为森林中第一棵树对应到二叉树的根和左子树，其它树构成的森林对应到二叉树的右子树。
树和森林的遍历第六章 树和二叉树第 93页示例 7 设有如下森林 F E
F G H
I
A
B
D
C
1,将它转换成对应的二叉树；
2,写出该森林按先根遍历和后根遍历所得的先根序列和后根序列
。
解：
J
E
F G H
I
A
B
D
C
J
A
B
F
I
C
D
E
G
J H先根序列 ABCDEFIGJH
后根序列 BDCAIFJGHE
树和森林的遍历第六章 树和二叉树第 94页结论：两个结论结论一,先根遍历森林是从左到右依次按先根效率遍历森林中的每一棵树，后根遍历森林则是从左到右依次按后根次序遍历森林中的每一棵树。
结论二,当用二叉链表作为树和森林的存储结构时，树和森林的先根遍历和后根遍历可分别用与该树和森林相对应的二叉树的先根遍历和中根遍历算法实现。
树和森林的遍历第六章 树和二叉树第 95页
1）基本术语树中两结点之间的路径从树中一个结点到另一个结点之间的分支。
树中两结点之间的路径长度从树中一个结点到另一个结点之间的路径上的分支数目。
树的路径长度从树 根 到树中每一结点的路径长度之和。
最优二叉树（哈夫曼树）
A
B
D E
C
F G
H I
第六章 树和二叉树第 96页示例 8 求下列四棵二叉树的路径长度
1
2
4
3
5
6 7
1
2
4
3
5 6 7
1
2 3
4 5
6 7
1
2
3
4
5
6
7
(1) (2) (3) (4)
[解 ] (1) 1+1+2+2+3+3=12
(2) 1+1+2+2+2+2=10
(3) 1+1+2+2+3+3=12
(4) 1+2+3+4+5+6=21
注,结点数目相同的二叉树,完全二叉树 的路径长度最短。
最优二叉树（哈夫曼树）
第六章 树和二叉树第 97页在许多应用中，常常将树中结点赋予一个有某种意义的实数，称为该结点的 权 。
结点带权的路径长度该点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度树中所有 叶结点 的带权路径长度之和，记作其中 n表示该树中 叶结点 的数目,wk和
lk(k=1,2,··,n)分别表示叶结点 ik的权值和从树根到叶结点 ik之间的路径长度。
最优二叉树（哈夫曼树）
第六章 树和二叉树第 98页示例 9 求下列三棵二叉树的带权路径长度，设它已知叶结点 a,b,c,d的权值分别为 7,5,2,4.
图 6.24具有不同带权路径长度的二叉树
[解 ] (1) WPL=7× 2+5× 2+2× 2+4× 2=36
(2) WPL=4× 2+7× 3+5× 3+2× 1=46
(3) WPL=7× 1+5× 2+2× 3+4× 3=35
问：具有 a,b,c,d4个叶结点的二叉树中，哪一种树其带权路径长度为最小？又，带权路径长度为最小的二叉树是否唯一？
a b c d7 5 2 4 d 4
a b
7 5
c
2 a 7
b
5
c d
2 4
(2) (3)(1)
最优二叉树（哈夫曼树）
第六章 树和二叉树第 99页定义 在权为 w1,w2,··,wn的 n个 叶结点 的所有二叉树中，带权路径长度最小的二叉树称为 最优二叉树或哈夫曼 (Huffman)树 。
上述三棵具有 4个叶结点 a,b,c,d且 分别带权 7,5,2,4的二叉树中，第三棵二叉树的 MPL最小。它是否一棵哈夫曼树呢？可以验证，它就是一棵哈夫曼树。
由上例可看出，在叶结点数目及权值相同的二叉树中,完全二叉树不一定是最优二叉树 。一般情况下
,在最优二叉树中，权值越大的叶结点离根结点越近
。
示例 哈夫曼树的简单应用 ——获得最佳判定算法。
问题：编制一个将百分制转换成五级分制的程序。
最优二叉树（哈夫曼树）
第六章 树和二叉树第 100页可用如下语句实现：
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`;
判定树
a
a<60
a<70
a<80
a<90
不及格中 等优 秀 良 好及 格
Y
Y
Y
Y
N
N
N
N
设学生成绩在五个等级的分布规律如下：
分 数 0~59 60~69 70~79 80~89 90~100
比例数 5% 15% 40% 30% 10%
80%以上的数据（ 70~100分）需进行三次或三次以上的比较才能得出结果。
第六章 树和二叉树第 101页在判定树 b中，每个判定框都有两次比较。今将这两次比较分开，
即可进一步得如下所示的判定树今尝试构造一棵有五个叶结点的哈夫曼树，即 按权值高者靠近根结点,以便使得大部分的数据经过 较少的比较次数 即可得出结果。得到如下之判定树
70≤a<80
80≤a<90
60≤a<70
a<60
中 等良 好及 格不及格 优 秀
Y
Y
Y
Y
N
N
N
N
判定树
b
第六章 树和二叉树第 102页
a<80
a<70 a<90
a<60
不及格 及 格 中 等 良 好 优 秀
Y
Y
Y N
NN Y
N
判定树 C计算 WPL
判定树 a
5× 1+15× 2+40× 3+30× 4+10× 4=315
判定树 b
40× 1+30× 2+15× 3+5× 4+10× 4=205（但每个判定框有两次比较）
判定树 c
5× 3+15× 3+40× 2+30× 2+10× 2=220
最优二叉树（哈夫曼树）
第六章 树和二叉树第 103页哈夫曼算法思想哈夫曼给出了一个精巧和、构造最优二叉树的方法，称为哈夫曼算法。其算法思想是：
(1) 根据给定的 n个权值 {w1,w2,···,wn}构成 n棵二叉树的集合
F={T1,T2,···Tn}，其中每棵二叉树 Ti(i=1,2,···,n)中只有一个带权为
wi的根结点，其左、右子树均为空；
(2) 在 F中选取两棵根 结点的权值最小的树作为左、右子树构造一棵新的二叉树，新树的根结点的权值为其左、右子树上根结点的权值之和；（进一步规定轻的在左边）
(3) 在 F中删除这两棵树，同时将新得到的二叉树加入 F中；
(4) 重复 (2)和 (3)，直到 F只含一棵树为止。这棵树便是哈夫曼树。
构造最优二叉树第六章 树和二叉树第 104页示例 1 构造一棵叶结点为 a,b,c,d且其权值分别为 7,5，
2,4的哈夫曼树。
a b c d
7 5 2 4步骤 1
a b
7 5步骤 2
d
6
4
c
2
a
7步骤 3 11
6
b
5
d
4
c
2
步骤 4 18
11
a
7
6
b
5
dc
2 4
图 6.26 哈夫曼树的构造过程
构造最优二叉树第六章 树和二叉树第 105页由哈夫曼算法可知，
(1)初始森林中共有 n棵二叉树，每棵树中都有仅有一个孤立的结点，它们既是根结点，又是叶结点。
(2)算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树。每合并一次，森林中就减少一棵树。
(3)显然，总共要进行 n-1次合并，才能使森林中的二叉树的数目，由 n棵减少到只剩下一棵最终的哈夫曼树。并且每次合并，都要产生一个新结点，显然它们都是具有两个孩子结点的分支结点。
(4)由此可知,最终求得的哈夫曼树中共有 2n-1个结点,其中 n
个叶结点是初始森林中的 n个孤立结点，并且哈夫曼树中 没有度数为 1的分支结点 。称这类树为 严格和（或正则的）二叉树 。
哈夫曼树的存储结构第六章 树和二叉树第 106页设哈夫曼树共有 n个叶结点。哈夫曼树中任一结点的度为 0或 2。
由 二叉树性质 3，二叉树的终端结点数等于度为 2的结点数加 1，即
n0=n2+1，
故有
n2=n0-1=n-1；
而总结点数为总结点数 =n0+n2 =n+(n-1) =2n-1.
哈夫曼树的存储结构：由于哈夫曼树的结点数据固定，
故可使用向量来存储并模拟一棵哈夫曼树 。
哈夫曼树的存储结构第六章 树和二叉树第 107页
typedef struct nodetype{
int weight； //或 float
int parent,lch,rch;
} *htnodeptr;
typedef nodetype[maxnode] huftree;
其中,weight：结点的权值,lch,rch：结点的左、右孩子在向量中的下标。若是叶结点，则这两个指针值均为 0
parent：结点双亲在向量中的下标。若 parent的值为 0，则表示该结点是无双亲的根结点，否则是非根结点。
哈夫曼树的存储结构第六章 树和二叉树第 108页构造哈夫曼树的算法可粗略描述如下：
(1) 将哈夫曼树向量（类型为 huftree）中的 2n-1个结点初始化，即将各结点中的三个指针和权值均置为 0；
(2) 将 n个权值 w[i](i=1,2,··,n)放入向量 ht的前 n个分量中
，它们是初始森林中的 n个孤立的根结点上的权值；
(3) 对森林中的树进行 n-1次合并，共产生 n-1个新结点
，依次放入向量 ht的第 i(n+1≤i≤m)个分量中。
哈夫曼算法描述第六章 树和二叉树第 109页
huffman( huftree ht,int *w,int n )
//构造哈夫曼树。 W中存放 n个叶结点的权值,ht表示哈夫曼树
{ for( i=1; i <= m; i++ )
{ ht[i].parent=0;
ht[i].lch=0;
ht[i].rch=0
}; //初始化
for( i=1; i <= n; i++ )
ht[i].weight = w[i]; //初始化
for( i=n+1; i <= m; i++ )
//构造哈夫曼树，共进行 n-1次合并，产生 n-1个新结点
{ s1 = s2 = 0; sm1 = max; sm2 = max;
//以上是为找两个权值最小的根结点作初始化,max是机器允许的最大数
for( j=1; j <= i-1; j++ )
//在当前森林的所有 i-1个结点中选出两个最小权值的根结点
哈夫曼算法描述第六章 树和二叉树第 110页
if( ht[j].parent == 0 ) //第 j个结点是根结点
if( ht[j].weight < sm1 )
//改变最小权 sm1和次小权 sm2及它们所对应的位置 s1和 s2
{ sm2 = sm1; sm1 = ht[j].weight;
s2 = s1; s1 = j;
}
else //ht[j].weight≥sm1
if( ht[j].weight < sm2 ) //改变次小权 sm2及位置 s2
{ sm2 = ht[j].weight; s2 = j };
//以下是合并
ht[s1].parent = i; ht[s2].parent = i;
ht[i].lch = s1; //最小权的根结点是新结点的左孩子
ht[i].rch = s2; //次小权的根结点是新结点的右孩子
ht[i].weight = ht[s1].weight + ht[s2].weight
} //FOR i
} //huffman
哈夫曼算法描述第六章 树和二叉树第 111页什么是哈夫曼编码哈夫曼算法的应用很广泛，联系到不同的计算机算法，可以赋予带权路径长度不同的含义。例如，外部排序中常使用哈夫曼算法来确定一个最佳合并次序。
哈夫曼算法的一个重要应用是哈夫曼编码，即应用于数据通信的二进制编码中。
在电报通信中，电文是以二进制的 0,1序列传送的。在发送端，
需要将电文中的字符转换成二进制的 0,1序列（编码），在接收端，
则要将收到的 0,1串转化为对应的字符序列（译码）。
哈夫曼编码第六章 树和二叉树第 112页问题,字符集中的字符被使用的频率是非均匀的，如
E,T较 Q,Z的使用频率要高得多。
如何能让使用频率高的字符的编码尽可能地短，从而使传送电文的总长度亦尽可能地短
？
哈夫曼编码最简单的编码方式是等长编码。
例如，设电文是由英文大写字母组成，其编码集合为 {A,B
,···,Z},等长二进制编码可采用每个字符用 5位二进制位串表示
(25>26),而可获得对应的文字。
第六章 树和二叉树第 113页什么是哈夫曼编码
哈夫曼编码
A – 00
B – 01
C – 10
D – 11
ABACCDA 00010010101100
ABACCDA 000011010
BBCCDA BADDA
示例：编码方式第一种
A – 0
B – 00
C – 1
D – 01
第二种
A – 0
B – 10
C – 110
D – 111
第三种
ABACCDA 01001101101110
能正确译出不能正确译出能正确译出第六章 树和二叉树第 114页可以使用二叉树来设计二进制的前缀编码。
示例 3 对于下述一棵二叉树，其四个叶结点分别表示
A,B,C,D四个字符,且约定左分支表示字符 `0`，右分支表示字符 `1`。 则可以从根结点到叶结点的路径上分支字符组成的字符串作为该叶结点字符的编码：
前缀编码：
A,0
B,10
C,110
D,111
A
D
1
B
C
1
1
0
0
0
哈夫曼编码若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。称这种编码为 前缀编码 或简称 前缀码 。
显然,等长编码是前缀码 。
什么是哈夫曼编码第六章 树和二叉树第 115页设计电文总长最短的二进制前缀编码即为以 n种字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码便称为 哈夫曼编码 。
struct nodetype{
int weight;
int parent,lch,rch; //0..m
};
struct codetype{ //字符的编码
char bits[n+1];
int start;
};
nodetype huftree[m];
codetype hufcode[n];
什么样的前缀码才能使得电文总长为最短？
哈夫曼编码的算法描述第六章 树和二叉树第 116页
huffman_code ( int w[n],huftree &ht,hufcode &hcd )
//w中存放 n个字符的权值,ht表示哈夫曼树,hcd存放 n个字符的哈夫曼编码
for( i=1; i<=n; i++ ) //求哈夫曼编码
{ cd.start = n;
//cd为 codetype型的变量； start表示编码开始的前一位置
c = i; f = ht[c].parent;
while( f ≠ 0 )
{ if( ht[f].lch == c )
cd.bits[cd.start] = 0
else cd.bits[cd.start] = 1;
cd.start--;
c = f; f = ht[f].parent;
};
hcd[i].bits[1..n-start] = cd[start+1...n]
}
} //huffman_code
{ huffman (ht,w); //建哈夫曼树
哈夫曼编码的算法描述
A
D
1
B
C
1
1
0
0
0
011
start
C
第六章 树和二叉树第 117页例 6-2 已知某系统在通信联络中只可能出现八种字符，其频率分别为 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，
试设计哈夫曼编码。
[分析 ] 设权值 w=(5,29,7,8,14,23,3,11).
n=8,m=2n-1=15,初始森林
哈夫曼编码的算法描述第六章 树和二叉树第 118页
w e i g h t p a r e n t l c h r c h
1 5 0 0
2 29 0 0
3 7 0 0
4 8 0 0
5 14 0 0
6 23 0 0
7 3 0 0
8 11 0 0
9
10
11
12
13
14
15
构建哈夫曼树
(b) ht的终态
d2
d1
d4
d3
d6
d5
d7
d8
哈夫曼编码的算法描述
(a) ht的初态
8 7 1
9
9
14
58 2 12
14
15 3 4
10
10
19 9 8
11
11
29 5 10
12
12
42 11 6
13
13
100 13 14
15
15
第六章 树和二叉树第 119页
d2
d4
1
d5
d3
1
1
0
0
1
d7
d6
d8
d1
1
0
0
0
0 1
100
42
19
8
35
7 8
15
29
58
29
14
f=0
f=15
f=13
f=11
f=9
c=1
哈夫曼树例 6-2 的哈夫曼树
23
11
0
1
2
3
4
5
6
7
8
0110
10
1110
1111
110
01111
010
00
1
第六章 树和二叉树第 120页可将编码表列表表示如下用累加各个代码的长度乘以字符出现的频率，求得平均代码长度为
AVG=4× 0.05＋ 2× 0.29＋ 4× 0.07
＋ 4× 0.08＋ 3× 0.14＋ 2× 0.23＋ 4× 0.03＋ 3× 0.11
=2.71
故它比固定长度的代码要好些。它具有的另一个重要优点是：当收到前缀码的一个序列后，仅仅只有一种译码的方法，从而不会因码的多义性而不知所措。
字 符 频 率 前缀编码
d 1 0,0 5 0 1 1 0
d 2 0,2 9 1 0
d 3 0,0 7 1 1 1 0
d 4 0,0 8 1111
d 5 0,1 4 1 1 0
d 6 0,2 3 0 0
d 7 0,0 3 0 111
d 8 0,1 1 0 10
固定代码 23=8.
AVG=3 但若有 9个值，则需 AVG=4而哈夫曼编码仍可能在小于 3之列第六章 树和二叉树第 121页一棵哈夫曼树编码树同时也是一棵 译码树 。收到的任一长度的码序列，可以被翻译成唯一的字符序列。可以让收到的二进制位信息序列从树根开始“流”下去，
每一位选择一条树的分枝，若位为 0时流向左分枝，为
1时流向右分枝。每到达一个叶结点时，就截取一个代码组，并译出一个相应字母，然后再回到根结点，重复译码过程，直至信息流变空为止。
哈夫曼编码的算法描述有什么缺点？
当在传送过程中若有一位发生了差错，那么其后的所有内容是否还能正常译出？
第六章 树和二叉树第 122页示例 2 （八枚硬币问题） 假定有八枚硬币 a,b,c,d,e,f,g,h，其中有一枚硬币是伪造的。真伪硬币的区别仅在于重量上有所不同，伪币可能比真币重，亦可能比真币轻。但真币均一般重。
今要求以天 平 为工具，用最少的比较次数挑出伪造硬币，并确定它比真币重或是轻。
[分析 ] 可经过三次用天平称重比较，即能获得所需结果。其方法可以用如下页之判定树来表示。
树的应用判定树第六章 树和二叉树第 123页
a+b+c? d+e+f
a+d? b+e a+d? b+eg? h
b?a c?a b?a g?a h?a b?a c?a b?a
> = <
< < <> > >= =
======
= =>
> > > ><<<
今仅分析其中一类情况。
设第一次称重有 a+b+c<d+e+f。可知伪币应在这六枚之中，即 g,h必是真币。
设第二次称重有 a+d<b+e。此时，由于交换了 b和 d的位置，而不等式仍然成立，故知,1,c,f均是真币； 2,b,d均是真币。从而可知,a,e中必有一枚是伪币。
设第三次称重有 b=a，则知 e是伪币，且 a较真币为重。
若第三次称重有 b>a，则知 a是伪币，且 a较真币为轻。
同理可以获得各种结论。
a-H e-L
c-H f-L
b-H d-L g-H h-L h-H g-L d-H b-L f-H c-Le-H a-L
注,H–Heavy L–Light
第六章 树和二叉树第 124页博弈树树形结构的另一个有趣的应用是在人机对奕的下棋程序中。
如象棋、跳棋的二人游戏等。今举一个示例以说明什么是博亦树
（比赛树）。
示例 3 （取牙签比赛）假定有 n根牙签，由 A,B两人交替地把这些牙签拿走，并规定：每次只能拿 1根或 2根或 3根牙签，不允许 1根也不拿，亦不允许多拿。拿最后一根牙签者判输。
[分析 ] A,B两个轮流拿牙签可以比拟成两个人轮流下棋，
棋盘即为游戏板。在任何时候游戏板的状态，由这堆牙签中所剩下的牙签数确定。
一个游戏板的状态序列 C1,C2,···,Cm 是有效的，需满足下列诸条件：
1) C1是游戏开始状态；
2) Ci(o<i<m)是非结束状态；
3) 如果 i是奇数，则由 A作合法移动，状态从 Ci 到 Ci+1；若 i是偶数，则由 B作合法移动，状态亦由 Ci 到 Ci+1。
如果 Cm是终结状态，则 C1,C2,···,Cm就构成一局比赛游戏
。
二叉树的应用第六章 树和二叉树第 125页一个有限的游戏
（比赛），可由博弈树（比赛树）来表示各种可能的情况。
为确定 A从某个状态拿几根牙签，使用估值函数 E(x)
+1，当 x是 A的一个获胜状态时
–1，当 x是 A的一个失败状态时应用这个估值函数，当 A移动到下一个状态（三种,b,c
或 d）时，应当选择
{V(b),V(c),V(d)}
中之最大值，其中 V(x)为状态 x的值。
注,剩余牙签树就是状态。
根到叶子的路径就是一局比赛。
E(x)=
| | | |
| | || | |
| | | |B B B
| AAA
B
1 2 3
a
b c d
1 2 3 1 2
21
-1 -1 +1
-1-1+1 -1
,B移动前状态
,A移动前状态
二叉树的应用第六章 树和二叉树第 126页问题：具有 n个结点的不同形态的树共有多少棵？
以讨论二叉树为示例，然后可将结论推广到一般树
。
定义 1 若已知两棵二叉树 T 和 T` 皆为空树，或皆不空且 T 的左、右子树和 T` 的左、右子树分别相似，
则称二叉树 T 和 T` 相似。
定义 2 若已知两棵二叉树 T 和 T` 相似，而且所有对应结点上的数据元素均相同，则称二叉树 T 和 T` 等价。
二叉树的计数问题就是讨论具有 n个结点、互不相似的二叉树的数目 bn。
树的计数第六章 树和二叉树第 127页
n=0,b0=1 （空树）
n=1,b1=1,只有一个根结点的树
n=2,b2=2,其形态分别为
n=3,b3=5,其形态分别为
n>3,bn=?
一般情况下，一棵具有 n(n>1)个结点的二叉树可以看成是由一个根结点、一棵具有 i个结点的左子树，和一棵具有 n-i-1个结点的右子树所组成，如下图所示根
(0≤i≤n-1)
第六章 树和二叉树第 128页结论
1,具有 n个结点、互不相似的二叉树的数目 bn可由下列之递推公式求得
2,具有 n个结点、互不相似的二叉树的数目 bn为注,
1,
1
1
0
1
0
nbbb
b
n
i
inin
.11 2n nn Cnb
14
)!48(!4
!8
5
1
5
1
,4
5
)!36(!3
!6
4
1
4
1
,3
2
)!24(!2
!4
3
1
3
1
,2
1
)!12(!1
!2
2
1
2
1
,1
1
1
1
,0
4
84
3
63
2
42
1
21
0
00
Cbn
Cbn
Cbn
Cbn
Cbn
第六章 树和二叉树第 129页从二叉树的遍历可知，任意一棵二叉树结点的前序遍历序列和中序遍历序列均是唯一的。现问：
若给定结点的前序遍历序列和中序遍历序列，能否据此唯一地确定一棵二叉树？
有如下之结论结论 由一棵二叉树的前序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。
还有下列两个推论推论 1 由一棵二叉树的后序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。
推论 2 由一棵二叉树的前序遍历序列和后序遍历序列，不能唯一确定这棵二叉树。
关于二叉树的确定第六章 树和二叉树第 130页为推论 2举一示例设已知某二叉树的前序遍历序列和后序遍历序列分别为前序遍历序列,AB
后序遍历序列,BA
则有可能是下述两棵二叉树中之一前序遍历序历,AB 前序遍历序列,AB
后序遍历序列,BA 后序遍历序列,BA
A
B
A
B
关于二叉树的确定第六章 树和二叉树第 131页例 6-5 已知结点的前序遍历序列和中序遍历序列分别为前序遍历序列,ABCDEFG
中序遍历序列,CBEDAFG
试构造据此唯一确定的二叉树。
[解 ] 第一步：由前序遍历序列知，二叉树的根为 A，而由中序遍历序列知，该二叉树的左子树的中序遍历序列为 CBED，又右子树的中序遍历序列为 FG。从而可推知其左子树的前序遍历序列必为 BCDE，而右子树的前序遍历序列必为 FG。故可得第二步：类似地处理左子树部分，可分解出根 B，以及其左子树
、右子树部分
A
关于二叉树的确定
C
B
E
D
F
G
第六章 树和二叉树第 132页
A
B
C
第三步：进一步分解出根结点 D及其左、右树部分
A
B
C D
E
第四步：最后分解出 A的右子树中的根 F及其左、右子树部分
A
B
C D
E
F
G
第六章 树和二叉树第 133页递归过程算法描述
preinorder (bt,P,M);
//P——先序遍历序列 M——中序遍历序列
{ bt=P[1];
i=1;
while( M[i]≠P[1] ) i++;
bt->lchild = M[1..i-1];
bt->rchild = M[i+1..n];
if( bt->lchild≠NULL )
preinorder (bt->lchild,P[2..i],M[1..i-1]);
if( bt->rchild≠NULL )
preinorder (bt->rchild,P[i+1..n],M[i-1..n])
} //preinorder
关于二叉树的确定第六章 树和二叉树第 134页第六章 树和二叉树小结这一章是本门课程内容中的一个重点内容提要
● 树的结构定义和基本操作
● 二叉树的定义、基本操作、性质和存储结构
● 二叉树的遍历和线索化
● 树、森林与二叉树的转换
● 树和森林的遍历
● 哈夫曼树与哈夫曼编码
● 树的其他应用 —— 表达式求值、判定树、博奕树、树的计数、二叉树的确定等第六章 树和二叉树第 135页学习要点
● 熟悉树和二叉树的递归定义、有关的术语及基本概念
● 熟练掌握二叉树的结构特性，了解其相应的证明方法
● 熟悉二叉树的各种存储结构的特点及适用范围
● 熟练掌握二叉树各种次序的遍历算法，了解遍历过程中栈的状态
● 了解二叉树的线索化及其实现，掌握在中序线索化树上寻找给定的前驱和后继的方法
● 熟练掌握树、森林与二叉树之间的转换方法
● 了解最优二叉树即哈夫曼树的特性，掌握建立最优二叉树和哈夫曼编码的方法
● 了解树的其他各种应用
