第 7章 树形结构
7.1 树的基本概念
7.2 二叉树概念和性质
7.3 二叉树存储结构
7.4 二叉树的遍历
7.5 二叉树的基本运算及其实现
7.6 二叉树的构造
7.8 哈夫曼树本章小结
7.7 线索二叉树
7.1 树的基本概念
7.1.1 树的定义
7.1.3 树的基本术语
7.1.2 树的表示
7.1.4 树的性质
7.1.5 树的基本运算
7.1.6 树的存储结构
7.1.1 树的定义形式化定义：
树,T＝ {K,R}。 K是包含 n个结点的有穷集合
(n>0),关系 R满足以下条件,
（ 1） 有且仅有一个结点 k0∈ K,它对于关系 R来说没有前驱结点,结点 k0称作树的根 。
（ 2） 除结点 k0外,K中的每个结点对于关系 R来说都有且仅有一个前驱结点 。
（ 3） K中每个结点对于关系 R来说可以有多个后继结点 。
递归定义：
树是由 n（ n≥0） 个结点组成的有限集合 （ 记为
T） 。 其中,
如果 n=0,它是一棵空树,这是树的特例；
如果 n>0,这 n个结点中存在 （ 有仅存在 ） 一个结点作为树的根结点,简称为根 （ root）,其余结点可分为 m （ m>0） 个互不相交的有限集 T1,,T2,…,
Tm,其中每一棵子集本身又是一棵符合本定义的树,
称为根 root的子树 。
7.1.2 树的表示
（ 1） 树形表示法 。 这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象 。 下图就是采用这种表示法 。
A
C
G
J
B
E
D
F I H
M K L
树形表示法
（ 2） 文氏图表示法 。 使用集合以及集合的包含关系描述树结构 。 下图就是树的文氏图表示法 。
H
L
D
K I
M
C
G
J
E
B
F
文氏图表示法
A
（ 3） 凹入表示法 。 使用线段的伸缩描述树结构 。 下图是树的凹入表示法 。
（ 4） 括号表示法 。 将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构 。 下图是树的括号表示法 。
7.1.3 树的基本术语
1,结点的度与树的度：树中某个结点的子树的个数称为该结点的度 。 树中各结点的度的最大值称为树的度,通常将度为 m的树称为 m次树或 m叉树 。
2,分支结点与叶结点：度不为零的结点称为非终端结点,又叫分支结点 。 度为零的结点称为终端结点或叶结点 。 在分支结点中,每个结点的分支数就是该结点的度 。 如对于度为 1的结点,其分支数为
1,被称为单分支结点；对于度为 2的结点,其分支数为 2,被称为双分支结点,其余类推 。
3,路径与路径长度：对于任意两个结点 ki和 kj，
若树中存在一个结点序列 ki,ki1,ki2,…,kin,kj，
使得序列中除 ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由 ki到 kj的一条路径,用路径所通过的结点序列 (ki,ki1,ki2,…,kj)表示这条路径 。 路径的长度等于路径所通过的结点数目减 1
（ 即路径上分支数目 ） 。 可见,路径就是从 ki出发
,自上而下,到达 kj所通过的树中结点序列 。 显然,
从树的根结点到树中其余结点均存在一条路径 。
4,孩子结点,双亲结点和兄弟结点：在一棵树中,
每个结点的后继,被称作该结点的孩子结点 （ 或子女结点 ） 。 相应地,该结点被称作孩子结点的双亲结点 （ 或父母结点 ） 。 具有同一双亲的孩子结点互为兄弟结点 。 进一步推广这些关系,可以把每个结点的所有子树中的结点称为该结点的子孙结点,从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点 。
5,结点的层次和树的高度：树中的每个结点都处在一定的层次上 。 结点的层次从树根开始定义,
根结点为第一层 （ 有的教材从第 0层开始 ）,它的孩子结点为第二层,以此类推,一个结点所在的层次为其双亲结点所在的层次加 1。 树中结点的最大层次称为树的高度 （ 或树的深度 ） 。
7,有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则称为有序树,否则称为无序树 。
7,森林,n（ n＞ 0） 个互不相交的树的集合称为森林 。 森林的概念与树的概念十分相近,
因为只要把树的根结点删去就成了森林 。 反之,
只要给 n棵独立的树加上一个结点,并把这 n棵树作为该结点的子树,则森林就变成了树 。
7.1.4 树的性质性质 1 树中的结点数等于所有结点的度数加 1。
证明：根据树的定义,在一棵树中,除树根结点外,每个结点有且仅有一个前驱结点 。 也就是说,
每个结点与指向它的一个分支一一对应,所以除树根之外的结点数等于所有结点的分支数 （ 度数 ）,
从而可得树中的结点数等于所有结点的度数加 1。
性质 2 度为 m的树中第 i层上至多有 mi-1个结点,这里应有 i≥1。
证明 （ 采用数学归纳法 ）
对于第一层,因为树中的第一层上只有一个结点,
即整个树的根结点,而由 i=1代入 mi-1,得 mi-1=m1-1=1，
也同样得到只有一个结点,显然结论成立 。
假设对于第 (i-1)层 （ i＞ 1） 命题成立,即度为 m的树中第 (i-1)层上至多有 mi-2个结点,则根据树的度的定义,度为 m的树中每个结点至多有 m个孩子结点,所以第 i层上的结点数至多为第 (i-1)层上结点数的 m倍,
即至多为 mi-2× m=mi-1个,这与命题相同,故命题成立 。
性质 3 高度为 h的 m次树至多有 个结点 。
证明：由树的性质 2可知,第 i层上最多结点数为
mi-1（ i=1,2,…,h）,显然当高度为 h的 m次树
（ 即度为 m的树 ） 上每一层都达到最多结点数时,整个 m次树具有最多结点数,因此有：
整 个 树的 最 多结 点数 =每 一 层最 多结 点 数之 和
=m0+m1+m2+… +mh-1 = 。
1
1
mm
h
1
1
mm
h
性质 4 具有 n个结点的 m次树的最小高度为
logm(n(m-1)+1)?。
证明：设具有 n个结点的 m次树的高度为 h,若在该树中前 h-1层都是满的,即每一层的结点数都等于
mi-1个 （ 1≤i≤h-1）,第 h层 （ 即最后一层 ） 的结点数可能满,也可能不满,则该树具有最小的高度 。 其高度 h可计算如下：
根据树的性质 3可得,＜ n≤
乘 (m-1)后得,mh-1＜ n(m-1)+1≤mh
以 m为底取对数后得,h-1＜ logm(n(m-1)+1)≤h
即 logm(n(m-1)+1)≤h＜ logm(n(m-1)+1)+1
因 h只能取整数,所以
h=?logm(n(m-1)+1)?
结论得证 。
1
11
m
mh 11mmh
例 7.1 含 n个结点的三次树的最小高度是多少？
解：设含 n个结点的 (为完全三次树时高度最小 )的三次树的最小高度为 h,则有：
1+3+9+… +3h-2+1≤n≤1+3+9+… +3h-1
(3h-1-1)/2 +1≤n≤ (3h-1)/2
3h-1 ≤2n-1≤ 3h-2
即,h=?log3(2n-1)?+1
或：
1+3+9+… +3h-2＜ n≤1+3+9+… +3h-1
(3h-1-1)/2 ＜ n≤ (3h-1)/2
3h-1＜ 2n+1≤3h
即,h=? log3(2n+1)?
7.1.5 树的基本运算树的运算主要分为三大类：
第一类,寻找满足某种特定关系的结点,如寻找当前结点的双亲结点等；
第二类,插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第 i
个孩子结点等；
第三类,遍历树中每个结点,这里着重介绍 。
树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次 。 树的遍历运算的算法主要有先根遍历和后根遍历两种 。 注意,下面的先根遍历和后根遍历算法都是递归的 。
1,先根遍历先根遍历算法为：
（ 1） 访问根结点；
（ 2）按照从左到右的次序先根遍历根结点的每一棵子树。
2,后根遍历后根遍历算法为：
（ 1） 按照从左到右的次序后根遍历根结点的每一棵子树；
（ 2） 访问根结点 。
7.1.6 树的存储结构
1,双亲存储结构这种存储结构是一种顺序存储结构,用一组连续空间存储树的所有结点,同时在每个结点中附设一个伪指针指示其双亲结点的位置 。
A
D B C
G E F
A - 1
B 0
C 0
D 0
E 2
F 2
G 2
0
1
2
3
4
5
6
(a ) (b)
2,孩子链存储结构孩子链存储结构可按树的度 （ 即树中所有结点度的最大值 ） 设计结点的孩子结点指针域个数 。 下图 （ a）
的树对应的孩子链存储结构如图 （ b） 所示 。
A
B C
F D E
(a )
G
A ∧
B C ∧ ∧ ∧
D ∧ ∧ ∧ E ∧ ∧ F ∧ ∧ ∧
G ∧ ∧ ∧
(b )
3,孩子兄弟链存储结构孩子兄弟链存储结构是为每个结点设计三个域：
一个数据元素域,一个该结点的第一个孩子结点指针域,一个该结点的下一个兄弟结点指针域 。 下图
（ a） 的树对应的孩子兄弟链存储结构如图 （ b） 所示 。
A
B C
F D E
(a )
G
A ∧
B
∧ D
∧ C ∧
E
∧ G ∧
∧ F ∧
( b )
7.2 二叉树概念和性质
7.2.1 二叉树概念
7.2.2 二叉树性质
7.2.3 二叉树与树、森林之间的转换
7.2.1 二叉树概念二叉树也称为二次树或二分树,它是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成 。
二叉树的定义是一种递归定义 。
二叉树有五种基本形态,如下图所示,任何复杂的二叉树都是这五种基本形态的复合 。
从定义看到,二叉树是一种特殊的树,其表示法也与树的表示法一样,有树形表示法,文氏图表示法,凹入表示法和括号表示法等 。
在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉树的最下一层,这样的二叉树称为满二叉树 。 下图所示就是一棵满二叉树 。 可以对满二叉树的结点进行连续编号,
约定编号从树根为 1开始,按照层数从小到大,同一层从左到右的次序进行 。 图中每个结点外边的数字为对该结点的编号 。
A
B C
D E
H I J K
F G
L M N O
1
2 3
4
5 6 7
8 9 10 15 11 12 13 14
满二叉树若二叉树中最多只有最下面两层的结点的度数可以小于 2,并且最下面一层的叶结点 都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树 。 如下图所示为一棵完全二叉树 。 同样可以对完全二叉树中每个结点进行连续编号,编号的方法同满二叉树相同 。 图中每个结点外边的数字为对该结点的编号 。
A
B C
D E
H I J K
F G
1
2 3
4
5 6 7
8 9 10 11
完全二叉树
7.2.2 二叉树性质性质 1 非空二叉树上叶结点数等于双分支结点数加
1。
证明：设二叉树上叶结点数为 n0,单分支结点数为 n1,双分支结点数为 n2,则总结点数 =n0+n1+n2。 在一棵二叉树中,所有结点的分支数 （ 即度数 ） 应等于单分支结点数加上双分支结点数的 2倍,即总的分支数 =n1+2n2。
由于二叉树中除根结点以外,每个结点都有惟一的一个分支指向它,因此二叉树中有：总的分支数 =总结点数 -1。
由上述三个等式可得,n1+2n2=n0+n1+n2-1
即,n0=n2+1
性质 2 非空二叉树上第 i层上至多有 2i-1个结点,这里应有 i≥1。
由树的性质 2可推出 。
性质 3 高度为 h的二叉树至多有 2h-1个结点
（ h≥1） 。
由树的性质 3可推出 。
性质 4 对完全二叉树中编号为 i的结点 （ 1≤i≤n，
n≥1,n为结点数 ） 有：
（ 1） 若 i≤?n/2?,即 2i≤n,则编号为 i的结点为分支结点,否则为叶子结点 。
（ 2） 若 n为奇数,则每个分支结点都既有左孩子结点,也有右孩子结点；若 n为偶数,则编号最大的分支结点 （ 编号为 ） 只有左孩子结点,没有右孩子结点,其余分支结点都有左,右孩子结点 。
（ 3） 若编号为 i的结点有左孩子结点,则左孩子结点的编号为 2i；若编号为 i的结点有右孩子结点,
则右孩子结点的编号为 (2i+1)。
（ 4） 除树根结点外,若一个结点的编号为 i,则它的双亲结点的编号为?i/2?,也就是说,当 i为偶数时,其双亲结点的编号为 i/2,它是双亲结点的左孩子结点,当 i为奇数时,其双亲结点的编号为 (i-1)/2，
它是双亲结点的右孩子结点 。
性质 5 具有 n个 （ n＞ 0） 结点的完全二叉树的高度为?log2n+1?或?log2n?+1。
由完全二叉树的定义和树的性质 3可推出 。
7.2.3 二叉树与树、森林之间的转换
1,森林,树转换为二叉树
（ 1） 在所有相邻兄弟结点 （ 森林中每棵树的根结点可看成是兄弟结点 ） 之间加一水平连线 。
（ 2） 对每个非叶结点 k,除了其最左边的孩子结点外,删去 k与其他孩子结点的连线 。
（ 3） 所有水平线段以左边结点为轴心顺时针旋转 45度 。
通过以上步骤,原来的森林就转换为一棵二叉树 。 一般的树是森林中的特殊情况,由一般的树转换的二叉树的根结点的右孩子结点始终为空,原因是一般的树的根结点不存在兄弟结点和相邻的树 。
A
B C D
E
F
G
H I
A
B E
F G C
D H
I
(a ) (c )
A
B C D
E
F
G
H I
(b)
将森林转换为二叉树的过程
2,二叉树还原为森林,树
（ 1） 对于一棵二叉树中任一结点 k0,沿着 k1
右孩子结点的右子树方向搜索所有右孩子结点,
即搜索结点序列 k2,k3,…,km,其中 ki+1为 ki
的右孩子结点 (1≤i＜ m),km没有右孩子结点 。
（ 2） 删去 k1,k2,…,km之间连线 。
（ 3 ） 若 k1 有双亲结点 k,则连接 k与 ki
（ 2≤i≤m） 。
（ 4） 将图形规整化,使各结点按层次排列 。
A
D H B
F C G
E
A
B
D C
F E H G
( a ) ( c )
A
B
D C
F E H G
( b)
将一棵二叉树还原为树的过程
7.3 二叉树存储结构
7.3.1 二叉树的顺序存储结构
7.3.2 二叉树的链式存储结构
7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构中结点的存放次序是：
对该树中每个结点进行编号，其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。
若把二叉树存储到一维数组中，则该编号就是下标值加 1（注意,C/C++语言中数组的起始下标为
0）。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同。
利用二叉树的性质 4。
A
B C
D E
H I J K
F G
1
2 3
4
5 6 7
8 9 10 11
完全二叉树
A B C D E F G H I J K
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
顺序存储结构
7.3.2 二叉树的链式存储结构在二叉树的链接存储中,结点的结构如下,
typedef struct node
{
ElemType data;
struct node *lchild,*rchild;
} BTNode;
其中,data表示值域,用于存储对应的数据元素,
lchild和 rchild分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点 （ 即左,右子树的根结点 ） 的存储位置 。
A
B
C
E F D
G
A
B ∧ C
∧ D ∧ E ∧ ∧ F ∧
∧ G ∧
(a) (b )
二叉树及其链式存储结构
7.4 二叉树的遍历
7.4.1 二叉树遍历的概念
7.4.2 二叉树遍历递归算法
7.4.1 二叉树遍历的概念二叉树的遍历是指按照一定次序访问树中所有结点,并且每个结点仅被访问一次的过程 。 它是最基本的运算,是二叉树中所有其他运算的基础 。
1,先序遍历先序遍历二叉树的过程是：
（ 1） 访问根结点；
（ 2） 先序遍历左子树；
（ 3） 先序遍历右子树 。
2,中序遍历中序遍历二叉树的过程是：
（ 1） 中序遍历左子树；
（ 2） 访问根结点；
（ 3） 中序遍历右子树 。
3,后序遍历后序遍历二叉树的过程是：
（ 1） 后序遍历左子树；
（ 2） 后序遍历右子树；
（ 3） 访问根结点 。
7.4.2 二叉树遍历递归算法由二叉树的三种遍历过程直接得到如下三种递归算法如下：
void PreOrder(BTNode *b) /*先序遍历的递归算法 */
{
if (b!=NULL)
{ printf("%c ",b->data); /*访问根结点 */
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
void InOrder(BTNode *b) /*中序遍历的递归算法 */
{
if (b!=NULL)
{ InOrder(b->lchild);
printf("%c ",b->data); /*访问根结点 */
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) /*后序遍历递归算法 */
{
if (b!=NULL)
{ PostOrder(b->lchild);
PostOrder(b->rchild);
printf("%c ",b->data); /*访问根结点 */
}
}
例 7.2 假设二叉树采用二叉链存储结构存储,试设计一个算法,输出一棵给定二叉树的所有叶子结点 。
解：输出一棵二叉树的所有叶子结点的递归模型 f()
如下：
f(b)：不做任何事件 若 b=NULL
f(b)：输出 *b结点的 data域 若 *b为叶子结点
f(b),f(b->lchild);f(b->rchild) 其他情况
void DispLeaf(BTNode *b)
{
if (b!=NULL)
{
if (b->lchild==NULL && b->rchild==NULL)
printf("%c ",b->data);
else
{ DispLeaf(b->lchild);
DispLeaf(b->rchild);
}
}
}
7.5 二叉树的基本运算及其实现
7.5.1 二叉树的基本运算概述
7.5.2 二叉树的基本运算算法实现
7.5.1 二叉树的基本运算概述归纳起来,二叉树有以下基本运算：
（ 1） 创建二叉树 CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串 *str生成对应的链式存储结构 。
（ 2） 查找结点 FindNode(*b,x)：在二叉树 b中寻找 data域值为 x的结点,并返回指向该结点的指针 。
（ 3） 找孩子结点 LchildNode(p)和 RchildNode(p)：
分别求二叉树中结点 *p的左孩子结点和右孩子结点 。
（ 4） 求高度 BTNodeDepth(*b)：求二叉树 b的高度 。 若二叉树为空,则其高度为 0；否则,其高度等于左子树与右子树中的最大高度加 l。
（ 5） 输出二叉树 DispBTNode(*b)：以括号表示法输出一棵二叉树 。
7.5.2 二叉树的基本运算算法实现
（ 1） 创建二叉树 CreateBTNode(*b,*str)
用 ch扫描采用括号表示法表示二叉树的字符串 。 分以下几种情况：
① 若 ch='('：则将前面刚创建的结点作为双亲结点进栈,并置 k=1,表示其后创建的结点将作为这个结点的左孩子结点；
② 若 ch=')'：表示栈中结点的左右孩子结点处理完毕,退栈；
③ 若 ch=','：表示其后创建的结点为右孩子结点；
④ 其他情况,表示要创建一个结点,并根据 k值建立它与栈中结点之间的联系,当 k=1时,表示这个结点作为栈中结点的左孩子结点,当 k=2时,表示这个结点作为栈中结点的右孩子结点 。 如此循环直到
str处理完毕 。 算法中使用一个栈 St保存双亲结点,
top为其栈指针,k指定其后处理的结点是双亲结点
（ 保存在栈中 ） 的左孩子结点 （ k=1） 还是右孩子结点 （ k=2） 。
void CreateBTNode(BTNode * &b,char *str)
{ BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL; /*建立的二叉树初始时为空 */
ch=str[j];
while (ch!='\0') /*str未扫描完时循环 */
{
switch(ch)
{
case '(':top++;St[top]=p;k=1; break;
/*为左孩子结点 */
case ')':top--;break;
case ',':k=2; break;
/*为孩子结点右结点 */
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if (b==NULL) /**p为二叉树的根结点 */
b=p;
else /*已建立二叉树根结点 */
{ switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;ch=str[j];
}
}
例如,对 于 括 号 表 示 法 字 符 串
A(B(D(,G)),C(E,F)),建立二叉树链式存储结构的过程如下表所示 。
ch 算法执行的操作 St中元素
A 建立 A结点,b指向该结点 空
( A结点进栈,k=1 A
B 建立 B结点,因 k=1,将其作为 A结点的左孩子结点
A
( B结点进栈,k=1 AB
D 建立 D结点,因 k=1,将其作为 B结点的左孩子结点
AB
( D结点进栈,k=1 ABD
,k=2 ABD
G 建立 E结点,因 k=2,将其作为 D
结点的右孩子结点
ABD
) 退栈一次 AB
) 退栈一次 A
,k=2 A
C 建立 C结点,因 k=2,将其作为 A
结点的右孩子结点
A
( C结点进栈,k=1 AC
E 建立 E结点,因 k=1,将其作为 C
结点的左孩子结点
AC
,k=2 AC
F 建立 F结点,因 k=2,将其作为 C结点的右孩子结点
AC
) 退栈一次 A
) 退栈一次 空
ch扫描完毕 算法结束
A
B ∧ C
∧ D ∧ E ∧ ∧ F ∧
∧ G ∧
（ 2） 查找结点 FindNode(*b,x)
采用先序遍历递归算法查找值为 x的结点 。 找到后返回其指针,否则返回 NULL。 算法如下：
BTNode *FindNode(BTNode *b,ElemType x)
{ BTNode *p;
if (b==NULL) return NULL;
else if (b->data==x) return b;
else { p=FindNode(b->lchild,x);
if (p!=NULL) return p;
else return FindNode(b->rchild,x);
}
}
（ 3） 找孩子结点 LchildNode(p)和 RchildNode(p)
直接返回 *p结点的左孩子结点或右孩子结点的指针 。 算法如下：
BTNode *LchildNode(BTNode *p)
{
return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
return p->rchild;
}
（ 4） 求高度 BTNodeDepth(*b)
求二叉树的高度的递归模型 f()如下：
f(NULL)=0
f(b)=MAX{f(b->lchild),f(b->rchild)}+1 其他情况对应的算法如下：
int BTNodeDepth(BTNode *b)
{ int lchilddep,rchilddep;
if (b==NULL) return(0); /*空树的高度为 0*/
else
{ lchilddep=BTNodeDepth(b->lchild);
/*求左子树的高度为 lchilddep*/
rchilddep=BTNodeDepth(b->rchild);
/*求右子树的高度为 rchilddep*/
return(lchilddep>rchilddep)?
(lchilddep+1):(rchilddep+1);
}
}
（ 5） 输出二叉树 DispBTNode(*b)
其过程是：对于非空二叉树 b,先输出其元素值,
当存在左孩子结点或右孩子结点时,输出一个,(”符号,然后递归处理左子树,输出一个,,”符号,递归处理右子树,最后输出一个,)”符号 。 对应的递归算法如下：
void DispBTNode(BTNode *b)
{ if (b!=NULL)
{ printf("%c",b->data);
if (b->lchild!=NULL || b->rchild!=NULL)
{ printf("(");
DispBTNode(b->lchild);
/*递归处理左子树 */
if (b->rchild!=NULL) printf(",");
DispBTNode(b->rchild);
/*递归处理右子树 */
printf(")");
}
}
}
例 7.3 假设二叉树采用二叉链存储结构,设计一个算法判断两棵二叉树是否相似,所谓二叉树 t1和
t2是相似的指的是 t1和 t2都是空的二叉树；或者 t1和
t2的根结点是相似的,以及 t1的左子树和 t2的左子树是相似的且 t1的右子树与 t2的右子树是相似的 。
解：判断两棵二叉树是否相似的递归模型 f()如下：
f(t1,t2)=true 若 t1=t2=NULL
f(t1,t2)=false 若 t1,t2之一为 NULL,另一不为 NULL
f(t1,t2)=f(t1->lchild,t2->lchild) & 其他情况
f(t1->rchild,t2->rchild)
对应的算法如下：
int Like(BTNode *b1,BTNode *b2)
/*t1和 t2两棵二叉树相似时返回 1,否则返回 0*/
{ int like1,like2;
if (b1==NULL && b2==NULL) return 1;
else if (b1==NULL || b2==NULL) return 0;
else
{ like1=Like(b1->lchild,b2->lchild);
like2=Like(b1->rchild,b2->rchild);
return (like1 & like2); /*返回 like1和 like2的与 */
}
}
例 7.4 假设二叉树采用二叉链存储结构,设计一个算法
Level()求二叉树中指定结点的层数 。 并利用本节的基本运算编写一个完整的程序,建立教材中图 7.8(a)的二叉树的二叉链,对于用户输入的任何结点值计算出在该二叉树中的层次 。
解：本题采用递归算法，设 h返回 p所指结点的高度，
其初值为 0。找到指定的结点时返回其层次；否则返回 0。
lh作为一个中间变量在计算搜索层次时使用，其初值为
1。对应的算法如下：
void Level(BTNode *b,BTNode *p,int &h,int lh)
/*找到 *p结点后 h为其层次,否则为 0*/
{ if (b==NULL) h=0; /*空树时返回 0*/
else if (p==b) h=lh; /*找到结点 p时 */
else
{ Level(b->lchild,p,h,lh+1); /*在左子树中递归查找 */
if (h==0) /*左子树中未找到时在右子树中递归查找 */
Level(b->rchild,p,h,lh+1);
}
}
例 7.5 假设二叉树采用二叉链存储结构,设计一个算法输出从每个叶子结点到根结点的路径 。
解：这里用层次遍历方法，设计的队列为非循环顺序队列（类似于第 3章 3.2.4小节中求解迷宫问题时使用的队列）将所有已扫描过的结点指针进队，并在队列中保存双亲结点的位置。当找到一个叶子结点时，
在队列中通过双亲结点的位置输出该叶子结点到根结点的路径。对应的算法如下：
void AllPath(BTNode *b)
{ struct snode
{ BTNode *node; /*存放当前结点指针 */
int parent; /*存放双亲结点在队列中的位置 */
} q[MaxSize]; /*定义顺序队列 */
int front,rear,p; /*定义队头和队尾指针 */
front=rear=-1; /*置队列为空队列 */
rear++;q[rear].node=b; /*根结点指针进入队列 */
q[rear].parent=-1; /*根结点没有双亲结点 */
while (front<rear) /*队列不为空 */
{ front++;
b=q[front].node; /*队头出队列 */
if (b->lchild==NULL && b->rchild==NULL)
{ printf("%c到根结点路径,",b->data);
p=front;
while (q[p].parent!=-1)
{ printf("%c->",q[p].node->data);
p=q[p].parent; }
printf("%c\n",q[p].node->data);
}
if (b->lchild!=NULL) /*左孩子结点入队列 */
{ rear++; q[rear].node=b->lchild;
q[rear].parent=front; }
if (b->rchild!=NULL) /*右孩子结点入队列 */
{ rear++; q[rear].node=b->rchild;
q[rear].parent=front; }
} /*end of while*/
}
7.6 二叉树的构造同一棵二叉树具有惟一先序序列,中序序列和后序序列,但不同的二叉树可能具有相同的先序序列,
中序序列和后序序列 。
例如，如教材中图 7.9所示的 5棵二叉树，先序序列都为 ABC。如图 7.10所示的 5棵二叉树，中序序列都为 ACB。如图 7.11所示的 5棵二叉树，后序序列都为 CBA。
显然，仅由一个先序序列（或中序序列、后序序列），无法确定这棵二叉树的树形。但是，如果同时知道一棵二叉树的先序序列和中序序列，或者同时知道中序序列和后序序列，就能确定这棵二叉树。
定理 7.1：任何 n（ n≥0） 个不同结点的二又树,都可由它的中序序列和先序序列惟一地确定 。
采用数学归纳法证明 。
当 n=0时,二叉树为空,结论正确 。
假设结点数小于 n的任何二叉树,都可以由其先序序列和中序序列惟一地确定 。
已知某棵二叉树具有 n（ n＞ 0） 个不同结点,其先序序列是 a0a1… an-1；中序序列是 b0b1… bk-1bkbk+1… bn-1。
因为在先序遍历过程中,访问根结点后,紧跟着遍历左子树,最后再遍历右子树 。 所以,a0必定是二叉树的根结点,而且 a0必然在中序序列中出现 。 也就是说,
在中序序列中必有某个 bk（ 0≤k≤n-1） 就是根结点 a0。
由于 bk是根结点,而在中序遍历过程中,先遍历左子树,再访问根结点,最后再遍历右子树 。 所以在中序序列中,b0b1… bk-1必是根结点 bk（ 也就是 a0） 左子树的中序序列,即 bk的左子树有 k个结点 （ 注意,k=0表示结点 bk没有左子树 。 ） 而 bk+1… bn-1必是根结点 bk
（ 也就是 a0） 右子树的中序序列,即 bk的右子树有 n-k-
1个结点 （ 注意,k=n-1表示结点 bk没有右子树 。 ） 。
另外,在先序序列中,紧跟在根结点 a0之后的 k个结点
a1… ak就是左子树的先序序列,ak+1… an-1这 n-k-1就是右子树的先序序列 。
根据归纳假设,由于子先序序列 a1… ak和子中序序列
b0b1… bk-1可以惟一地确定根结点 a0的左子树,而子先序序列 ak+1… an-1和子中序序列 bk+1… bn-1可以惟一地确定根结点 a0的右子树 。
综上所述，这棵二叉树的根结点己经确定，而且其左、右子树都惟一地确定了，所以整个二叉树也就惟一地确定了。
例如，已知先序序列为 ABDGCEF，中序序列为 DGBAECF，
则构造二叉树的过程如下所示。
根结点,A
左先序,BDG 左中序,DGB
右先序,CEF 右中序,ECF
根结点,B
左先序,DG左中序,DG
右先序,空 右中序,空根结点,D
左先序,空 左中序,空右先序,G 右中序,G
根结点,G
左先序,空 左中序,空右先序,空 右中序,空根结点,C
左先序,E 左中序,E
右先序,F右中序,F
根结点,E
左先序,空 左中序,空右先序,空 右中序,空根结点,F
左先序,空 左中序,空右先序,空 右中序,空由上述定理得到以下构造二叉树的算法：
BTNode *CreateBT1(char *pre,char *in,int n)
{ BTNode *s; char *p; int k;
if (n<=0) return NULL;
s=(BTNode *)malloc(sizeof(BTNode)); /*创建结点 *s*/
s->data=*pre;
for (p=in;p<in+n;p++) /*在中序中找为 *ppos的位置 k*/
if (*p==*pre)
break;
k=p-in;
s->lchild=CreateBT1(pre+1,in,k); /*递归构造左子树 */
s->rchild=CreateBT1(pre+k+1,p+1,n-k-1); /*构造右子树 */
return s;
}
定理 7.2,任何 n（ n＞ 0） 个不同结点的二又树,
都可由它的中序序列和后序序列惟一地确定 。
同样采用数学归纳法证明。
实际上，对于根结点 ak的左右子树，在确定左右子树的子中序序列后，不需要确定左右子树的整个子后序序列，只需确定子中序序列中全部字符在后序序列中最右边的那个字符即可，因为这个字符就是子树的根结点。
例如，已知中序序列为 DGBAECF，后序序列为 GDBEFCA。
对应的构造二叉树的过程如下所示。
根结点,A
左中序,DGB 左根,B
右中序,ECF右根,C
根结点,B
左中序,DG左根,D
右中序,空 右根,空根结点,D
左中序,空 左根,空右中序,G 右根,G
根结点,G
左中序,空 左根,空右中序,空 右根,空根结点,C
左中序,E 左根,E
右中序,F右根,F
根结点,E
左中序,空 左根,空右中序,空 右根,空根结点,F
左中序,空 左根,空右中序,空 右根,空由上述定理得到以下构造二叉树的算法：
BTNode *CreateBT2(char *post,char *in,int n,int m)
{ BTNode *s;char *p,*q,*maxp;int maxpost,maxin,k;
if (n<=0) return NULL;
maxpost=-1;
for (p=in;p<in+n;p++) /*求 in在 post中最右边的那个字符 */
for (q=post;q<post+m;q++) /*在 in中用 maxp指向这个字符,
用 maxin标识它在 in中的下标 */
if (*p==*q)
{ k=q-post;
if (k>maxpost)
{ maxpost=k; maxp=p; maxin=p-in; }
}
s=(BTNode *)malloc(sizeof(BTNode)); /*创建二叉树结点 *s*/
s->data=post[maxpost];
s->lchild=CreateBT2(post,in,maxin,m);
/*递归构造左子树 */
s->rchild=CreateBT2(post,maxp+1,n-maxin-1,m);
/*递归构造右子树 */
return s;
}
7.7 线索二叉树
7.7.1 线索二叉树的概念对于具有 n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有 2n个指针域，
又由于只有 n-1个结点被有效指针所指向（ n个结点中只有树根结点没有被有效指针域所指向），则共有 2n-(n-1)=n+1个空链域，
我们知道,遍历二叉树的结果是一个结点的线性序列 。 可以利用这些空链域存放指向结点的前驱和后继结点的指针 。 这样的指向该线性序列中的
,前驱,和,后继,的指针,称作线索 。
在结点的存储结构上增加两个标志位来区分这两种情况：
左标志 ltag,0 表示 lchild指向左孩子结点
1 表示 lchild指向前驱结点右标志 rtag,0 表示 rchild指向右孩子结点
1 表示 rchild指向后继结点这样,每个结点的存储结构如下：
ltag lchild data rchild rtag
按上述原则在二叉树的每个结点上加上线索的二叉树称作 线索二叉树 。 对二叉树以某种方式遍历使其变为线索二叉树的过程称作按该方式对二叉树进行 线索化 。
为使算法设计方便，在线索二叉树中再增加一个头结点。头结点的 data域为空； lchild指向无线索时的根结点,ltag为 0； rchild指向按某种方式遍历二叉树时的最后一个结点,rtag为 1。
教材中图 7.14为图 7.8(a)所示二叉树的线索二叉树。
其中，图 7.14(a)是中序线索二叉树（中序序列为：
DGBAECF），图 7.14(b)是先序线索二叉树（先序序列为,ABDGCEF），图 7.14(c)是后序线索二叉树
（后序序列为,GDBEFCA）。图中实线表示二叉树原来指针所指的结点，虚线表示线索二叉树所添加的线索。
7.7.2 线索化二叉树建立线索二叉树,或者说,对二叉树线索化,实质上就是遍历一棵二叉树,在遍历的过程中,检查当前结点的左,右指针域是否为空 。 如果为空,将它们改为指向前驱结点或后继结点的线索 。 另外,在对一棵二叉树添加线索时,我们创建一个头结点,并建立头结点与二叉树的根结点的线索 。 对二叉树线索化后,还须建立最后一个结点与头结点之间的线索 。
下面以中序线索二叉树为例,讨论建立线索二叉树的算法 。
为了实现线索化二叉树,将前面二叉树结点的类型定义修改如下：
typedef struct node
{
ElemType data; /*结点数据域 */
int ltag,rtag; /*增加的线索标记 */
struct node *lchild; /*左孩子或线索指针 */
struct node *rchild; /*右孩子或线索指针 */
} TBTNode; /*线索树结点类型定义 */
下面是建立中序线索二叉树的算法 。 CreaThread(b)
算法是将以二叉链存储的二叉树 b进行中序线索化,并返回线索化后头结点的指针 root。 Thread(p)算法用于对于以 *p为根结点的二叉树中序线索化 。 在整个算法中 p总是指向当前被线索化的结点,而 pre作为全局变量,指向刚刚访问过的结点,*pre是 *p的前驱结点,
*p是 *pre的后继结点 。
CreaThread(b)算法思路是：先创建头结点 *root，
其 lchild域为线索,rchild域为链指针。将 rchild指针指向 *b，如果 b二叉树为空，则将其 lchild指向自身。否则将 *root的 lchild指向 *b结点,p指向 *b结点,pre指向 *root结点。再调用 Thread(b)对整个二叉树线索化。
最后加入指向头结点的线索，并将头结点的 rchild指针域线索化为指向最后一个结点（由于线索化直到 p等于
NULL为止，所以最后一个结点为 *pre）。
TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树 */
{ TBTNode *root;
root=(TBTNode *)malloc(sizeof(TBTNode)); /*创建头结点 */
root->ltag=0;root->rtag=1; root->rchild=b;
if (b==NULL) root->lchild=root; /*空二叉树 */
else
{ root->lchild=b;
pre=root; /*pre是 *p的前驱结点,供加线索用 */
Thread(b); /*中序遍历线索化二叉树 */
pre->rchild=root; /*最后处理,加入指向头结点的线索 */
pre->rtag=1;
root->rchild=pre; /*头结点右线索化 */
}
return root;
}
Thread(p)算法思路是：类似于中序遍历的递归算法,
在 p指针不为 NULL时,先对 *p结点的左子树线索化；
若 *p结点没有左孩子结点,则将其 lchild指针线索化为指向其前驱结点 *pre,否则表示 lchild指向其左孩子结点,将其 ltag置为 1；若 *pre结点的 rchild指针为
NULL,将其 rchild指针线索化为指向其后继结点 *p，
否则 rchild表示指向其右孩子结点,将其 rtag置为 1，
再将 pre指向 *p；最后对 *p结点的右子树线索化 。
TBTNode *pre; /*全局变量 */
void Thread(TBTNode *&p) /*对二叉树 b进行中序线索化 */
{ if (p!=NULL)
{ Thread(p->lchild); /*左子树线索化 */
if (p->lchild==NULL) /*前驱线索 */
{ p->lchild=pre; p->ltag=1;} /*建立当前结点的前驱线索 */
else p->ltag=0;
if (pre->rchild==NULL) /*后继线索 */
{ pre->rchild=p;pre->rtag=1;}/*建立前驱结点的后继线索 */
else pre->rtag=0;
pre=p;
Thread(p->rchild); /*递归调用右子树线索化 */
}
}
7.7.3 遍历线索化二叉树遍历某种次序的线索二叉树，就是从该次序下的开始结点出发，反复找到该结点在该次序下的后继结点，
直到终端结点。
在中序线索二叉树中，开始结点就是根结点的最左下结点，而求当前结点在中序序列下的后继和前驱结点的方法如教材中表 7.2所示，最后一个结点的 rchild指针被线索化为指向头结点。利用这些条件，在中序线索化二叉树中实现中序遍历的算法如下：
void ThInOrder(TBTNode *tb)
{ TBTNode *p=tb->lchild; /*p指向根结点 */
while (p!=tb)
{ while (p->ltag==0) p=p->lchild; /*找开始结点 */
printf("%c",p->data); /*访问开始结点 */
while (p->rtag==1 && p->rchild!=tb)
{ p=p->rchild;
printf("%c",p->data);
}
p=p->rchild;
}
}
7.8 哈夫曼树
7.8.1 哈夫曼树的定义
7.8.2 构造哈夫曼树
7.8.3 哈夫曼编码
7.8.1 哈夫曼树的定义设二叉树具有 n个带权值的叶子结点,那么从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和,叫做二叉树的带权路径长度 。
其中,n表示叶子结点的数目,wi和 li分别表示叶子结点 ki的权值和根到 ki之间的路径长度
（ 即从叶子结点到达根结点的分支数 ） 。
具有最小带权路径长度的二叉树称为哈夫曼树 。
n
i
ii lwW P L
1
7.8.2 构造哈夫曼树根据哈夫曼树的定义,一棵二叉树要使其 WPL值最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点 。 那么如何构造一棵哈夫曼树呢?其方法如下,
（ 1） 由给定的 n个权值 {W1,W2,...,Wn}构造 n棵只有一个叶子结点的二叉树,从而得到一个二叉树的集合 F={T1,T2,...,Tn};
（ 2） 在 F中选取根结点的权值最小和次小的两棵二叉树作为左,右子树构造一棵新的二叉树,这棵新的二叉树根结点的权值为其左,右子树根结点权值之和 ;
（ 3） 在集合 F中删除作为左,右子树的两棵二叉树,
并将新建立的二叉树加入到集合 F中 ;
（ 4） 重复 (2),(3)两步,当 F中只剩下一棵二叉树时,
这棵二叉树便是所要建立的哈夫曼树 。
给定权值 w=(1,3,5,7)来构造一棵哈夫曼树 。
9
4
1
7
5
3
16
9
4
1
7
5
3
(c ) (d )
1 3 5 7
4 5 7
1 3
(a ) (b )
为了实现构造哈夫曼树的算法,设计哈夫曼树中每个结点类型如下：
typedef struct
{ char data; /*结点值 */
float weight; /*权重 */
int parent; /*双亲结点 */
int lchild; /*左孩子结点 */
int rchild; /*右孩子结点 */
} HTNode;
用 ht[]数组存放哈夫曼树，对于具有 n个叶子结点的哈夫曼树，总共有 2n-1个结点。其算法思路是,n个叶子结点只有 data和 weight域值，先将所有 2n-1个结点的 parent,lchild和 rchild域置为初值 -1。处理每个非叶子结点 ht[i]（存放在 ht[n]～ ht[2n-2]中）：从 ht[0] ～
ht[i-2]中找出根结点（即其 parent域为 -1）最小的两个结点 ht[lnode]和 ht[rnode]，将它们作为 ht[i]的左右子树，
ht[lnode]和 ht[rnode]的双亲结点置为 ht[i]，并且
ht[i].weight=ht[lnode].weight+ht[rnode].weight。如此这样直到所有 2n-1个非叶子结点处理完毕。
构造哈夫曼树的算法如下：
void CreateHT(HTNode ht[],int n)
{ int i,j,k,lnode,rnode; float min1,min2;
for (i=0;i<2*n-1;i++) /*所有结点的相关域置初值 -1*/
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n;i<2*n-1;i++) /*构造哈夫曼树 */
{ min1=min2=32767; lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1)/*未构造二叉树的结点中查找 */
{ if (ht[k].weight<min1)
{ min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k; }
else if (ht[k].weight<min2)
{ min2=ht[k].weight;rnode=k; } } /*if*/
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}
7.8.3 哈夫曼编码具体构造方法如下：设需要编码的字符集合为
{d1,d2,…,dn},各个字符在电文中出现的次数集合为
{w1,w2,…,wn},以 d1,d2,…,dn作为叶结点,以 w1，
w2,…,wn作为各根结点到每个叶结点的权值构造一棵二叉树,规定哈夫曼树中的左分支为 0,右分支为 1，
则从根结点到每个叶结点所经过的分支对应的 0和 1组成的序列便为该结点对应字符的编码 。 这样的编码称为哈夫曼编码 。
对应的哈夫曼编码如下：
1,000 3,001 5,01 7,1
为了实现构造哈夫曼编码的算法,设计存放每个结点哈夫曼编码的类型如下：
typedef struct
{
char cd[N]; /*存放当前结点的哈夫曼码 */
int start;
} HCode;
根据哈夫曼树求对应的哈夫曼编码的算法如下：
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{ int i,f,c; HCode hc;
for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码 */
{ hc.start=n;c=i; f=ht[i].parent;
while (f!=-1) /*循环直到无双亲结点即到达树根结点 */
{ if (ht[f].lchild==c) /*当前结点是左孩子结点 */
hc.cd[hc.start--]='0';
else /*当前结点是双亲结点的右孩子结点 */
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent; /*再对双亲结点进行同样的操作 */
}
hc.start++;/*start指向哈夫曼编码最开始字符 */
hcd[i]=hc;
}
}
本章小结本章的基本学习要点如下：
（ 1） 掌握树的相关概念,包括树,结点的度,
树的度,分支结点,叶子结点,儿子结点,双亲结点,树的深度,森林等定义 。
（ 2） 掌握树的表示,包括树形表示法,文氏图表示法,凹入表示法和括号表示法等 。
（ 3） 掌握二叉树的概念,包括二叉树,满二叉树和完全二叉树的定义 。
（ 4） 掌握二叉树的性质 。
（ 5） 重点掌握二叉树的存储结构,包括二叉树顺序存储结构和链式存储结构 。
（ 6） 重点掌握二叉树的基本运算和各种遍历算法的实现 。
（ 7） 掌握线索二叉树的概念和相关算法的实现 。
（ 8） 掌握哈夫曼树的定义,哈夫曼树的构造过程和哈夫曼编码产生方法 。
（ 9） 灵活运用二叉树这种数据结构解决一些综合应用问题 。
练习教材中 p170的习题 1,2,4,6和 7。
上机实习题教材中 p170题 1,3和 7。
7.1 树的基本概念
7.2 二叉树概念和性质
7.3 二叉树存储结构
7.4 二叉树的遍历
7.5 二叉树的基本运算及其实现
7.6 二叉树的构造
7.8 哈夫曼树本章小结
7.7 线索二叉树
7.1 树的基本概念
7.1.1 树的定义
7.1.3 树的基本术语
7.1.2 树的表示
7.1.4 树的性质
7.1.5 树的基本运算
7.1.6 树的存储结构
7.1.1 树的定义形式化定义：
树,T＝ {K,R}。 K是包含 n个结点的有穷集合
(n>0),关系 R满足以下条件,
（ 1） 有且仅有一个结点 k0∈ K,它对于关系 R来说没有前驱结点,结点 k0称作树的根 。
（ 2） 除结点 k0外,K中的每个结点对于关系 R来说都有且仅有一个前驱结点 。
（ 3） K中每个结点对于关系 R来说可以有多个后继结点 。
递归定义：
树是由 n（ n≥0） 个结点组成的有限集合 （ 记为
T） 。 其中,
如果 n=0,它是一棵空树,这是树的特例；
如果 n>0,这 n个结点中存在 （ 有仅存在 ） 一个结点作为树的根结点,简称为根 （ root）,其余结点可分为 m （ m>0） 个互不相交的有限集 T1,,T2,…,
Tm,其中每一棵子集本身又是一棵符合本定义的树,
称为根 root的子树 。
7.1.2 树的表示
（ 1） 树形表示法 。 这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象 。 下图就是采用这种表示法 。
A
C
G
J
B
E
D
F I H
M K L
树形表示法
（ 2） 文氏图表示法 。 使用集合以及集合的包含关系描述树结构 。 下图就是树的文氏图表示法 。
H
L
D
K I
M
C
G
J
E
B
F
文氏图表示法
A
（ 3） 凹入表示法 。 使用线段的伸缩描述树结构 。 下图是树的凹入表示法 。
（ 4） 括号表示法 。 将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构 。 下图是树的括号表示法 。
7.1.3 树的基本术语
1,结点的度与树的度：树中某个结点的子树的个数称为该结点的度 。 树中各结点的度的最大值称为树的度,通常将度为 m的树称为 m次树或 m叉树 。
2,分支结点与叶结点：度不为零的结点称为非终端结点,又叫分支结点 。 度为零的结点称为终端结点或叶结点 。 在分支结点中,每个结点的分支数就是该结点的度 。 如对于度为 1的结点,其分支数为
1,被称为单分支结点；对于度为 2的结点,其分支数为 2,被称为双分支结点,其余类推 。
3,路径与路径长度：对于任意两个结点 ki和 kj，
若树中存在一个结点序列 ki,ki1,ki2,…,kin,kj，
使得序列中除 ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由 ki到 kj的一条路径,用路径所通过的结点序列 (ki,ki1,ki2,…,kj)表示这条路径 。 路径的长度等于路径所通过的结点数目减 1
（ 即路径上分支数目 ） 。 可见,路径就是从 ki出发
,自上而下,到达 kj所通过的树中结点序列 。 显然,
从树的根结点到树中其余结点均存在一条路径 。
4,孩子结点,双亲结点和兄弟结点：在一棵树中,
每个结点的后继,被称作该结点的孩子结点 （ 或子女结点 ） 。 相应地,该结点被称作孩子结点的双亲结点 （ 或父母结点 ） 。 具有同一双亲的孩子结点互为兄弟结点 。 进一步推广这些关系,可以把每个结点的所有子树中的结点称为该结点的子孙结点,从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点 。
5,结点的层次和树的高度：树中的每个结点都处在一定的层次上 。 结点的层次从树根开始定义,
根结点为第一层 （ 有的教材从第 0层开始 ）,它的孩子结点为第二层,以此类推,一个结点所在的层次为其双亲结点所在的层次加 1。 树中结点的最大层次称为树的高度 （ 或树的深度 ） 。
7,有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则称为有序树,否则称为无序树 。
7,森林,n（ n＞ 0） 个互不相交的树的集合称为森林 。 森林的概念与树的概念十分相近,
因为只要把树的根结点删去就成了森林 。 反之,
只要给 n棵独立的树加上一个结点,并把这 n棵树作为该结点的子树,则森林就变成了树 。
7.1.4 树的性质性质 1 树中的结点数等于所有结点的度数加 1。
证明：根据树的定义,在一棵树中,除树根结点外,每个结点有且仅有一个前驱结点 。 也就是说,
每个结点与指向它的一个分支一一对应,所以除树根之外的结点数等于所有结点的分支数 （ 度数 ）,
从而可得树中的结点数等于所有结点的度数加 1。
性质 2 度为 m的树中第 i层上至多有 mi-1个结点,这里应有 i≥1。
证明 （ 采用数学归纳法 ）
对于第一层,因为树中的第一层上只有一个结点,
即整个树的根结点,而由 i=1代入 mi-1,得 mi-1=m1-1=1，
也同样得到只有一个结点,显然结论成立 。
假设对于第 (i-1)层 （ i＞ 1） 命题成立,即度为 m的树中第 (i-1)层上至多有 mi-2个结点,则根据树的度的定义,度为 m的树中每个结点至多有 m个孩子结点,所以第 i层上的结点数至多为第 (i-1)层上结点数的 m倍,
即至多为 mi-2× m=mi-1个,这与命题相同,故命题成立 。
性质 3 高度为 h的 m次树至多有 个结点 。
证明：由树的性质 2可知,第 i层上最多结点数为
mi-1（ i=1,2,…,h）,显然当高度为 h的 m次树
（ 即度为 m的树 ） 上每一层都达到最多结点数时,整个 m次树具有最多结点数,因此有：
整 个 树的 最 多结 点数 =每 一 层最 多结 点 数之 和
=m0+m1+m2+… +mh-1 = 。
1
1
mm
h
1
1
mm
h
性质 4 具有 n个结点的 m次树的最小高度为
logm(n(m-1)+1)?。
证明：设具有 n个结点的 m次树的高度为 h,若在该树中前 h-1层都是满的,即每一层的结点数都等于
mi-1个 （ 1≤i≤h-1）,第 h层 （ 即最后一层 ） 的结点数可能满,也可能不满,则该树具有最小的高度 。 其高度 h可计算如下：
根据树的性质 3可得,＜ n≤
乘 (m-1)后得,mh-1＜ n(m-1)+1≤mh
以 m为底取对数后得,h-1＜ logm(n(m-1)+1)≤h
即 logm(n(m-1)+1)≤h＜ logm(n(m-1)+1)+1
因 h只能取整数,所以
h=?logm(n(m-1)+1)?
结论得证 。
1
11
m
mh 11mmh
例 7.1 含 n个结点的三次树的最小高度是多少？
解：设含 n个结点的 (为完全三次树时高度最小 )的三次树的最小高度为 h,则有：
1+3+9+… +3h-2+1≤n≤1+3+9+… +3h-1
(3h-1-1)/2 +1≤n≤ (3h-1)/2
3h-1 ≤2n-1≤ 3h-2
即,h=?log3(2n-1)?+1
或：
1+3+9+… +3h-2＜ n≤1+3+9+… +3h-1
(3h-1-1)/2 ＜ n≤ (3h-1)/2
3h-1＜ 2n+1≤3h
即,h=? log3(2n+1)?
7.1.5 树的基本运算树的运算主要分为三大类：
第一类,寻找满足某种特定关系的结点,如寻找当前结点的双亲结点等；
第二类,插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第 i
个孩子结点等；
第三类,遍历树中每个结点,这里着重介绍 。
树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次 。 树的遍历运算的算法主要有先根遍历和后根遍历两种 。 注意,下面的先根遍历和后根遍历算法都是递归的 。
1,先根遍历先根遍历算法为：
（ 1） 访问根结点；
（ 2）按照从左到右的次序先根遍历根结点的每一棵子树。
2,后根遍历后根遍历算法为：
（ 1） 按照从左到右的次序后根遍历根结点的每一棵子树；
（ 2） 访问根结点 。
7.1.6 树的存储结构
1,双亲存储结构这种存储结构是一种顺序存储结构,用一组连续空间存储树的所有结点,同时在每个结点中附设一个伪指针指示其双亲结点的位置 。
A
D B C
G E F
A - 1
B 0
C 0
D 0
E 2
F 2
G 2
0
1
2
3
4
5
6
(a ) (b)
2,孩子链存储结构孩子链存储结构可按树的度 （ 即树中所有结点度的最大值 ） 设计结点的孩子结点指针域个数 。 下图 （ a）
的树对应的孩子链存储结构如图 （ b） 所示 。
A
B C
F D E
(a )
G
A ∧
B C ∧ ∧ ∧
D ∧ ∧ ∧ E ∧ ∧ F ∧ ∧ ∧
G ∧ ∧ ∧
(b )
3,孩子兄弟链存储结构孩子兄弟链存储结构是为每个结点设计三个域：
一个数据元素域,一个该结点的第一个孩子结点指针域,一个该结点的下一个兄弟结点指针域 。 下图
（ a） 的树对应的孩子兄弟链存储结构如图 （ b） 所示 。
A
B C
F D E
(a )
G
A ∧
B
∧ D
∧ C ∧
E
∧ G ∧
∧ F ∧
( b )
7.2 二叉树概念和性质
7.2.1 二叉树概念
7.2.2 二叉树性质
7.2.3 二叉树与树、森林之间的转换
7.2.1 二叉树概念二叉树也称为二次树或二分树,它是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成 。
二叉树的定义是一种递归定义 。
二叉树有五种基本形态,如下图所示,任何复杂的二叉树都是这五种基本形态的复合 。
从定义看到,二叉树是一种特殊的树,其表示法也与树的表示法一样,有树形表示法,文氏图表示法,凹入表示法和括号表示法等 。
在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉树的最下一层,这样的二叉树称为满二叉树 。 下图所示就是一棵满二叉树 。 可以对满二叉树的结点进行连续编号,
约定编号从树根为 1开始,按照层数从小到大,同一层从左到右的次序进行 。 图中每个结点外边的数字为对该结点的编号 。
A
B C
D E
H I J K
F G
L M N O
1
2 3
4
5 6 7
8 9 10 15 11 12 13 14
满二叉树若二叉树中最多只有最下面两层的结点的度数可以小于 2,并且最下面一层的叶结点 都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树 。 如下图所示为一棵完全二叉树 。 同样可以对完全二叉树中每个结点进行连续编号,编号的方法同满二叉树相同 。 图中每个结点外边的数字为对该结点的编号 。
A
B C
D E
H I J K
F G
1
2 3
4
5 6 7
8 9 10 11
完全二叉树
7.2.2 二叉树性质性质 1 非空二叉树上叶结点数等于双分支结点数加
1。
证明：设二叉树上叶结点数为 n0,单分支结点数为 n1,双分支结点数为 n2,则总结点数 =n0+n1+n2。 在一棵二叉树中,所有结点的分支数 （ 即度数 ） 应等于单分支结点数加上双分支结点数的 2倍,即总的分支数 =n1+2n2。
由于二叉树中除根结点以外,每个结点都有惟一的一个分支指向它,因此二叉树中有：总的分支数 =总结点数 -1。
由上述三个等式可得,n1+2n2=n0+n1+n2-1
即,n0=n2+1
性质 2 非空二叉树上第 i层上至多有 2i-1个结点,这里应有 i≥1。
由树的性质 2可推出 。
性质 3 高度为 h的二叉树至多有 2h-1个结点
（ h≥1） 。
由树的性质 3可推出 。
性质 4 对完全二叉树中编号为 i的结点 （ 1≤i≤n，
n≥1,n为结点数 ） 有：
（ 1） 若 i≤?n/2?,即 2i≤n,则编号为 i的结点为分支结点,否则为叶子结点 。
（ 2） 若 n为奇数,则每个分支结点都既有左孩子结点,也有右孩子结点；若 n为偶数,则编号最大的分支结点 （ 编号为 ） 只有左孩子结点,没有右孩子结点,其余分支结点都有左,右孩子结点 。
（ 3） 若编号为 i的结点有左孩子结点,则左孩子结点的编号为 2i；若编号为 i的结点有右孩子结点,
则右孩子结点的编号为 (2i+1)。
（ 4） 除树根结点外,若一个结点的编号为 i,则它的双亲结点的编号为?i/2?,也就是说,当 i为偶数时,其双亲结点的编号为 i/2,它是双亲结点的左孩子结点,当 i为奇数时,其双亲结点的编号为 (i-1)/2，
它是双亲结点的右孩子结点 。
性质 5 具有 n个 （ n＞ 0） 结点的完全二叉树的高度为?log2n+1?或?log2n?+1。
由完全二叉树的定义和树的性质 3可推出 。
7.2.3 二叉树与树、森林之间的转换
1,森林,树转换为二叉树
（ 1） 在所有相邻兄弟结点 （ 森林中每棵树的根结点可看成是兄弟结点 ） 之间加一水平连线 。
（ 2） 对每个非叶结点 k,除了其最左边的孩子结点外,删去 k与其他孩子结点的连线 。
（ 3） 所有水平线段以左边结点为轴心顺时针旋转 45度 。
通过以上步骤,原来的森林就转换为一棵二叉树 。 一般的树是森林中的特殊情况,由一般的树转换的二叉树的根结点的右孩子结点始终为空,原因是一般的树的根结点不存在兄弟结点和相邻的树 。
A
B C D
E
F
G
H I
A
B E
F G C
D H
I
(a ) (c )
A
B C D
E
F
G
H I
(b)
将森林转换为二叉树的过程
2,二叉树还原为森林,树
（ 1） 对于一棵二叉树中任一结点 k0,沿着 k1
右孩子结点的右子树方向搜索所有右孩子结点,
即搜索结点序列 k2,k3,…,km,其中 ki+1为 ki
的右孩子结点 (1≤i＜ m),km没有右孩子结点 。
（ 2） 删去 k1,k2,…,km之间连线 。
（ 3 ） 若 k1 有双亲结点 k,则连接 k与 ki
（ 2≤i≤m） 。
（ 4） 将图形规整化,使各结点按层次排列 。
A
D H B
F C G
E
A
B
D C
F E H G
( a ) ( c )
A
B
D C
F E H G
( b)
将一棵二叉树还原为树的过程
7.3 二叉树存储结构
7.3.1 二叉树的顺序存储结构
7.3.2 二叉树的链式存储结构
7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构中结点的存放次序是：
对该树中每个结点进行编号，其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。
若把二叉树存储到一维数组中，则该编号就是下标值加 1（注意,C/C++语言中数组的起始下标为
0）。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同。
利用二叉树的性质 4。
A
B C
D E
H I J K
F G
1
2 3
4
5 6 7
8 9 10 11
完全二叉树
A B C D E F G H I J K
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
顺序存储结构
7.3.2 二叉树的链式存储结构在二叉树的链接存储中,结点的结构如下,
typedef struct node
{
ElemType data;
struct node *lchild,*rchild;
} BTNode;
其中,data表示值域,用于存储对应的数据元素,
lchild和 rchild分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点 （ 即左,右子树的根结点 ） 的存储位置 。
A
B
C
E F D
G
A
B ∧ C
∧ D ∧ E ∧ ∧ F ∧
∧ G ∧
(a) (b )
二叉树及其链式存储结构
7.4 二叉树的遍历
7.4.1 二叉树遍历的概念
7.4.2 二叉树遍历递归算法
7.4.1 二叉树遍历的概念二叉树的遍历是指按照一定次序访问树中所有结点,并且每个结点仅被访问一次的过程 。 它是最基本的运算,是二叉树中所有其他运算的基础 。
1,先序遍历先序遍历二叉树的过程是：
（ 1） 访问根结点；
（ 2） 先序遍历左子树；
（ 3） 先序遍历右子树 。
2,中序遍历中序遍历二叉树的过程是：
（ 1） 中序遍历左子树；
（ 2） 访问根结点；
（ 3） 中序遍历右子树 。
3,后序遍历后序遍历二叉树的过程是：
（ 1） 后序遍历左子树；
（ 2） 后序遍历右子树；
（ 3） 访问根结点 。
7.4.2 二叉树遍历递归算法由二叉树的三种遍历过程直接得到如下三种递归算法如下：
void PreOrder(BTNode *b) /*先序遍历的递归算法 */
{
if (b!=NULL)
{ printf("%c ",b->data); /*访问根结点 */
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
void InOrder(BTNode *b) /*中序遍历的递归算法 */
{
if (b!=NULL)
{ InOrder(b->lchild);
printf("%c ",b->data); /*访问根结点 */
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) /*后序遍历递归算法 */
{
if (b!=NULL)
{ PostOrder(b->lchild);
PostOrder(b->rchild);
printf("%c ",b->data); /*访问根结点 */
}
}
例 7.2 假设二叉树采用二叉链存储结构存储,试设计一个算法,输出一棵给定二叉树的所有叶子结点 。
解：输出一棵二叉树的所有叶子结点的递归模型 f()
如下：
f(b)：不做任何事件 若 b=NULL
f(b)：输出 *b结点的 data域 若 *b为叶子结点
f(b),f(b->lchild);f(b->rchild) 其他情况
void DispLeaf(BTNode *b)
{
if (b!=NULL)
{
if (b->lchild==NULL && b->rchild==NULL)
printf("%c ",b->data);
else
{ DispLeaf(b->lchild);
DispLeaf(b->rchild);
}
}
}
7.5 二叉树的基本运算及其实现
7.5.1 二叉树的基本运算概述
7.5.2 二叉树的基本运算算法实现
7.5.1 二叉树的基本运算概述归纳起来,二叉树有以下基本运算：
（ 1） 创建二叉树 CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串 *str生成对应的链式存储结构 。
（ 2） 查找结点 FindNode(*b,x)：在二叉树 b中寻找 data域值为 x的结点,并返回指向该结点的指针 。
（ 3） 找孩子结点 LchildNode(p)和 RchildNode(p)：
分别求二叉树中结点 *p的左孩子结点和右孩子结点 。
（ 4） 求高度 BTNodeDepth(*b)：求二叉树 b的高度 。 若二叉树为空,则其高度为 0；否则,其高度等于左子树与右子树中的最大高度加 l。
（ 5） 输出二叉树 DispBTNode(*b)：以括号表示法输出一棵二叉树 。
7.5.2 二叉树的基本运算算法实现
（ 1） 创建二叉树 CreateBTNode(*b,*str)
用 ch扫描采用括号表示法表示二叉树的字符串 。 分以下几种情况：
① 若 ch='('：则将前面刚创建的结点作为双亲结点进栈,并置 k=1,表示其后创建的结点将作为这个结点的左孩子结点；
② 若 ch=')'：表示栈中结点的左右孩子结点处理完毕,退栈；
③ 若 ch=','：表示其后创建的结点为右孩子结点；
④ 其他情况,表示要创建一个结点,并根据 k值建立它与栈中结点之间的联系,当 k=1时,表示这个结点作为栈中结点的左孩子结点,当 k=2时,表示这个结点作为栈中结点的右孩子结点 。 如此循环直到
str处理完毕 。 算法中使用一个栈 St保存双亲结点,
top为其栈指针,k指定其后处理的结点是双亲结点
（ 保存在栈中 ） 的左孩子结点 （ k=1） 还是右孩子结点 （ k=2） 。
void CreateBTNode(BTNode * &b,char *str)
{ BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL; /*建立的二叉树初始时为空 */
ch=str[j];
while (ch!='\0') /*str未扫描完时循环 */
{
switch(ch)
{
case '(':top++;St[top]=p;k=1; break;
/*为左孩子结点 */
case ')':top--;break;
case ',':k=2; break;
/*为孩子结点右结点 */
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if (b==NULL) /**p为二叉树的根结点 */
b=p;
else /*已建立二叉树根结点 */
{ switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;ch=str[j];
}
}
例如,对 于 括 号 表 示 法 字 符 串
A(B(D(,G)),C(E,F)),建立二叉树链式存储结构的过程如下表所示 。
ch 算法执行的操作 St中元素
A 建立 A结点,b指向该结点 空
( A结点进栈,k=1 A
B 建立 B结点,因 k=1,将其作为 A结点的左孩子结点
A
( B结点进栈,k=1 AB
D 建立 D结点,因 k=1,将其作为 B结点的左孩子结点
AB
( D结点进栈,k=1 ABD
,k=2 ABD
G 建立 E结点,因 k=2,将其作为 D
结点的右孩子结点
ABD
) 退栈一次 AB
) 退栈一次 A
,k=2 A
C 建立 C结点,因 k=2,将其作为 A
结点的右孩子结点
A
( C结点进栈,k=1 AC
E 建立 E结点,因 k=1,将其作为 C
结点的左孩子结点
AC
,k=2 AC
F 建立 F结点,因 k=2,将其作为 C结点的右孩子结点
AC
) 退栈一次 A
) 退栈一次 空
ch扫描完毕 算法结束
A
B ∧ C
∧ D ∧ E ∧ ∧ F ∧
∧ G ∧
（ 2） 查找结点 FindNode(*b,x)
采用先序遍历递归算法查找值为 x的结点 。 找到后返回其指针,否则返回 NULL。 算法如下：
BTNode *FindNode(BTNode *b,ElemType x)
{ BTNode *p;
if (b==NULL) return NULL;
else if (b->data==x) return b;
else { p=FindNode(b->lchild,x);
if (p!=NULL) return p;
else return FindNode(b->rchild,x);
}
}
（ 3） 找孩子结点 LchildNode(p)和 RchildNode(p)
直接返回 *p结点的左孩子结点或右孩子结点的指针 。 算法如下：
BTNode *LchildNode(BTNode *p)
{
return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
return p->rchild;
}
（ 4） 求高度 BTNodeDepth(*b)
求二叉树的高度的递归模型 f()如下：
f(NULL)=0
f(b)=MAX{f(b->lchild),f(b->rchild)}+1 其他情况对应的算法如下：
int BTNodeDepth(BTNode *b)
{ int lchilddep,rchilddep;
if (b==NULL) return(0); /*空树的高度为 0*/
else
{ lchilddep=BTNodeDepth(b->lchild);
/*求左子树的高度为 lchilddep*/
rchilddep=BTNodeDepth(b->rchild);
/*求右子树的高度为 rchilddep*/
return(lchilddep>rchilddep)?
(lchilddep+1):(rchilddep+1);
}
}
（ 5） 输出二叉树 DispBTNode(*b)
其过程是：对于非空二叉树 b,先输出其元素值,
当存在左孩子结点或右孩子结点时,输出一个,(”符号,然后递归处理左子树,输出一个,,”符号,递归处理右子树,最后输出一个,)”符号 。 对应的递归算法如下：
void DispBTNode(BTNode *b)
{ if (b!=NULL)
{ printf("%c",b->data);
if (b->lchild!=NULL || b->rchild!=NULL)
{ printf("(");
DispBTNode(b->lchild);
/*递归处理左子树 */
if (b->rchild!=NULL) printf(",");
DispBTNode(b->rchild);
/*递归处理右子树 */
printf(")");
}
}
}
例 7.3 假设二叉树采用二叉链存储结构,设计一个算法判断两棵二叉树是否相似,所谓二叉树 t1和
t2是相似的指的是 t1和 t2都是空的二叉树；或者 t1和
t2的根结点是相似的,以及 t1的左子树和 t2的左子树是相似的且 t1的右子树与 t2的右子树是相似的 。
解：判断两棵二叉树是否相似的递归模型 f()如下：
f(t1,t2)=true 若 t1=t2=NULL
f(t1,t2)=false 若 t1,t2之一为 NULL,另一不为 NULL
f(t1,t2)=f(t1->lchild,t2->lchild) & 其他情况
f(t1->rchild,t2->rchild)
对应的算法如下：
int Like(BTNode *b1,BTNode *b2)
/*t1和 t2两棵二叉树相似时返回 1,否则返回 0*/
{ int like1,like2;
if (b1==NULL && b2==NULL) return 1;
else if (b1==NULL || b2==NULL) return 0;
else
{ like1=Like(b1->lchild,b2->lchild);
like2=Like(b1->rchild,b2->rchild);
return (like1 & like2); /*返回 like1和 like2的与 */
}
}
例 7.4 假设二叉树采用二叉链存储结构,设计一个算法
Level()求二叉树中指定结点的层数 。 并利用本节的基本运算编写一个完整的程序,建立教材中图 7.8(a)的二叉树的二叉链,对于用户输入的任何结点值计算出在该二叉树中的层次 。
解：本题采用递归算法，设 h返回 p所指结点的高度，
其初值为 0。找到指定的结点时返回其层次；否则返回 0。
lh作为一个中间变量在计算搜索层次时使用，其初值为
1。对应的算法如下：
void Level(BTNode *b,BTNode *p,int &h,int lh)
/*找到 *p结点后 h为其层次,否则为 0*/
{ if (b==NULL) h=0; /*空树时返回 0*/
else if (p==b) h=lh; /*找到结点 p时 */
else
{ Level(b->lchild,p,h,lh+1); /*在左子树中递归查找 */
if (h==0) /*左子树中未找到时在右子树中递归查找 */
Level(b->rchild,p,h,lh+1);
}
}
例 7.5 假设二叉树采用二叉链存储结构,设计一个算法输出从每个叶子结点到根结点的路径 。
解：这里用层次遍历方法，设计的队列为非循环顺序队列（类似于第 3章 3.2.4小节中求解迷宫问题时使用的队列）将所有已扫描过的结点指针进队，并在队列中保存双亲结点的位置。当找到一个叶子结点时，
在队列中通过双亲结点的位置输出该叶子结点到根结点的路径。对应的算法如下：
void AllPath(BTNode *b)
{ struct snode
{ BTNode *node; /*存放当前结点指针 */
int parent; /*存放双亲结点在队列中的位置 */
} q[MaxSize]; /*定义顺序队列 */
int front,rear,p; /*定义队头和队尾指针 */
front=rear=-1; /*置队列为空队列 */
rear++;q[rear].node=b; /*根结点指针进入队列 */
q[rear].parent=-1; /*根结点没有双亲结点 */
while (front<rear) /*队列不为空 */
{ front++;
b=q[front].node; /*队头出队列 */
if (b->lchild==NULL && b->rchild==NULL)
{ printf("%c到根结点路径,",b->data);
p=front;
while (q[p].parent!=-1)
{ printf("%c->",q[p].node->data);
p=q[p].parent; }
printf("%c\n",q[p].node->data);
}
if (b->lchild!=NULL) /*左孩子结点入队列 */
{ rear++; q[rear].node=b->lchild;
q[rear].parent=front; }
if (b->rchild!=NULL) /*右孩子结点入队列 */
{ rear++; q[rear].node=b->rchild;
q[rear].parent=front; }
} /*end of while*/
}
7.6 二叉树的构造同一棵二叉树具有惟一先序序列,中序序列和后序序列,但不同的二叉树可能具有相同的先序序列,
中序序列和后序序列 。
例如，如教材中图 7.9所示的 5棵二叉树，先序序列都为 ABC。如图 7.10所示的 5棵二叉树，中序序列都为 ACB。如图 7.11所示的 5棵二叉树，后序序列都为 CBA。
显然，仅由一个先序序列（或中序序列、后序序列），无法确定这棵二叉树的树形。但是，如果同时知道一棵二叉树的先序序列和中序序列，或者同时知道中序序列和后序序列，就能确定这棵二叉树。
定理 7.1：任何 n（ n≥0） 个不同结点的二又树,都可由它的中序序列和先序序列惟一地确定 。
采用数学归纳法证明 。
当 n=0时,二叉树为空,结论正确 。
假设结点数小于 n的任何二叉树,都可以由其先序序列和中序序列惟一地确定 。
已知某棵二叉树具有 n（ n＞ 0） 个不同结点,其先序序列是 a0a1… an-1；中序序列是 b0b1… bk-1bkbk+1… bn-1。
因为在先序遍历过程中,访问根结点后,紧跟着遍历左子树,最后再遍历右子树 。 所以,a0必定是二叉树的根结点,而且 a0必然在中序序列中出现 。 也就是说,
在中序序列中必有某个 bk（ 0≤k≤n-1） 就是根结点 a0。
由于 bk是根结点,而在中序遍历过程中,先遍历左子树,再访问根结点,最后再遍历右子树 。 所以在中序序列中,b0b1… bk-1必是根结点 bk（ 也就是 a0） 左子树的中序序列,即 bk的左子树有 k个结点 （ 注意,k=0表示结点 bk没有左子树 。 ） 而 bk+1… bn-1必是根结点 bk
（ 也就是 a0） 右子树的中序序列,即 bk的右子树有 n-k-
1个结点 （ 注意,k=n-1表示结点 bk没有右子树 。 ） 。
另外,在先序序列中,紧跟在根结点 a0之后的 k个结点
a1… ak就是左子树的先序序列,ak+1… an-1这 n-k-1就是右子树的先序序列 。
根据归纳假设,由于子先序序列 a1… ak和子中序序列
b0b1… bk-1可以惟一地确定根结点 a0的左子树,而子先序序列 ak+1… an-1和子中序序列 bk+1… bn-1可以惟一地确定根结点 a0的右子树 。
综上所述，这棵二叉树的根结点己经确定，而且其左、右子树都惟一地确定了，所以整个二叉树也就惟一地确定了。
例如，已知先序序列为 ABDGCEF，中序序列为 DGBAECF，
则构造二叉树的过程如下所示。
根结点,A
左先序,BDG 左中序,DGB
右先序,CEF 右中序,ECF
根结点,B
左先序,DG左中序,DG
右先序,空 右中序,空根结点,D
左先序,空 左中序,空右先序,G 右中序,G
根结点,G
左先序,空 左中序,空右先序,空 右中序,空根结点,C
左先序,E 左中序,E
右先序,F右中序,F
根结点,E
左先序,空 左中序,空右先序,空 右中序,空根结点,F
左先序,空 左中序,空右先序,空 右中序,空由上述定理得到以下构造二叉树的算法：
BTNode *CreateBT1(char *pre,char *in,int n)
{ BTNode *s; char *p; int k;
if (n<=0) return NULL;
s=(BTNode *)malloc(sizeof(BTNode)); /*创建结点 *s*/
s->data=*pre;
for (p=in;p<in+n;p++) /*在中序中找为 *ppos的位置 k*/
if (*p==*pre)
break;
k=p-in;
s->lchild=CreateBT1(pre+1,in,k); /*递归构造左子树 */
s->rchild=CreateBT1(pre+k+1,p+1,n-k-1); /*构造右子树 */
return s;
}
定理 7.2,任何 n（ n＞ 0） 个不同结点的二又树,
都可由它的中序序列和后序序列惟一地确定 。
同样采用数学归纳法证明。
实际上，对于根结点 ak的左右子树，在确定左右子树的子中序序列后，不需要确定左右子树的整个子后序序列，只需确定子中序序列中全部字符在后序序列中最右边的那个字符即可，因为这个字符就是子树的根结点。
例如，已知中序序列为 DGBAECF，后序序列为 GDBEFCA。
对应的构造二叉树的过程如下所示。
根结点,A
左中序,DGB 左根,B
右中序,ECF右根,C
根结点,B
左中序,DG左根,D
右中序,空 右根,空根结点,D
左中序,空 左根,空右中序,G 右根,G
根结点,G
左中序,空 左根,空右中序,空 右根,空根结点,C
左中序,E 左根,E
右中序,F右根,F
根结点,E
左中序,空 左根,空右中序,空 右根,空根结点,F
左中序,空 左根,空右中序,空 右根,空由上述定理得到以下构造二叉树的算法：
BTNode *CreateBT2(char *post,char *in,int n,int m)
{ BTNode *s;char *p,*q,*maxp;int maxpost,maxin,k;
if (n<=0) return NULL;
maxpost=-1;
for (p=in;p<in+n;p++) /*求 in在 post中最右边的那个字符 */
for (q=post;q<post+m;q++) /*在 in中用 maxp指向这个字符,
用 maxin标识它在 in中的下标 */
if (*p==*q)
{ k=q-post;
if (k>maxpost)
{ maxpost=k; maxp=p; maxin=p-in; }
}
s=(BTNode *)malloc(sizeof(BTNode)); /*创建二叉树结点 *s*/
s->data=post[maxpost];
s->lchild=CreateBT2(post,in,maxin,m);
/*递归构造左子树 */
s->rchild=CreateBT2(post,maxp+1,n-maxin-1,m);
/*递归构造右子树 */
return s;
}
7.7 线索二叉树
7.7.1 线索二叉树的概念对于具有 n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有 2n个指针域，
又由于只有 n-1个结点被有效指针所指向（ n个结点中只有树根结点没有被有效指针域所指向），则共有 2n-(n-1)=n+1个空链域，
我们知道,遍历二叉树的结果是一个结点的线性序列 。 可以利用这些空链域存放指向结点的前驱和后继结点的指针 。 这样的指向该线性序列中的
,前驱,和,后继,的指针,称作线索 。
在结点的存储结构上增加两个标志位来区分这两种情况：
左标志 ltag,0 表示 lchild指向左孩子结点
1 表示 lchild指向前驱结点右标志 rtag,0 表示 rchild指向右孩子结点
1 表示 rchild指向后继结点这样,每个结点的存储结构如下：
ltag lchild data rchild rtag
按上述原则在二叉树的每个结点上加上线索的二叉树称作 线索二叉树 。 对二叉树以某种方式遍历使其变为线索二叉树的过程称作按该方式对二叉树进行 线索化 。
为使算法设计方便，在线索二叉树中再增加一个头结点。头结点的 data域为空； lchild指向无线索时的根结点,ltag为 0； rchild指向按某种方式遍历二叉树时的最后一个结点,rtag为 1。
教材中图 7.14为图 7.8(a)所示二叉树的线索二叉树。
其中，图 7.14(a)是中序线索二叉树（中序序列为：
DGBAECF），图 7.14(b)是先序线索二叉树（先序序列为,ABDGCEF），图 7.14(c)是后序线索二叉树
（后序序列为,GDBEFCA）。图中实线表示二叉树原来指针所指的结点，虚线表示线索二叉树所添加的线索。
7.7.2 线索化二叉树建立线索二叉树,或者说,对二叉树线索化,实质上就是遍历一棵二叉树,在遍历的过程中,检查当前结点的左,右指针域是否为空 。 如果为空,将它们改为指向前驱结点或后继结点的线索 。 另外,在对一棵二叉树添加线索时,我们创建一个头结点,并建立头结点与二叉树的根结点的线索 。 对二叉树线索化后,还须建立最后一个结点与头结点之间的线索 。
下面以中序线索二叉树为例,讨论建立线索二叉树的算法 。
为了实现线索化二叉树,将前面二叉树结点的类型定义修改如下：
typedef struct node
{
ElemType data; /*结点数据域 */
int ltag,rtag; /*增加的线索标记 */
struct node *lchild; /*左孩子或线索指针 */
struct node *rchild; /*右孩子或线索指针 */
} TBTNode; /*线索树结点类型定义 */
下面是建立中序线索二叉树的算法 。 CreaThread(b)
算法是将以二叉链存储的二叉树 b进行中序线索化,并返回线索化后头结点的指针 root。 Thread(p)算法用于对于以 *p为根结点的二叉树中序线索化 。 在整个算法中 p总是指向当前被线索化的结点,而 pre作为全局变量,指向刚刚访问过的结点,*pre是 *p的前驱结点,
*p是 *pre的后继结点 。
CreaThread(b)算法思路是：先创建头结点 *root，
其 lchild域为线索,rchild域为链指针。将 rchild指针指向 *b，如果 b二叉树为空，则将其 lchild指向自身。否则将 *root的 lchild指向 *b结点,p指向 *b结点,pre指向 *root结点。再调用 Thread(b)对整个二叉树线索化。
最后加入指向头结点的线索，并将头结点的 rchild指针域线索化为指向最后一个结点（由于线索化直到 p等于
NULL为止，所以最后一个结点为 *pre）。
TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树 */
{ TBTNode *root;
root=(TBTNode *)malloc(sizeof(TBTNode)); /*创建头结点 */
root->ltag=0;root->rtag=1; root->rchild=b;
if (b==NULL) root->lchild=root; /*空二叉树 */
else
{ root->lchild=b;
pre=root; /*pre是 *p的前驱结点,供加线索用 */
Thread(b); /*中序遍历线索化二叉树 */
pre->rchild=root; /*最后处理,加入指向头结点的线索 */
pre->rtag=1;
root->rchild=pre; /*头结点右线索化 */
}
return root;
}
Thread(p)算法思路是：类似于中序遍历的递归算法,
在 p指针不为 NULL时,先对 *p结点的左子树线索化；
若 *p结点没有左孩子结点,则将其 lchild指针线索化为指向其前驱结点 *pre,否则表示 lchild指向其左孩子结点,将其 ltag置为 1；若 *pre结点的 rchild指针为
NULL,将其 rchild指针线索化为指向其后继结点 *p，
否则 rchild表示指向其右孩子结点,将其 rtag置为 1，
再将 pre指向 *p；最后对 *p结点的右子树线索化 。
TBTNode *pre; /*全局变量 */
void Thread(TBTNode *&p) /*对二叉树 b进行中序线索化 */
{ if (p!=NULL)
{ Thread(p->lchild); /*左子树线索化 */
if (p->lchild==NULL) /*前驱线索 */
{ p->lchild=pre; p->ltag=1;} /*建立当前结点的前驱线索 */
else p->ltag=0;
if (pre->rchild==NULL) /*后继线索 */
{ pre->rchild=p;pre->rtag=1;}/*建立前驱结点的后继线索 */
else pre->rtag=0;
pre=p;
Thread(p->rchild); /*递归调用右子树线索化 */
}
}
7.7.3 遍历线索化二叉树遍历某种次序的线索二叉树，就是从该次序下的开始结点出发，反复找到该结点在该次序下的后继结点，
直到终端结点。
在中序线索二叉树中，开始结点就是根结点的最左下结点，而求当前结点在中序序列下的后继和前驱结点的方法如教材中表 7.2所示，最后一个结点的 rchild指针被线索化为指向头结点。利用这些条件，在中序线索化二叉树中实现中序遍历的算法如下：
void ThInOrder(TBTNode *tb)
{ TBTNode *p=tb->lchild; /*p指向根结点 */
while (p!=tb)
{ while (p->ltag==0) p=p->lchild; /*找开始结点 */
printf("%c",p->data); /*访问开始结点 */
while (p->rtag==1 && p->rchild!=tb)
{ p=p->rchild;
printf("%c",p->data);
}
p=p->rchild;
}
}
7.8 哈夫曼树
7.8.1 哈夫曼树的定义
7.8.2 构造哈夫曼树
7.8.3 哈夫曼编码
7.8.1 哈夫曼树的定义设二叉树具有 n个带权值的叶子结点,那么从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和,叫做二叉树的带权路径长度 。
其中,n表示叶子结点的数目,wi和 li分别表示叶子结点 ki的权值和根到 ki之间的路径长度
（ 即从叶子结点到达根结点的分支数 ） 。
具有最小带权路径长度的二叉树称为哈夫曼树 。
n
i
ii lwW P L
1
7.8.2 构造哈夫曼树根据哈夫曼树的定义,一棵二叉树要使其 WPL值最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点 。 那么如何构造一棵哈夫曼树呢?其方法如下,
（ 1） 由给定的 n个权值 {W1,W2,...,Wn}构造 n棵只有一个叶子结点的二叉树,从而得到一个二叉树的集合 F={T1,T2,...,Tn};
（ 2） 在 F中选取根结点的权值最小和次小的两棵二叉树作为左,右子树构造一棵新的二叉树,这棵新的二叉树根结点的权值为其左,右子树根结点权值之和 ;
（ 3） 在集合 F中删除作为左,右子树的两棵二叉树,
并将新建立的二叉树加入到集合 F中 ;
（ 4） 重复 (2),(3)两步,当 F中只剩下一棵二叉树时,
这棵二叉树便是所要建立的哈夫曼树 。
给定权值 w=(1,3,5,7)来构造一棵哈夫曼树 。
9
4
1
7
5
3
16
9
4
1
7
5
3
(c ) (d )
1 3 5 7
4 5 7
1 3
(a ) (b )
为了实现构造哈夫曼树的算法,设计哈夫曼树中每个结点类型如下：
typedef struct
{ char data; /*结点值 */
float weight; /*权重 */
int parent; /*双亲结点 */
int lchild; /*左孩子结点 */
int rchild; /*右孩子结点 */
} HTNode;
用 ht[]数组存放哈夫曼树，对于具有 n个叶子结点的哈夫曼树，总共有 2n-1个结点。其算法思路是,n个叶子结点只有 data和 weight域值，先将所有 2n-1个结点的 parent,lchild和 rchild域置为初值 -1。处理每个非叶子结点 ht[i]（存放在 ht[n]～ ht[2n-2]中）：从 ht[0] ～
ht[i-2]中找出根结点（即其 parent域为 -1）最小的两个结点 ht[lnode]和 ht[rnode]，将它们作为 ht[i]的左右子树，
ht[lnode]和 ht[rnode]的双亲结点置为 ht[i]，并且
ht[i].weight=ht[lnode].weight+ht[rnode].weight。如此这样直到所有 2n-1个非叶子结点处理完毕。
构造哈夫曼树的算法如下：
void CreateHT(HTNode ht[],int n)
{ int i,j,k,lnode,rnode; float min1,min2;
for (i=0;i<2*n-1;i++) /*所有结点的相关域置初值 -1*/
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n;i<2*n-1;i++) /*构造哈夫曼树 */
{ min1=min2=32767; lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1)/*未构造二叉树的结点中查找 */
{ if (ht[k].weight<min1)
{ min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k; }
else if (ht[k].weight<min2)
{ min2=ht[k].weight;rnode=k; } } /*if*/
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}
7.8.3 哈夫曼编码具体构造方法如下：设需要编码的字符集合为
{d1,d2,…,dn},各个字符在电文中出现的次数集合为
{w1,w2,…,wn},以 d1,d2,…,dn作为叶结点,以 w1，
w2,…,wn作为各根结点到每个叶结点的权值构造一棵二叉树,规定哈夫曼树中的左分支为 0,右分支为 1，
则从根结点到每个叶结点所经过的分支对应的 0和 1组成的序列便为该结点对应字符的编码 。 这样的编码称为哈夫曼编码 。
对应的哈夫曼编码如下：
1,000 3,001 5,01 7,1
为了实现构造哈夫曼编码的算法,设计存放每个结点哈夫曼编码的类型如下：
typedef struct
{
char cd[N]; /*存放当前结点的哈夫曼码 */
int start;
} HCode;
根据哈夫曼树求对应的哈夫曼编码的算法如下：
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{ int i,f,c; HCode hc;
for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码 */
{ hc.start=n;c=i; f=ht[i].parent;
while (f!=-1) /*循环直到无双亲结点即到达树根结点 */
{ if (ht[f].lchild==c) /*当前结点是左孩子结点 */
hc.cd[hc.start--]='0';
else /*当前结点是双亲结点的右孩子结点 */
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent; /*再对双亲结点进行同样的操作 */
}
hc.start++;/*start指向哈夫曼编码最开始字符 */
hcd[i]=hc;
}
}
本章小结本章的基本学习要点如下：
（ 1） 掌握树的相关概念,包括树,结点的度,
树的度,分支结点,叶子结点,儿子结点,双亲结点,树的深度,森林等定义 。
（ 2） 掌握树的表示,包括树形表示法,文氏图表示法,凹入表示法和括号表示法等 。
（ 3） 掌握二叉树的概念,包括二叉树,满二叉树和完全二叉树的定义 。
（ 4） 掌握二叉树的性质 。
（ 5） 重点掌握二叉树的存储结构,包括二叉树顺序存储结构和链式存储结构 。
（ 6） 重点掌握二叉树的基本运算和各种遍历算法的实现 。
（ 7） 掌握线索二叉树的概念和相关算法的实现 。
（ 8） 掌握哈夫曼树的定义,哈夫曼树的构造过程和哈夫曼编码产生方法 。
（ 9） 灵活运用二叉树这种数据结构解决一些综合应用问题 。
练习教材中 p170的习题 1,2,4,6和 7。
上机实习题教材中 p170题 1,3和 7。
