1北京邮电大学自动化学院
第六章 树和二叉树
? 6.1 树的定义和基本概念
? 6.2 二叉树
? 6.3 遍历二叉树
? 6.4 树和森林
? 6.5 赫夫曼树及其应用
2北京邮电大学自动化学院
? 树型结构是一类重要的非线性结构 。树结构在客观世界里是大
量存在的，树在计算机领域中也有着广泛的应用，例如在编译
程序中，用树来表示源程序的语法结构；在数据库系统中，可
用树来组织信息；在分析算法的行为时，可用树来描述其执行
过程等等。
6.1 树的定义和基本术语
? 1、定义 树是 n(n>=0)个结点的有限集 T,T为空时称为空
树，否则它满足如下两个条件：
? （ 1）有且仅有一个特定的称为根的结点；
? （ 2）当 n>1时，其余结点可分为 m(m>0)个互不相交的有限集
T1,T2,T3…Tm,其中每个子集又是一棵树，并称其为根的子
树。
3北京邮电大学自动化学院
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根
子树
1、定义
4北京邮电大学自动化学院
? 结点 —— 表示树中的元素，包括数据项及若干指向其子树的分支
2、基本术语
? 结点的度 (degree)—— 结点拥有的子树数
? 叶子 (leaf)—— 度为 0的结点
? 孩子 (child)—— 结点子树的根称为该结点的孩子
? 双亲 (parents)—— 孩子结点的上层结点叫该结点的 ~
? 兄弟 (sibling)—— 同一双亲的孩子
? 树的度 —— 一棵树中最大的结点度数
? 结点的层次 (level)—— 从根结点算起，根为第一层，它的孩子
为第二层 ……
? 深度 (depth)—— 树中结点的最大层次数
? 森林 (forest)—— m(m?0)棵互不相交的树的集合
5北京邮电大学自动化学院
A
B C D
E F G H I J
K L M
结点 A的度,3
结点 B的度,2
结点 M的度,0
叶子,K,L,F,G,M,I,J
结点 A的孩子,B,C,D
结点 B的孩子,E,F
结点 I的双亲,D
结点 L的双亲,E
结点 B,C,D为兄弟
结点 K,L为兄弟
树的度,3
结点 A的层次,1
结点 M的层次,4
树的深度,4
结点 F,G为堂兄弟
结点 A是结点 F,G的祖先
2、基本术语
6北京邮电大学自动化学院
6.2 二叉树
? 二叉树在树结构的应用中起着非常重要的作用，因为对二叉
树的许多操作算法简单，而任何树都可以与二叉树相互转
换，这样就解决了树的存储结构及其运算中存在的复杂性。
? 定义,二叉树是由 n(n>=0)个结点的有限集合构成，此集合
或者为空集，或者由一个根结点及两棵互不相交的左右子树
组成，并且左右子树都是二叉树。
? 这也是一个递归定义。二叉树可以是空集合，根可以有空的
左子树或空的右子树。二叉树不是树的特殊情况，它们是两
个概念。
7北京邮电大学自动化学院
(a)
空二叉树
A A
B
A
B
A
CB
(b)
根和空的
左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树
? 图 6.3二叉树的 5种形式
? 二叉树结点的子树要区分左子树和右子树，即使只有一棵
子树也要进行区分，说明它是左子树，还是右子树。这是
二叉树与树的最主要的差别。图 6.3列出二差树的 5种基本
形态，图 6.3(C) 和图 6.3（ d）是不同的两棵二叉树。
6.2 二叉树
8北京邮电大学自动化学院
? 6.2.2 二叉树的性质
? 二叉树具有下列重要性质：
? 性质 1,在二叉树的第 i层上至多有 2i-1个结点 (i>=1)。
? 采用归纳法证明此性质。
? 当 i=1时，只有一个根结点,2i-1=20 =1,命题成立。
? 现在假定对所有的 j,1<=j<i，命题成立，即第 j层上至多有
2j-1个结点，那么可以证明 j＝ i时命题也成立。由归纳假设可
知，第 i－ 1层上至多有 2i-2个结点。
? 由于二叉树每个结点的度最大为 2，故在第 i层上最大结点数
为第 i－ 1层上最大结点数的二倍，
? 即 2× 2i-2＝ 2i-1。命题得到证明。
9北京邮电大学自动化学院
? 性质 2：深度为 k的二叉树至多有 2k－ 1个结点（ k>=1).
122
1 1
1 ???? ?
? ?
? kk
i
k
i
ii 层上的最大结点数）（第
? 性质 3,对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2的
结点数为 n2，则 n0＝ n2＋ 1。
? 深度为 k的二叉树的最大的结点数为二叉树中每层上的最大结点
数之和，由性质 1得到每层上的最大结点数，
? 设二叉树中度为 1的结点数为 n1，二叉树中总结点数为 N，因为二
叉树中所有结点均小于或等于 2，所以有：
? N＝ n0＋ n1＋ n2 (6-1)
? 再看二叉树中的分支数，除根结点外，其余结点都有一个进入分
支，设 B为二叉树中的分支总数，
? 则有,N＝ B＋ 1。
10北京邮电大学自动化学院
? 由于这些分支都是由度为 1和 2的结点射出的，所以有：
? B＝ n1+2*n2
? N＝ B＋ 1＝ n1＋ 2× n2＋ 1 （ 6－ 2)
? 由式（ 6－ 1）和（ 6－ 2）得到：
? N＝ n0＋ n1＋ n2 （ 6-1）
? 性质 3,对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2的
结点数为 n2，则 n0＝ n2＋ 1。
? n0+n1+n2=n1+2*n2+1
? n0＝ n2＋ 1
11北京邮电大学自动化学院
图 6.4 满二叉树
2
4 5
3
6 7
1
（ 1）满二叉树
? 一棵深度为 k且由 2k-1个结点的二叉树称为满二叉树。
图 6.4就是一棵满二叉树，对结点进行了顺序编号。
下面介绍两种特殊形态的二叉树,满二叉树和完全二叉树。
12北京邮电大学自动化学院
1
2 3
4 5 6
（ a）完全二叉树
1
2 3
4 5 7
（ b）非完全二叉树
1
2 3
6 7
（ c）非完全二叉树
图 6.5 完全二叉树
（ 2）完全二叉树
? 如果深度为 k、由 n个结点的二叉树中每个结点能够与深度为
k的顺序编号的满二叉树从 1到 n标号的结点相对应，则称这
样的二叉树为 完全二叉树,图 6.5（ b）、（ c）是 2棵非完全
二叉树。满二叉树是完全二叉树的特例。
13北京邮电大学自动化学院
完全二叉树的特点
? （ 1）所有的叶结点都出现在第 k层或 k－ 1层。
? （ 2）对任一结点，若其右分支下的子孙的最大层次为 l，则其
左分支下的子孙的最大层次必为 l或 l＋ 1。
? 性质 4：具有 n个结点的完全二叉树的深度为 ?log2n?＋ 1。
? 符号 ?x?表示不大于 x的最大整数。
? 假设此二叉树的深度为 k，则根据性质 2及完全二叉树的定义得：
?2k-1－ 1<n<=2k-1 或 2k-1<=n<2k
? 取对数得到,k－ 1?log2n<k 因为 k是整数。所以有：
?k＝ ? log2n ?＋ 1
14北京邮电大学自动化学院
? 性质 5,如果对一棵有 n个结点的完全二叉树的结点按层序
编号（从第 1层到第 ?log2n ?+1层，每层从左到右 ),则对任一
结点 i（ 1<=i<=n),有：
? （ 1）如果 i＝ 1，则结点 i无双亲，是二叉树的根；如果 i>1，
则其双亲是结点 ?i/2 ? 。
? （ 2）如果 2i>n，则结点 i为叶子结点，无左孩子；否则，其
左孩子是结点 2i。
? （ 3）如果 2i＋ 1>n，则结点 i无右孩子；否则，其右孩子是
结点 2i＋ 1。
15北京邮电大学自动化学院
? 图 6.6 完全二叉树中结点 i和 i+1
[i/2]
i i+1
2i 2i+1 2(i+1) 2i+3
(a) i和 i+1结点在同一层
i+1
2(i+1) 2i+3
i
2i 2i+1
? (b)i和 i+1结点不在同一层
? 我们只要先证明（ 2）和（ 3），便可以从（ 2）和（ 3）推出（ 1）。
? 对于 i＝ 1，由完全二叉树的定义，其左孩子是结点 2，若 2>n，
即不存在结点 2，此时，结点 i无孩子。结点 i的右孩子也只能是
结点 3，若结点 3不存在，即 3>n，此时结点 i无右孩子。
16北京邮电大学自动化学院
图 6.6 完全二叉树中结点 i和 i+1
[i/2]
i i+1
2i 2i+1 2(i+1) 2i+3
(a) i和 i+1结点在同一层
i+1
2(i+1) 2i+3
i
2i 2i+1
(b)i和 i+1结点不在同一层
? 对于 i>1，可分为两种情况：
? （ 1）设第 j（ 1?j??log2n?)层的第一个结点的编号为 i（由二叉
树的定义和性质 2可知 i＝ 2j-1），则其左孩子必定为 j＋ 1层的
第一个结点，其编号为 2j＝ 2× 2j-1＝ 2i。如果 2i>n，则无左孩
子；
? 其右孩子必定为第 j＋ 1层的第二个结点，编号为 2i＋ 1。若
2i+1>n，则无右孩子。
17北京邮电大学自动化学院
图 6.6 完全二叉树中结点 i和 i+1
[i/2]
i i+1
2i 2i+1 2(i+1) 2i+3
(a) i和 i+1结点在同一层
i+1
2(i+1) 2i+3
i
2i 2i+1
(b)i和 i+1结点不在同一层
? （ 2）假设第 j（ 1?j??log2n?)层上的某个结点编号为 i（ 2 j-1?i<2j-
1)，且 2i＋ 1<n，则其左孩子为 2i，右孩子为 2i＋ 1.
? 又编号为 i＋ 1的结点是编号为 i的结点的右兄弟或堂兄弟。若它有
左孩子，则其编号必定为 2i＋ 2＝ 2× （ i＋ 1）；若它有右孩子，
则其编号必定为 2i＋ 3＝ 2× （ i＋ 1）＋ 1。
18北京邮电大学自动化学院
? 图 6.6 完全二叉树中结点 i和 i+1
[i/2]
i i+1
2i 2i+1 2(i+1) 2i+3
(a) i和 i+1结点在同一层
i+1
2(i+1) 2i+3
i
2i 2i+1
? (b)i和 i+1结点不在同一层
? 当 i＝ 1时，就是根，因此无双亲。
? 当 i>1时，如果 i为左孩子，即 2× （ i/2)=i，则 i/2是 i的双
亲；如果 i为右孩子,i＝ 2p+1,i的双亲应为 p,p＝（ i－
1） /2=?i/2?。 证毕。
19北京邮电大学自动化学院
? 1、顺序存储结构
6.2.3 二叉树的存储结构
? #define MAX-TREE-SIZE 100
? Typedef TelemType SqBiTree[ MAX-TREE-SIZE];
? SqBitree bt;
? 按照顺序存储结构的定义，在此约定，用一组地址连续的
存储单元依次自上而下，自左至右存储完全二叉树上的结
点元素，即将完全二叉树上编号为 i的的结点元素存储在
如上定义的一维数组中下标为 i-1的分量中。
20北京邮电大学自动化学院
a b c d e f g h i j k l
1 2 3 4 5 6 7 8 9 10 11 12
a
b c
d e f g
h i j k l
1、顺序存储结构
完全二叉树
21北京邮电大学自动化学院
a
b c
d e
f g
? 从树根起，自上层至下层，每层自左至右的给所有结点编号,
一般二叉树
? 缺点是有可能对存储空间造成极大的浪费，在最坏的情况
下，一个深度为 h且只有 h个结点的右单支树，却需要 2h-1个
结点存储空间。而且，若经常需要插入与删除树中结点时，
顺序存储方式不是很好！
a b c d e 0 0 0 0 f g
1 2 3 4 5 6 7 8 9 10 11
22北京邮电大学自动化学院
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree; A
B
C D
E F
G
? 在 n个结点的二叉链表中，有 n+1个空指针域
A
B
C D
E F
G
^
^ ^
^ ^ ^
^ ^
? 二叉链表,二叉树的每一个结点最多有左、右两棵子树，故链
表的结点结构除数据域外可设两个链域：左孩子（ lc）、右孩
子（ rc）分别指向左、右孩子。 称结点由两个链域组成的链表
为二叉链表。
2、链式存储结构
lchild data rchild
23北京邮电大学自动化学院
? typedef struct node
? { datatype data;
? struct node *lchild,*rchild,*parent;
? }JD;
A
B
C D
E F
G
A
B
C D
E F
G
^ ^
^ ^
^ ^ ^
^ ^
? 三叉链表,有时为了便于找到双亲结点，另设一个指向双亲的
链域，结点由三个链域组成的链表称为 三叉链表 。
lchild data parent rchild
24北京邮电大学自动化学院
? 线索链表,用链表表示的二叉树中也会存在许多空链域。例如
在含有 n个结点的二叉链表中，共有 2n个链域，实用 n-1链域
（仅有 n-1个分支），还有 n+1个空链域。（可以利用这些空链
域存储其它有用信息，从而得到另一种链式存储结构 —— 线索
链表 。）
6.3 遍历二叉树和线索二叉树
? 6.3.1 遍历二叉树
? 1、定义及递归算法
? 遍历二叉树,是指按一定的次序系统地访问二叉树中所有结
点，而且仅被访问一次。
? 访问,所谓“访问”可以是对结点作各种处理，如输出结点数
据域值。
25北京邮电大学自动化学院
? 二叉树是由三个基本单元组成,根结点、左子树和右子树。
因此，若能依次遍历这三部分，便是遍历了整个二叉树。
? 假如以 L,D,R分别表示遍历左子树、访问根结点和遍历右
子树，则可能有,DLR,LDR,LRD,DRL,RDL,RLD六
种遍历二叉树的方案。
? 若限定先左后右，则只有前三种情况，分别称之为 先（根）
序遍历，中（根）序遍历和后（根）序遍历。
6.3.1 遍历二叉树
26北京邮电大学自动化学院
先序遍历算法
? 若二叉树为空树，则空操作；否则，
? （ 1）访问根结点；
? （ 2）先序遍历左子树；
? （ 3）先序遍历右子树。
? void PreOrder（ BiTree bt） {/*先序遍历二叉树 bt*/
? if (bt==NULL) return; /*递归调用的结束条件 */
? Visite（ bt->data） ; /*访问结点的数据域 */
? PreOrder（ bt->lchild） ; /*先序递归遍历 bt的左子树 */
? PreOrder（ bt->rchild） ;/*先序递归遍历 bt的右子树 */}
27北京邮电大学自动化学院
A
D
B C
D L R
A
D L R
D L R
B
D
C
D L R
先序遍历序列,A B D C
先序遍历,
先序遍历
28北京邮电大学自动化学院
void preorder(JD *bt)
{ if(bt!=NULL)
{ printf("%d\t",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
主程序
Pre( T )
返回
返回
pre(T
R);
返回
返回
pre(T
R);
A
CB
D
T B
printf(B);
pre(T
L);
T A
printf(A);
pre(T
L);
T D
printf(D);
pre(T
L);
T C
printf(C);
pre(T
L);
返回
T
左是空返回
pre(T
R);
T
左是空返回
T
右是空返回
T
左是空返回
T
右是空返回
pre(T
R);
先序序列,A B D C
29北京邮电大学自动化学院
? 若二叉树为空树，则空操作；否则，
中序遍历算法
? （ 1）中序遍历左子树；
? （ 2）访问根结点；
? （ 3）中序遍历右子树。
? void InOrder（ BiTree bt） {/*中序遍历二叉树 bt*/
? if (bt==NULL) return; /*递归调用的结束条件 */
? InOrder（ bt->lchild） ; /*中序递归遍历 bt的左子 */
? Visite（ bt->data） ; /*访问结点的数据域 */
? InOrder（ bt->rchild） ; /*中序递归遍历 bt的右子树 */}
30北京邮电大学自动化学院
A
D
B C
L D R
B
L D R
L D R
A
D
C
L D R
中序遍历序列,B D A C
中序遍历
中序遍历算法
31北京邮电大学自动化学院
后序遍历算法
? 若二叉树为空树，则空操作；否则，
? （ 1）后序遍历左子树；
? （ 2）后序遍历右子树；
? （ 3）访问根结点。
? void PostOrder（ BiTree bt） {/*后序遍历二叉树 bt*/
? if (bt==NULL) return; /*递归调用的结束条件 */
? PostOrder（ bt->lchild） ;/*后序递归遍历 bt的左子树 */
? PostOrder（ bt->rchild） ; /*后序递归遍历 bt的右子树 */
? Visite（ bt->data） ; /*访问结点的数据域 */}
32北京邮电大学自动化学院
A
D
B C
L R D
L R D
L R D
A
D
C
L R D
后序遍历序列,D B C A
后序遍历,
B
后序遍历算法
33北京邮电大学自动化学院
? 所谓二叉树的 层次遍历,是指从二叉树的第一层（根结点）
开始，从上至下逐层遍历，在同一层中，则按从左到右的顺
序对结点逐个访问。
层次遍历
2
4 5
3
6 7
1
34北京邮电大学自动化学院
A
B
C
D
E
F
G
H K
例如,先序序列：
中序序列：
后序序列：
A B C D E F G H K
B D C A E H G K F
D C B H K G F E A
层次序列：
A B E C F D G H K
35北京邮电大学自动化学院
? 例如图（ 1）所示的二叉树表达式
? 按中序遍历,其中序序列为：
? a+b*c-d-e/f
－
＋
*a
/
b -
dc
fe
?(a+b*(c-d)-e/f)
? 若先序遍历 此二叉树，按访问结点的先后次序将结点排
列起来,其先序序列为,-+a*b-cd/ef
? 按后序遍历,其后序序列为：
? abcd-*+ef/ -
? 人喜欢中缀形式 的算术表达式，对于
计算机，使用后缀易于求值 图
（ 1）
36北京邮电大学自动化学院
? （ 1）查询二叉树中某个结点
2、二叉树其它操作的算法
? （ 1）查询二叉树中某个结点
? 在二叉树不空的前提下，和根结点的元素进行比较。若相
等，则找到返回 TRUE;
? 否则在左子树中进行查找，若找到，则返回 TRUE;
? 否则继续在右子树中进行查找,若找到，则返回 TRUE，否
则返回 FALSE。
? （ 2）计算二叉树中叶子结点的个数
? （ 3）求二叉树的深度 (后序遍历 )
? （ 4）按先序遍历序列建立二叉树
37北京邮电大学自动化学院
Status Preorder (BiTree T,ElemType x,BiTree &p) {
// 若二叉树中存在和 x 相同的元素，则 p 指向该结点并返回 OK,
// 否则返回 FALSE
}
if (T) {
if (T->data==x) { p = T; return OK,}
}//if
else return FALSE;
else {
if (Preorder(T->lchild,x,p) return OK;
else return (Preorder(T->rchild,x,p)) ;
}//else
38北京邮电大学自动化学院
? 算法基本思想,先序 (或中序或后序 )遍历二叉树，在遍历过
程中查找叶子结点，并计数。
（ 2）计算二叉树中叶子结点的个数
? 由此，需在遍历算法中增添一个“计数”的参数，并将
算法中“访问结点” 的操作改为,若是叶子，则计数器增
1。
39北京邮电大学自动化学院
void CountLeaf (BiTree T,int& count){
if ( T ) {
if ((!T->lchild)&& (!T->rchild))
count++; // 对叶子结点计数
CountLeaf( T->lchild,count);
CountLeaf( T->rchild,count);
} // if
} // CountLeaf
40北京邮电大学自动化学院
int CountLeaf (BiTree T){
//返回指针 T所指二叉树中所有叶子结点个数
if (!T ) return 0;
if (!T->lchild && !T->rchild) return 1;
else{
m = CountLeaf( T->lchild);
n = CountLeaf( T->rchild);
return (m+n);
} //else
} // CountLeaf
41北京邮电大学自动化学院
int Count (BiTree T){
//返回指针 T所指二叉树中所有结点个数
if (!T ) return 0;
if (!T->lchild && !T->rchild) return 1;
else{
m = Count ( T->lchild);
n = Count ( T->rchild);
return (m+n+1);
} //else
} // CountLeaf
42北京邮电大学自动化学院
? 算法基本思想,首先分析二叉树的深度和它的左、右子树
深度之间的关系
（ 3）求二叉树的深度 (后序遍历 )
? 从二叉树深度的定义可知，二叉树的深度应为其左、右子
树深度的最大值加 1。由此，需先分别求得左、右子树的
深度，算法中“访问结点”的操作为,求得左、右子树深度
的最大值，然后加 1 。
43北京邮电大学自动化学院
? int Depth (BiTree T ){ // 返回二叉树的深度
? if ( !T ) depthval = 0; else {
? depthLeft = Depth( T->lchild );
? return depthval;
? }
（ 3）求二叉树的深度 (后序遍历 )
? depthRight= Depth( T->rchild );
? depthval = 1 + (depthLeft > depthRight?
? depthLeft, depthRight);
? }
44北京邮电大学自动化学院
A
B
C D
E F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^
（ 4）按先序遍历序列建立二叉树
? 建立二叉树的方法很多，这里介绍一个基于先序遍历的构
造方法。算法的输入是二叉树的先序序列，但必须在其中
加入空指针。若用,?”表示空指针，要建立下图中所示的
二叉树，其输入序列为：
? A B C ? ? D E ? G ? ? F ? ? ?
45北京邮电大学自动化学院
? Status CreateBiTree (BiTree &T ){ //按先序次序输入二叉树
中结点的值（一个字符），空格字符表示空树，构造二叉链
表表示的二叉树 T
? scanf (&ch);
? if ( ch==‘ ‘ ) T=NULL; else {
? if(!T=(BiTNode *)malloc(sizeof(BiTNode)))) exit
(OVERFLOW);
? T->data=ch; //生成根结点
? CreateBiTree(T->lchild);//构造左子树
? CreateBiTree(T->rchild);//构造右子树 }
? Return OK; }//CreateBiTree
46北京邮电大学自动化学院
3、遍历二叉树的非递归算法
? （ 1）先序遍历非递归算法
? 当找到没有左孩子的结点时，从栈顶退出某结点的右
孩子，此时该结点的左子树已遍历完
? 再按上述过程遍历该结点的右子树。
? 使用栈实现先序遍历二叉树的基本思想是：
? 从二叉树的根结点开始，沿左支一直走到没有左孩子的结点
为止，在走的过程中访问所遇到的结点，并把非空右孩子进
栈。
47北京邮电大学自动化学院
? void inorder(JD *r)//先序遍历二叉树非递归算法 //
? { int i=0; JD *p,*s[M]; p=r;
3、遍历二叉树的非递归算法
? do { while(p!=NULL)
? { printf("%d\t",p->data);
? s[i++]=p->rc;
? if ( i > 0) p=s[--i];
? }while( i>0 || p!=NULL); }
? if (p->rc!=NULL)
? p=p->lc; }
48北京邮电大学自动化学院
（ 2）中序遍历二叉树的非递归算法
? 使用栈实现中序遍历的二叉树的基本思想与先序遍历类
同，只是在沿左支向前走的过程中将所遇到结点进栈，待
到遍历完左子树时，从栈顶退出结点并访问，然后再遍历
右子树。
49北京邮电大学自动化学院
? 非递归算法
A
B
C D
E F
G
p
i
P->A
(1)
A
B
C D
E F
G
p
i
P->A
P->B
(2)
A
B
C D
E F
G
p i
P->A
P->B
P->C
(3)
p=NUL
L
A
B
C D
E F
G
i
P->A
P->B
访问,C(4)
50北京邮电大学自动化学院
p A
B
C D
E F
G
i
P->A
访问,C B(5)
A
B
C D
E F
G
i
P->A
P->D
访问,C B
p
(6)
A
B
C D
E F
G
i
P->A
P->D
P->E
访问,C B
p
(7)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E
p (8)
51北京邮电大学自动化学院
A
B
C D
E F
G
i
P->A
P->D
P->G
访问,C B E
P=NULL
(9)
A
B
C D
E F
G
i
P->A
访问,C B E G D
p
(11)
A
B
C D
E F
G
i
P->A
P->F
访问,C B E G D
p
(12)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E G
p
(10)
52北京邮电大学自动化学院
A
B
C D
E F
G
i
P->A
访问,C B E G D F
p=NULL
(13)
A
B
C D
E F
G
i
访问,C B E G D F A
p
(14)
A
B
C D
E F
G
i
访问,C B E G D F A
p=NULL
(15)
53北京邮电大学自动化学院
（ 3）后序遍历二叉树的非递归算法
? 使用栈实现后序遍历的二叉树要比先序和中序遍历复杂一
些。每个结点要等到遍历左、右子树之后才得以访问，所
以在去遍历左、右子树之前，结点都需要进栈。
? 因此设两个栈，分别称为结点栈（ S1[M]）和标志栈
（ S2[M]），标志栈中存放进 S1栈结点的标记。标记,0”
表明结点在遍历左子树时进栈，标记,1”表明结点在遍历
右子树时进栈。
? 当它出栈时，需要判断是从遍历左子树后的返回（即遍历
完左子树，需要继续遍历右子树），还是从遍历右子树后
的返回（即遍历完右子树，需要访问这个结点）。
54北京邮电大学自动化学院
? 仅知二叉树的先序序列,abcdefg” 不能唯一确定一棵二叉
树，
? 如果同时已知二叉树的中序序列,cbdaegf”,则会如何？
? 二叉树的先序序列
? 二叉树的中序序列 左子树
左子树 右子树
右子树
根
根
4、由结点先序序列和中序序列构造对应的二叉树
55北京邮电大学自动化学院
? 根据先序遍历的定义，先序序列中的第一个元素一定是二
叉树的根结点。由中序遍历定义可知，中序序列中根结点
恰为左、右子树的中序序列的分界点。于是根结点元素把
中序序列划分两个子序列，左子树的中序序列和右子树的
中序序列。
? 然后根据左子树的中序序列结点个数在先序序列中找到对
应的左子树的先序序列和右子树的先序序列。
? 由此可建立一个根结点，再确定其左、右子树各自的中序
序列和先序序列。
? 然后用同样的方法分别找出其左、右子树的根结点及子树
根结点的左、右子树各自的中序序列和先序序列，依次类
推，直到所得左、右子树中包含一个结点为止。
4、由结点先序序列和中序序列构造对应的二叉树
56北京邮电大学自动化学院
? 上述过程是一个递归过程，其递归算法的思想是：先根据先序
序列的第一个元素建立根结点；
? 二叉树的先序序列
? 二叉树的中序序列 左子树
左子树 右子树
右子树
根
根
? 然后在中序序列中找到该元素，确定根结点的左、右子树的中
序序列；
? 再在先序序列中确定左、右子树的先序序列；
? 最后由左子树的先序序列与中序序列建立左子树，由右子树的
先序序列与中序序列建立右子树。
57北京邮电大学自动化学院
? 同样的道理，由二叉树的后序序列和中序序列也可唯一地
确定一棵二叉树。
? 因为，依据后序遍历和中序遍历的定义，后序序列的最后
一个结点，就如同先序序列的第一个结点一样，可将中序
序列分成两个子序列，分别为这个结点的左子树的中序序
列和右子树的中序序列，再拿出后序序列的倒数第二个结
点，并继续分割中序序列，如此递归下去，当倒着取取尽
后序序列中的结点时，便可以得到一棵二叉树。
4、由结点先序序列和中序序列构造对应的二叉树
58北京邮电大学自动化学院
a b c d e f g
c b d a e g f
例如, b f
a
b
c d
e
f
g
^ ^ ^ ^
^
^ ^
^
先序序列
中序序列
59北京邮电大学自动化学院
? 线索二叉树,以二叉链表作为存储结构时,只能找到结点的左
右孩子的信息,而不能在结点的任一序列的前驱与后继信息,这
种信息只有在遍历的动态过程中才能得到,为了能保存所需的
信息,可增加标志域 ;
lchild Ltag data Rtag rchild
6.3.2 线索二叉树
Ltag=
Rtag=
? 其中, 0 lchild 域指示结点的左孩子
1 lchild 域指示结点的前驱
? 以这种结构构成的二叉链表作为二叉树的存储结构,叫做线
索链表,其中指向结点前驱与后继的指针叫做线索，加上线
索的二叉树称之为线索二叉树。
0 rchild 域指示结点的右孩子
1 rchild 域指示结点的后驱
60北京邮电大学自动化学院
A
B D
C E
T
? 先序序列,ABCDE
? 先序线索二叉树
0 0
0 01 1
1 1 ^1 1
A
B
C
D
E
1、先序线索二叉树
61北京邮电大学自动化学院
A
B
C
D
E
A
B D
C E
T
? 中序序列,BCAED
? 中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
2、中 序线索二叉树
? 在线索树上进行遍历，只要先找到序列中的第一个结
点，然后依次找结点后继直至其后继为空时为止。
62北京邮电大学自动化学院
A
B
C
D
E
A
B D
C E
T
? 后序序列,CBEDA
? 后序线索二叉树
0 0
0 01 1
1 11 1^
3、后 序线索二叉树
63北京邮电大学自动化学院
? 在中序线索二叉树上查找任意结点的中序前驱结点，对于
中序线索二叉树上的任一结点，寻找其中序的前驱结点，
有以下两种情况：
4、线索二叉树的基本操作实现
? （ 1）如果该结点的左标志为 1，那么其左指针域所指向的
结点便是它的前驱结点；
? （ 2）如果该结点的左标志为 0，表明该结点有左孩子，根
据中序遍历的定义，它的前驱结点是以该结点的左孩子为
根结点的子树的最右结点，即沿着其左子树的右指针链向
下查找，当某结点的右标志为 1时，它就是所要找的前驱
结点。
64北京邮电大学自动化学院
? 如何在中序线索树中找结点的后继？树中所有叶子
结点的右链是线索，则右链域直接指示了结点的后
继，如结点 b的后继为结点 *（ P133）。树中所有非
终端结点的右域均为指针，则无法得到后继的信
息。
? 根据中序遍历的规律可知，结点的后继应是遍历其右
子树时访问的第 1个结点，即右子树最左下的结点。
例如结点 × 的后继，它的后继结点为 c （ P133 ） ；
4、线索二叉树的基本操作实现
65北京邮电大学自动化学院
? 在后序线索二叉树上查找结点后继？
? （ 1）若结点 x是二叉树的根，则其后继为空；
? 例如：结点 B的后继为 C结点,C结点的后继为结点 D，
结点 D的后继为结点 E。 E结点的后继为结点 F,F结点
的后继为 G。（ P133)
4、线索二叉树的基本操作实现
? （ 2）若结点 x是其双亲的右孩子或其双亲的左孩子且
其双亲没有右子树，则其后继为双亲结点；
? （ 3）若结点 x是其双亲结点的左孩子，且其双亲有右
子树，则其后继为双亲的右子树按后序遍历列出的第 1
个结点。
66北京邮电大学自动化学院
? 在中序线索二叉树上查找值为 x的结点
? 利用在中序线索二叉树上寻找后继结点和前驱结点的算
法，就可以遍历到二叉树的所有结点。比如，先找到按
某序遍历的第一个结点，然后再依次查询其后继；或先
找到按某序遍历的最后一个结点，然后再依次查询其前
驱。这样，既不用栈也不用递归就可以访问到二叉树的
所有结点。
? 在中序线索二叉树上查找值为 x的结点，实质上就是在
线索二叉树上进行遍历，将访问结点的操作具体写为那
结点的值与 x比较的语句。
4、线索二叉树的基本操作实现
67北京邮电大学自动化学院
5、二叉树的线性化
? 由于线索化的实质是将二叉链表中的空指针改为指向前驱
或后继的线索，而前驱或后继的信息只有在遍历时才能得
到，因此线索化的过程即为在遍历过程中修改空指针的过
程。
? 为了记下遍历过程中访问结点的先后关系，附设一个指针
pre始终指向刚刚访问过的结点，若指针 p指向当前访问的
结点，则 pre指向它的前驱。由此得到中序遍历建立中序
线索化链表的算法。
68北京邮电大学自动化学院
A
B
C
D
E
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
头结点：
lt=0,lc指向根结点
rt=1,rc指向遍历序列中最后一个结点
遍历序列中第一个结点的 lc域和最后
一个结点的 rc域都指向头结点
A
B D
C E
T
中序序列,BCAED
中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
69北京邮电大学自动化学院
6.4 树和森林
? 一、树的存储结构
? 1、双亲表示法
? 2、孩子表示法
? 3、孩子兄弟表示法
70北京邮电大学自动化学院
a
b c
d e f
hg i
1、双亲表示法
? 假设以一组连续空间存储树的结点，同时在每个结点中附设一
个指示器指示其双亲结点在链表中的位置。用这种存储方法，
容易找到双亲结点及所有的祖先，但找孩子却比较麻烦，需要
顺序扫描数组。
6
1
2
3
4
5
7
8
9
a
c
d
e
f
g
h
i
b
data
0
1
2
2
3
5
5
5
1
parent
71北京邮电大学自动化学院
? typedef struct PTNode {//结点结构
? ElemType data;
? int parent; // 双亲位置域
? } PTNode;
? #define MAX_TREE_SIZE 100
? typedef struct {//树结构
? PTNode nodes[MAX_TREE_SIZE];
? int r,n; // 根结点的位置和结点个数
? } PTree;
data parent? 结点结构,
72北京邮电大学自动化学院
a
b c
d e f
hg i
2、孩子表示法
? 把每个结点的孩子结点排列起来，看成是一个线性表，且以单
链表作存储结构，则 n个结点有 n个孩子链表（叶子结点的孩
子链表为空表）。而 n个头指针又组成一个线性表，为了便于
查找，采用顺序存储结构。
6
1
2
3
4
5
7
8
9
a
c
d
e
f
g
h
i
b
data fc
2 3
4 5
97 8
6
^
^
^
^
^
^
^
^
^
73北京邮电大学自动化学院
a
b c
d e f
hg i
? 与双亲表示法相反，孩子表示法便于那些涉及孩子的操作的实
现，却不适合双亲操作。
带双亲的孩子链表
6
1
2
3
4
5
7
8
9
a
c
d
e
f
g
h
i
b
data fc
2 3
4 5
97 8
6
^
^
^
^
^
^
^
^
^
0
1
2
2
3
5
5
5
1
parent
? 我们可以把双亲表示法和孩子表示法结合起来，即将双亲表示
和孩子链表结合在一起。下图就是这种存储结构的一个例子。
74北京邮电大学自动化学院
typedef struct node
{ datatype data;
struct node *fch,*nsib;
}JD;
a
b c
d e f
hg i
a
b c
d e f
g h i
^
^
^
^ ^ ^
^ ^ ^ ^
? 实现：用二叉链表作树的存储结构，链表中每个结点的两
个指针域分别指向其第一个孩子结点和下一个兄弟结点,
3、孩子兄弟表示法（二叉树表示法）
75北京邮电大学自动化学院
A
CB E
D
树
A
B
C
D E
二叉树
A ^
^ B
C
^ D ^
^ E ^
A ^
^ B C
^ D ^
^ E ^
A ^
^ B
C
^ D ^ ^ E ^
对应
二、森林与二叉树的转换
76北京邮电大学自动化学院
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B
C
D
E
F
G H
I
树转换成的二叉树其右子树一定为空
1、树转换二叉树
? 加线,在兄弟之间加一连线
? 抹线,对每个结点，除了其左孩子外，去除其与其余孩子之
间的关系，
? 旋转,以树的根结点为轴心，将整树顺时针转 45°
77北京邮电大学自动化学院
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
IA
B C D
E F G H I
2、将 二叉 树转换成树
? 加线,若 p结点是双亲结点的左孩子，则将 p的右孩子，右
孩子的右孩子,…… 沿分支找到的所有右孩子，都与 p的双
亲用线连起来,
? 抹线,抹掉原二叉树中双亲与右孩子之间的连线
? 调整,将结点按层次排列，形成树结构
78北京邮电大学自动化学院
A
B C D
E
F
G
H I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F G
H
I
J
3、森林转换二叉树
? （ 1）将各棵树分别转换成二叉树,
? （ 2）将每棵树的根结点用线相连,
? （ 3）以第一棵树根结点为二叉树的根，再以根结点为
轴心，顺时针旋转，构成二叉树型结构
79北京邮电大学自动化学院
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B C D
E
F
G
H I
J
4、二叉树转换成森林
? 抹线,将二叉树中根结点与其右孩子连线，及沿右分支搜索
到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树,
? 还原,将孤立的二叉树还原成
80北京邮电大学自动化学院
三、树和森林的遍历
? 1、树的遍历
A
CB E
D
树
? 一种是 后根（次序）遍历,即先依次后根遍历每棵子
树，然后访问根结点。
? 例题,先根序列,A B C D E
? 后根序列,B D C E A
? 两种次序遍历树的方法：一种是 先根（次序）遍历
树,即先访问树的根结点，然后依次先根遍历根的每
棵子树；
81北京邮电大学自动化学院
2、森林的遍历
? 先序遍历,ABCDEFGHIJ A
B C D
E
F
G
H I
J
? 中序遍历,BCDAFEHJIG
? 访问森林中第一棵树的根结点；
? 先序遍历第一棵树中根结点的子树森林
? 先序遍历除去第一棵树之后剩余的树构成的森林
? 中序遍历森林中第一棵树的根结点的子树森林
? 访问第一棵树的根结点；
? 中序遍历除去第一棵树之后剩余的树构成的森林
82北京邮电大学自动化学院
6.5 赫夫曼树及其应用
? 一、最优二叉树（哈夫曼树）
? 2、树的路径长度,从树根到每一个结点的路径长度之和。
? 3、结点的带权路径长度,从结点到树根之间的路径长度
与结点上权的乘积。
? 1、路径长度,从树中一个结点到另一个结点之间的分支
构成这两个结点间的路径，路径上的分支数目称为路径长
度。
83北京邮电大学自动化学院
? 4、树的带权路径长度,树中所有叶子结点的带权路径长
度之和，通常
—结点到根的路径长度—
—权值—其中：
记作：
k
k
n
k
kk
l
w
lwwp l ?
?
?
1
? 5、假设有 n个权值 {w1,w2,……w n}，试 构造一棵有 n个叶
子结点的二叉树，每个叶子的权值为 wi,则其中带权路径
长度 WPL最小的二叉树称为最优二叉树或 哈夫曼树
(Huffman)—— 带权路径长度最短的树。
? 一、最优二叉树（哈夫曼树）
84北京邮电大学自动化学院
? 例如 有 4个结点，权值分别为 7,5，
2,4，构造有 4个叶子结点的二叉树
a b c d
7 5 2 4
WPL=7*2+5*2+2*2+4*2=36
d
c
a b
2
4
7 5
WPL=7*3+5*3+2*1+4*2=46
a
b
c d
7
5
2 4
WPL=7*1+5*2+2*3+4*3=35
?
?
? n
k
KK LWW P L
1
85北京邮电大学自动化学院
等级
分数段
比例
ABCDE
0~59 60~69 70~79 80~89 90~100
0.05 0.15 0.40 0.30 0.10
a<60
a<90
a<80
a<70
E
Y
N
D
Y
N
C
Y
N
B
Y
N
A
将百分制转换成五分制的程序
70?a<80
a<60
C
Y
N
B
Y
N
D
Y
N
E
Y
N
A
80?a<90
60?a<70
? 则 80%的数据需要进行
三次或三次以上的比较
才能的出结果。
a b
? 假设以 5,15,40,30
和 10为树构造一棵有五
个叶子结点的哈夫曼
数，则得到 (b)的判定过
程。
86北京邮电大学自动化学院
E A
D
E
C
a<80
a<70
a<60
a<90
E
Y
N
D
Y
NC
Y
N B
Y
N
A
? 它可使大部分的数据经过较少的比
较次数得出结果。但由于每个判定
框有两次比较，将这两次分开，得
到（ c）所示的判定树。
c
? 现假设现有 10000个输入
数据，若按图（ a）所示的
判定过程进行操作，则总
共需要进行 31500次比
较；而若按图（ c）的判定
过程进行操作，则总共仅
需要进行 22000次比较。
将百分制转换成五分制的程序
87北京邮电大学自动化学院
6、如何构造哈夫曼树？
? （ 1）根据给定的 n个权值 {w1,w2,……w n}构造 n棵二叉树的集
合 F={T1,T2,…… T n}，其中每棵二叉树 Ti中只有一个带权
为 wi的根结点，其左右子树均空。
? （ 4） 重复 （ 2）和（ 3）,直到只含一棵树为止，这棵树即
哈夫曼树。
? （ 3） 在森林中删除这两棵树，同时将新得到的二叉树加
入森林中。
? （ 2） 在森林中选取两棵根结点权值最小的树作左右子
树，构造一棵新的二叉树，并且置新二叉树根结点权值为
其左右子树根结点权值之和。
? 构造 Huffman树步骤
88北京邮电大学自动化学院
a
7
b
5
c
2
d
4
a
7
b
5
c
2
d
4
6
a7
b5
c2 d4
6
11
a
7
b
5
c
2
d
4
6
11
18
? 例如，下图展示了赫夫曼树的构造过程。其中，根结点
上标注的数字是所赋的权。
6、如何构造哈夫曼树？
89北京邮电大学自动化学院
? 1、例题
? 例如，假设要传送的电文为,ABACCDA”，电文中只含
有 A,B,C,D四种字符，只需要两个字符的串便可分
辨。假设 A,B,C,D的编码分别为 00,01,10和 11，则
上述七个字符的电文代码为,00010010101100”，总长度
为 14，对方接收时，可按二位一分进行译码。
二、哈夫曼编码
? 在传送电文时，我们总是希望传送时间尽可能短，这就要
求电文代码尽可能短，显然，这种编码方案产生的电文代
码不够短。
90北京邮电大学自动化学院
? 如果对每个字符设计长度不等的编码，且让电文中出现次
数较多的字符采用尽可能短的编码，则传送电文的总长便
可减少。例如设计 A,B,C,D的编码分别为 0,00,1和
01，则上述七个字符的电文可转换成总长为 9的字符串
,000011010”。
? 但是，这样的电文无法翻译。例如传送过去的字符串中前
四个字符的子串,0000”就可有多种译法,AAAA”或
,ABA”，也可以是,BB”。
? 因此，若要设计长短不等的编码，则必须是任一个字符的
编码都不是另一个字符的编码的前缀，这种编码称做前缀
编码。
二、哈夫曼编码
91北京邮电大学自动化学院
C
B
A
D
0 1
1
10
0
? 编码
? 假设有一棵如下图所示的二叉树，其 4个叶子结点分别表
示 A,B,C,D这 4个字符，且约定左分支表示字符,0”，
右分支表示字符,1”，从根结点到叶子结点的路径上分支
字符组成的字符串作为该结点字符的编码。
? A（ 0）
? B（ 10）
? C（ 110）
? D（ 111）
2、利用二叉树来设计二进制的前缀编码
92北京邮电大学自动化学院
3、如何得到使电子总长最短的二进制前缀编码
? 假设每种字符在电文中出现的次数为 wi，其编码长度为
li，电文中只有 n中字符，则电文总长为
?
?
n
i
iilw
1
?
?
n
i
iilw
1
? 对应到二叉树上，若置 wi为叶子结点的权,li恰为根到叶子的
路径长度。则 恰为二叉树上带权路径长度。
? 由此可见，设计电文总长度最短的二进制前缀编码即以 n种字
符出现的频率作权，设计一棵哈夫曼树的问题，由此得到的
二进制前缀编码便称为哈夫曼编码。
? 如何选定结点结构？
93北京邮电大学自动化学院
? 由于在构成哈夫曼树之后，为求编码需从叶子结点出发走一条
从叶子到根的路径；而为译码需从根出发走一条从根到叶子的
路径。则对每个结点而言，既需知双亲的信息，又需要知孩子
结点的信息。
? 编码：把一棵二叉树中每个结点左分支标上,0”，右分支标上
,1”。从叶子结点开始，顺着双亲域 pa反推上去一直到根结
点，并将路径上的,0”或,1”连接而得的序列就是叶子结点所
对应的字符的二进制编码的逆序。
? 译码：由于每个字符对应一个叶子结点，则任何一个字符的编
码不是另一个字符的编码的前缀，因此，只要顺序扫描电文，
就很容易译出相应的电文。
3、如何得到使电子总长最短的二进制前缀编码
94北京邮电大学自动化学院
? 具体译法是：从哈夫曼树的根结点出发，用待译码的二进制
位串中逐位取码，与二叉树分支上标明的,0”，,1”相匹
配，确定一条到达叶子结点的路径。若码是,0”，则向左
走，否则向右走到下一层的结点，一旦到达叶子结点，则译
出一个字符。再重新从根结点出发，从二进制位串中的下一
位开始继续译码直至二进制电文结束。
? 例题 1：已知某系统在通讯联络中只可能出现八种字符，其概率
分布分别为 0.05,0.29,0.07,0.08,0.14,0.23,0.11，试设
计哈夫曼编码。
? 设权 W=（ 5,29,7,8,14,23,3,11）,n=8,m=15，按
上述算法可构造一棵哈夫曼树，其存储结构 HT的初始状态如后
图所示，其终结状态如后图所示，所得哈夫曼编码。
3、如何得到使电子总长最短的二进制前缀编码
95北京邮电大学自动化学院
? 设置一个结构数组保存哈夫曼树中各结点的信息,
? 其中,weight域保存结点的权值,lchild和 rchild域分别保
存该结点的左、右孩子结点在数组中的序号，从而建立起
结点之间的关系。
? 构造哈夫曼树时，首先将由 n个字符形成的 n个叶结点存放
到数组的前 n个分量中，然后根据前面介绍的哈夫曼方法
的基本思想，不断将两个小子树合并为一个较大的子树，
每次构成的新子树的根结点顺序放到 HuffNode数组中的前
n个分量的后面。
3、如何得到使电子总长最短的二进制前缀编码
rchild weight lchild parent
96北京邮电大学自动化学院
例 w={5,29,7,8,14,23,3,11}
5 1429 7 8 23 3 11
1429 7 8 23 11
35
8
87
151429 23
35
811
11
35
8
191429 23
87
15
11
35
8
1929 23
14
87
15
29
29
14
87
15
29
11
35
8
1923
42
11
35
8
1923
42
29
14
87
15
29
58
11
35
8
1923
42
29
14
87
15
29
58
100
97北京邮电大学自动化学院
11
35
8
1923
42
29
14
87
15
29
58
100
5 9 0 0
29 14 0 0
7 10 0 0
8 10 0 0
14 12 0 0
23 12 0 0
3 9 0 0
11 11 0 0
8 11 1 7
15 12 3 4
19 13 8 9
29 14 5 10
42 15 6 11
58 15 2 12
100 0 13 14
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Weight parent lchild rchild
5 0 1 1 0
29 1 0
7 1 1 1 0
8 1 1 1 1
14 1 1 0
23 0 0
3 0 1 1 1
11 0 1 0
98北京邮电大学自动化学院
? 例题 2：要传输的电文是 {CAS； CAT； SAT； AT}
? 要传输的字符集 D={C,A,S,T,; }
? 字符出现频率 w={2,4,2,3,3}
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T, 00;, 01
A, 10
C, 110
S, 111
99北京邮电大学自动化学院
? 译码,从 Huffman树根开始，从待译码电文中逐位取码。若编
码是,0”，则向左走；若编码是,1”，则向右走，一旦到达
叶子结点，则译出一个字符；再重新从根出发，直到电文结束
? 例 电文是 {CAS;CAT;SAT;AT}
? 其编码, 11010111011101000011111000011000”
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T, 00;, 01
A, 10
C, 110
S, 111
? 电文为,1101000”
? 译文只能是,CAT”
100北京邮电大学自动化学院
? 1,掌握树的相关概念、树的表示和树的性质。
? 2,熟悉二叉树的各种存储结构的特点及适用范围。
? 3,遍历二叉树是二叉树各种操作的基础。掌握各种遍历策
略的递归算法，灵活运用遍历算法实现二叉树的其它操
作。
? 4,掌握根据先序遍历和中序遍历构造二叉树。
? 5,熟悉树的各种存储结构及其特点，掌握树和森林与二叉
树的转换方法。掌握 1 至 2 种建立二叉树和树的存储结构
的方法。
? 6,了解最优树的特性，掌握建立最优二叉树和哈夫曼编码
的方法。
第六章 学习要点
101北京邮电大学自动化学院
第六章 作业
? 一、单项选择题
? 1、由于二叉树中每个结点的度最大为 2，所以二叉树是一种
特殊的树，这种说法 B 。
? （ A）正确 （ B）错误
? 2、某二叉树的先序遍历序列和后序遍历序列正好相反，则
该二叉树一定是 B 。
? （ A）空或只有一个结点 （ B） 完全二叉树
? （ C）二叉排序树 （ D） 高度等于其节点数
102北京邮电大学自动化学院
? 3、深度为 5的二叉树至多有 C 个结点。
? （ A） 16 （ B） 32 （ C） 31 （ D） 10
? 4、根据使用频率为 5个字符设计的哈夫曼编码不可能是 D
? （ A） 111,110,10,01,00
? （ B） 000,001,010,011,1
? （ C） 100,11,10,1,0
? （ D） 001,000,01,11,10
第五章 作业
103北京邮电大学自动化学院
? 二、填空题
? 1、树和二叉树的主要差别是, 。
? 2、深度为 k的完全二叉树至少有 个结点，至多有
个结点，若按自上而下，从左到右次序给结点编号
（从 1开始），则编号最小的叶子结点的编号是 。
? 3、一棵二叉树的第 i(i?1)层最多有 个结点；一棵有 n
（ n>0）个结点的满二叉树共有 个叶子结点和 个
非叶子结点。
第五章 作业
104北京邮电大学自动化学院
? 1、已知二叉树的先序、中序和后序序列分别如下，其中有
一些看不清的字母用 *表示，请构造出一棵符合条件的二叉
树并画出该二叉树。
? 先序序列是,*BC**FG
? 中序序列是,CB*EAG*
? 后序序列是,*EDB*FA A
B C D
E F G H I
? 2、将右图所示的树转化为二叉
树，并写出先序遍历，中序遍
历和后序遍历的结果。
? 3、设给定权集 w={2,3,4,7,8,9}，试构造关于 w的一
棵哈夫曼树，并求其加权路径长度 WPL。
105北京邮电大学自动化学院
? 1、编程与上机题，基本要求
? 用二叉链表作为存储结构，建立一棵二叉树。
? 分别按先序、中序、后序和层次顺序遍历二叉树。
? 编写交换二叉树中所有结点的左、右孩子的非递归算
法。
第六章 上机题
第六章 树和二叉树
? 6.1 树的定义和基本概念
? 6.2 二叉树
? 6.3 遍历二叉树
? 6.4 树和森林
? 6.5 赫夫曼树及其应用
2北京邮电大学自动化学院
? 树型结构是一类重要的非线性结构 。树结构在客观世界里是大
量存在的，树在计算机领域中也有着广泛的应用，例如在编译
程序中，用树来表示源程序的语法结构；在数据库系统中，可
用树来组织信息；在分析算法的行为时，可用树来描述其执行
过程等等。
6.1 树的定义和基本术语
? 1、定义 树是 n(n>=0)个结点的有限集 T,T为空时称为空
树，否则它满足如下两个条件：
? （ 1）有且仅有一个特定的称为根的结点；
? （ 2）当 n>1时，其余结点可分为 m(m>0)个互不相交的有限集
T1,T2,T3…Tm,其中每个子集又是一棵树，并称其为根的子
树。
3北京邮电大学自动化学院
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根
子树
1、定义
4北京邮电大学自动化学院
? 结点 —— 表示树中的元素，包括数据项及若干指向其子树的分支
2、基本术语
? 结点的度 (degree)—— 结点拥有的子树数
? 叶子 (leaf)—— 度为 0的结点
? 孩子 (child)—— 结点子树的根称为该结点的孩子
? 双亲 (parents)—— 孩子结点的上层结点叫该结点的 ~
? 兄弟 (sibling)—— 同一双亲的孩子
? 树的度 —— 一棵树中最大的结点度数
? 结点的层次 (level)—— 从根结点算起，根为第一层，它的孩子
为第二层 ……
? 深度 (depth)—— 树中结点的最大层次数
? 森林 (forest)—— m(m?0)棵互不相交的树的集合
5北京邮电大学自动化学院
A
B C D
E F G H I J
K L M
结点 A的度,3
结点 B的度,2
结点 M的度,0
叶子,K,L,F,G,M,I,J
结点 A的孩子,B,C,D
结点 B的孩子,E,F
结点 I的双亲,D
结点 L的双亲,E
结点 B,C,D为兄弟
结点 K,L为兄弟
树的度,3
结点 A的层次,1
结点 M的层次,4
树的深度,4
结点 F,G为堂兄弟
结点 A是结点 F,G的祖先
2、基本术语
6北京邮电大学自动化学院
6.2 二叉树
? 二叉树在树结构的应用中起着非常重要的作用，因为对二叉
树的许多操作算法简单，而任何树都可以与二叉树相互转
换，这样就解决了树的存储结构及其运算中存在的复杂性。
? 定义,二叉树是由 n(n>=0)个结点的有限集合构成，此集合
或者为空集，或者由一个根结点及两棵互不相交的左右子树
组成，并且左右子树都是二叉树。
? 这也是一个递归定义。二叉树可以是空集合，根可以有空的
左子树或空的右子树。二叉树不是树的特殊情况，它们是两
个概念。
7北京邮电大学自动化学院
(a)
空二叉树
A A
B
A
B
A
CB
(b)
根和空的
左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树
? 图 6.3二叉树的 5种形式
? 二叉树结点的子树要区分左子树和右子树，即使只有一棵
子树也要进行区分，说明它是左子树，还是右子树。这是
二叉树与树的最主要的差别。图 6.3列出二差树的 5种基本
形态，图 6.3(C) 和图 6.3（ d）是不同的两棵二叉树。
6.2 二叉树
8北京邮电大学自动化学院
? 6.2.2 二叉树的性质
? 二叉树具有下列重要性质：
? 性质 1,在二叉树的第 i层上至多有 2i-1个结点 (i>=1)。
? 采用归纳法证明此性质。
? 当 i=1时，只有一个根结点,2i-1=20 =1,命题成立。
? 现在假定对所有的 j,1<=j<i，命题成立，即第 j层上至多有
2j-1个结点，那么可以证明 j＝ i时命题也成立。由归纳假设可
知，第 i－ 1层上至多有 2i-2个结点。
? 由于二叉树每个结点的度最大为 2，故在第 i层上最大结点数
为第 i－ 1层上最大结点数的二倍，
? 即 2× 2i-2＝ 2i-1。命题得到证明。
9北京邮电大学自动化学院
? 性质 2：深度为 k的二叉树至多有 2k－ 1个结点（ k>=1).
122
1 1
1 ???? ?
? ?
? kk
i
k
i
ii 层上的最大结点数）（第
? 性质 3,对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2的
结点数为 n2，则 n0＝ n2＋ 1。
? 深度为 k的二叉树的最大的结点数为二叉树中每层上的最大结点
数之和，由性质 1得到每层上的最大结点数，
? 设二叉树中度为 1的结点数为 n1，二叉树中总结点数为 N，因为二
叉树中所有结点均小于或等于 2，所以有：
? N＝ n0＋ n1＋ n2 (6-1)
? 再看二叉树中的分支数，除根结点外，其余结点都有一个进入分
支，设 B为二叉树中的分支总数，
? 则有,N＝ B＋ 1。
10北京邮电大学自动化学院
? 由于这些分支都是由度为 1和 2的结点射出的，所以有：
? B＝ n1+2*n2
? N＝ B＋ 1＝ n1＋ 2× n2＋ 1 （ 6－ 2)
? 由式（ 6－ 1）和（ 6－ 2）得到：
? N＝ n0＋ n1＋ n2 （ 6-1）
? 性质 3,对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2的
结点数为 n2，则 n0＝ n2＋ 1。
? n0+n1+n2=n1+2*n2+1
? n0＝ n2＋ 1
11北京邮电大学自动化学院
图 6.4 满二叉树
2
4 5
3
6 7
1
（ 1）满二叉树
? 一棵深度为 k且由 2k-1个结点的二叉树称为满二叉树。
图 6.4就是一棵满二叉树，对结点进行了顺序编号。
下面介绍两种特殊形态的二叉树,满二叉树和完全二叉树。
12北京邮电大学自动化学院
1
2 3
4 5 6
（ a）完全二叉树
1
2 3
4 5 7
（ b）非完全二叉树
1
2 3
6 7
（ c）非完全二叉树
图 6.5 完全二叉树
（ 2）完全二叉树
? 如果深度为 k、由 n个结点的二叉树中每个结点能够与深度为
k的顺序编号的满二叉树从 1到 n标号的结点相对应，则称这
样的二叉树为 完全二叉树,图 6.5（ b）、（ c）是 2棵非完全
二叉树。满二叉树是完全二叉树的特例。
13北京邮电大学自动化学院
完全二叉树的特点
? （ 1）所有的叶结点都出现在第 k层或 k－ 1层。
? （ 2）对任一结点，若其右分支下的子孙的最大层次为 l，则其
左分支下的子孙的最大层次必为 l或 l＋ 1。
? 性质 4：具有 n个结点的完全二叉树的深度为 ?log2n?＋ 1。
? 符号 ?x?表示不大于 x的最大整数。
? 假设此二叉树的深度为 k，则根据性质 2及完全二叉树的定义得：
?2k-1－ 1<n<=2k-1 或 2k-1<=n<2k
? 取对数得到,k－ 1?log2n<k 因为 k是整数。所以有：
?k＝ ? log2n ?＋ 1
14北京邮电大学自动化学院
? 性质 5,如果对一棵有 n个结点的完全二叉树的结点按层序
编号（从第 1层到第 ?log2n ?+1层，每层从左到右 ),则对任一
结点 i（ 1<=i<=n),有：
? （ 1）如果 i＝ 1，则结点 i无双亲，是二叉树的根；如果 i>1，
则其双亲是结点 ?i/2 ? 。
? （ 2）如果 2i>n，则结点 i为叶子结点，无左孩子；否则，其
左孩子是结点 2i。
? （ 3）如果 2i＋ 1>n，则结点 i无右孩子；否则，其右孩子是
结点 2i＋ 1。
15北京邮电大学自动化学院
? 图 6.6 完全二叉树中结点 i和 i+1
[i/2]
i i+1
2i 2i+1 2(i+1) 2i+3
(a) i和 i+1结点在同一层
i+1
2(i+1) 2i+3
i
2i 2i+1
? (b)i和 i+1结点不在同一层
? 我们只要先证明（ 2）和（ 3），便可以从（ 2）和（ 3）推出（ 1）。
? 对于 i＝ 1，由完全二叉树的定义，其左孩子是结点 2，若 2>n，
即不存在结点 2，此时，结点 i无孩子。结点 i的右孩子也只能是
结点 3，若结点 3不存在，即 3>n，此时结点 i无右孩子。
16北京邮电大学自动化学院
图 6.6 完全二叉树中结点 i和 i+1
[i/2]
i i+1
2i 2i+1 2(i+1) 2i+3
(a) i和 i+1结点在同一层
i+1
2(i+1) 2i+3
i
2i 2i+1
(b)i和 i+1结点不在同一层
? 对于 i>1，可分为两种情况：
? （ 1）设第 j（ 1?j??log2n?)层的第一个结点的编号为 i（由二叉
树的定义和性质 2可知 i＝ 2j-1），则其左孩子必定为 j＋ 1层的
第一个结点，其编号为 2j＝ 2× 2j-1＝ 2i。如果 2i>n，则无左孩
子；
? 其右孩子必定为第 j＋ 1层的第二个结点，编号为 2i＋ 1。若
2i+1>n，则无右孩子。
17北京邮电大学自动化学院
图 6.6 完全二叉树中结点 i和 i+1
[i/2]
i i+1
2i 2i+1 2(i+1) 2i+3
(a) i和 i+1结点在同一层
i+1
2(i+1) 2i+3
i
2i 2i+1
(b)i和 i+1结点不在同一层
? （ 2）假设第 j（ 1?j??log2n?)层上的某个结点编号为 i（ 2 j-1?i<2j-
1)，且 2i＋ 1<n，则其左孩子为 2i，右孩子为 2i＋ 1.
? 又编号为 i＋ 1的结点是编号为 i的结点的右兄弟或堂兄弟。若它有
左孩子，则其编号必定为 2i＋ 2＝ 2× （ i＋ 1）；若它有右孩子，
则其编号必定为 2i＋ 3＝ 2× （ i＋ 1）＋ 1。
18北京邮电大学自动化学院
? 图 6.6 完全二叉树中结点 i和 i+1
[i/2]
i i+1
2i 2i+1 2(i+1) 2i+3
(a) i和 i+1结点在同一层
i+1
2(i+1) 2i+3
i
2i 2i+1
? (b)i和 i+1结点不在同一层
? 当 i＝ 1时，就是根，因此无双亲。
? 当 i>1时，如果 i为左孩子，即 2× （ i/2)=i，则 i/2是 i的双
亲；如果 i为右孩子,i＝ 2p+1,i的双亲应为 p,p＝（ i－
1） /2=?i/2?。 证毕。
19北京邮电大学自动化学院
? 1、顺序存储结构
6.2.3 二叉树的存储结构
? #define MAX-TREE-SIZE 100
? Typedef TelemType SqBiTree[ MAX-TREE-SIZE];
? SqBitree bt;
? 按照顺序存储结构的定义，在此约定，用一组地址连续的
存储单元依次自上而下，自左至右存储完全二叉树上的结
点元素，即将完全二叉树上编号为 i的的结点元素存储在
如上定义的一维数组中下标为 i-1的分量中。
20北京邮电大学自动化学院
a b c d e f g h i j k l
1 2 3 4 5 6 7 8 9 10 11 12
a
b c
d e f g
h i j k l
1、顺序存储结构
完全二叉树
21北京邮电大学自动化学院
a
b c
d e
f g
? 从树根起，自上层至下层，每层自左至右的给所有结点编号,
一般二叉树
? 缺点是有可能对存储空间造成极大的浪费，在最坏的情况
下，一个深度为 h且只有 h个结点的右单支树，却需要 2h-1个
结点存储空间。而且，若经常需要插入与删除树中结点时，
顺序存储方式不是很好！
a b c d e 0 0 0 0 f g
1 2 3 4 5 6 7 8 9 10 11
22北京邮电大学自动化学院
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree; A
B
C D
E F
G
? 在 n个结点的二叉链表中，有 n+1个空指针域
A
B
C D
E F
G
^
^ ^
^ ^ ^
^ ^
? 二叉链表,二叉树的每一个结点最多有左、右两棵子树，故链
表的结点结构除数据域外可设两个链域：左孩子（ lc）、右孩
子（ rc）分别指向左、右孩子。 称结点由两个链域组成的链表
为二叉链表。
2、链式存储结构
lchild data rchild
23北京邮电大学自动化学院
? typedef struct node
? { datatype data;
? struct node *lchild,*rchild,*parent;
? }JD;
A
B
C D
E F
G
A
B
C D
E F
G
^ ^
^ ^
^ ^ ^
^ ^
? 三叉链表,有时为了便于找到双亲结点，另设一个指向双亲的
链域，结点由三个链域组成的链表称为 三叉链表 。
lchild data parent rchild
24北京邮电大学自动化学院
? 线索链表,用链表表示的二叉树中也会存在许多空链域。例如
在含有 n个结点的二叉链表中，共有 2n个链域，实用 n-1链域
（仅有 n-1个分支），还有 n+1个空链域。（可以利用这些空链
域存储其它有用信息，从而得到另一种链式存储结构 —— 线索
链表 。）
6.3 遍历二叉树和线索二叉树
? 6.3.1 遍历二叉树
? 1、定义及递归算法
? 遍历二叉树,是指按一定的次序系统地访问二叉树中所有结
点，而且仅被访问一次。
? 访问,所谓“访问”可以是对结点作各种处理，如输出结点数
据域值。
25北京邮电大学自动化学院
? 二叉树是由三个基本单元组成,根结点、左子树和右子树。
因此，若能依次遍历这三部分，便是遍历了整个二叉树。
? 假如以 L,D,R分别表示遍历左子树、访问根结点和遍历右
子树，则可能有,DLR,LDR,LRD,DRL,RDL,RLD六
种遍历二叉树的方案。
? 若限定先左后右，则只有前三种情况，分别称之为 先（根）
序遍历，中（根）序遍历和后（根）序遍历。
6.3.1 遍历二叉树
26北京邮电大学自动化学院
先序遍历算法
? 若二叉树为空树，则空操作；否则，
? （ 1）访问根结点；
? （ 2）先序遍历左子树；
? （ 3）先序遍历右子树。
? void PreOrder（ BiTree bt） {/*先序遍历二叉树 bt*/
? if (bt==NULL) return; /*递归调用的结束条件 */
? Visite（ bt->data） ; /*访问结点的数据域 */
? PreOrder（ bt->lchild） ; /*先序递归遍历 bt的左子树 */
? PreOrder（ bt->rchild） ;/*先序递归遍历 bt的右子树 */}
27北京邮电大学自动化学院
A
D
B C
D L R
A
D L R
D L R
B
D
C
D L R
先序遍历序列,A B D C
先序遍历,
先序遍历
28北京邮电大学自动化学院
void preorder(JD *bt)
{ if(bt!=NULL)
{ printf("%d\t",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
主程序
Pre( T )
返回
返回
pre(T
R);
返回
返回
pre(T
R);
A
CB
D
T B
printf(B);
pre(T
L);
T A
printf(A);
pre(T
L);
T D
printf(D);
pre(T
L);
T C
printf(C);
pre(T
L);
返回
T
左是空返回
pre(T
R);
T
左是空返回
T
右是空返回
T
左是空返回
T
右是空返回
pre(T
R);
先序序列,A B D C
29北京邮电大学自动化学院
? 若二叉树为空树，则空操作；否则，
中序遍历算法
? （ 1）中序遍历左子树；
? （ 2）访问根结点；
? （ 3）中序遍历右子树。
? void InOrder（ BiTree bt） {/*中序遍历二叉树 bt*/
? if (bt==NULL) return; /*递归调用的结束条件 */
? InOrder（ bt->lchild） ; /*中序递归遍历 bt的左子 */
? Visite（ bt->data） ; /*访问结点的数据域 */
? InOrder（ bt->rchild） ; /*中序递归遍历 bt的右子树 */}
30北京邮电大学自动化学院
A
D
B C
L D R
B
L D R
L D R
A
D
C
L D R
中序遍历序列,B D A C
中序遍历
中序遍历算法
31北京邮电大学自动化学院
后序遍历算法
? 若二叉树为空树，则空操作；否则，
? （ 1）后序遍历左子树；
? （ 2）后序遍历右子树；
? （ 3）访问根结点。
? void PostOrder（ BiTree bt） {/*后序遍历二叉树 bt*/
? if (bt==NULL) return; /*递归调用的结束条件 */
? PostOrder（ bt->lchild） ;/*后序递归遍历 bt的左子树 */
? PostOrder（ bt->rchild） ; /*后序递归遍历 bt的右子树 */
? Visite（ bt->data） ; /*访问结点的数据域 */}
32北京邮电大学自动化学院
A
D
B C
L R D
L R D
L R D
A
D
C
L R D
后序遍历序列,D B C A
后序遍历,
B
后序遍历算法
33北京邮电大学自动化学院
? 所谓二叉树的 层次遍历,是指从二叉树的第一层（根结点）
开始，从上至下逐层遍历，在同一层中，则按从左到右的顺
序对结点逐个访问。
层次遍历
2
4 5
3
6 7
1
34北京邮电大学自动化学院
A
B
C
D
E
F
G
H K
例如,先序序列：
中序序列：
后序序列：
A B C D E F G H K
B D C A E H G K F
D C B H K G F E A
层次序列：
A B E C F D G H K
35北京邮电大学自动化学院
? 例如图（ 1）所示的二叉树表达式
? 按中序遍历,其中序序列为：
? a+b*c-d-e/f
－
＋
*a
/
b -
dc
fe
?(a+b*(c-d)-e/f)
? 若先序遍历 此二叉树，按访问结点的先后次序将结点排
列起来,其先序序列为,-+a*b-cd/ef
? 按后序遍历,其后序序列为：
? abcd-*+ef/ -
? 人喜欢中缀形式 的算术表达式，对于
计算机，使用后缀易于求值 图
（ 1）
36北京邮电大学自动化学院
? （ 1）查询二叉树中某个结点
2、二叉树其它操作的算法
? （ 1）查询二叉树中某个结点
? 在二叉树不空的前提下，和根结点的元素进行比较。若相
等，则找到返回 TRUE;
? 否则在左子树中进行查找，若找到，则返回 TRUE;
? 否则继续在右子树中进行查找,若找到，则返回 TRUE，否
则返回 FALSE。
? （ 2）计算二叉树中叶子结点的个数
? （ 3）求二叉树的深度 (后序遍历 )
? （ 4）按先序遍历序列建立二叉树
37北京邮电大学自动化学院
Status Preorder (BiTree T,ElemType x,BiTree &p) {
// 若二叉树中存在和 x 相同的元素，则 p 指向该结点并返回 OK,
// 否则返回 FALSE
}
if (T) {
if (T->data==x) { p = T; return OK,}
}//if
else return FALSE;
else {
if (Preorder(T->lchild,x,p) return OK;
else return (Preorder(T->rchild,x,p)) ;
}//else
38北京邮电大学自动化学院
? 算法基本思想,先序 (或中序或后序 )遍历二叉树，在遍历过
程中查找叶子结点，并计数。
（ 2）计算二叉树中叶子结点的个数
? 由此，需在遍历算法中增添一个“计数”的参数，并将
算法中“访问结点” 的操作改为,若是叶子，则计数器增
1。
39北京邮电大学自动化学院
void CountLeaf (BiTree T,int& count){
if ( T ) {
if ((!T->lchild)&& (!T->rchild))
count++; // 对叶子结点计数
CountLeaf( T->lchild,count);
CountLeaf( T->rchild,count);
} // if
} // CountLeaf
40北京邮电大学自动化学院
int CountLeaf (BiTree T){
//返回指针 T所指二叉树中所有叶子结点个数
if (!T ) return 0;
if (!T->lchild && !T->rchild) return 1;
else{
m = CountLeaf( T->lchild);
n = CountLeaf( T->rchild);
return (m+n);
} //else
} // CountLeaf
41北京邮电大学自动化学院
int Count (BiTree T){
//返回指针 T所指二叉树中所有结点个数
if (!T ) return 0;
if (!T->lchild && !T->rchild) return 1;
else{
m = Count ( T->lchild);
n = Count ( T->rchild);
return (m+n+1);
} //else
} // CountLeaf
42北京邮电大学自动化学院
? 算法基本思想,首先分析二叉树的深度和它的左、右子树
深度之间的关系
（ 3）求二叉树的深度 (后序遍历 )
? 从二叉树深度的定义可知，二叉树的深度应为其左、右子
树深度的最大值加 1。由此，需先分别求得左、右子树的
深度，算法中“访问结点”的操作为,求得左、右子树深度
的最大值，然后加 1 。
43北京邮电大学自动化学院
? int Depth (BiTree T ){ // 返回二叉树的深度
? if ( !T ) depthval = 0; else {
? depthLeft = Depth( T->lchild );
? return depthval;
? }
（ 3）求二叉树的深度 (后序遍历 )
? depthRight= Depth( T->rchild );
? depthval = 1 + (depthLeft > depthRight?
? depthLeft, depthRight);
? }
44北京邮电大学自动化学院
A
B
C D
E F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^
（ 4）按先序遍历序列建立二叉树
? 建立二叉树的方法很多，这里介绍一个基于先序遍历的构
造方法。算法的输入是二叉树的先序序列，但必须在其中
加入空指针。若用,?”表示空指针，要建立下图中所示的
二叉树，其输入序列为：
? A B C ? ? D E ? G ? ? F ? ? ?
45北京邮电大学自动化学院
? Status CreateBiTree (BiTree &T ){ //按先序次序输入二叉树
中结点的值（一个字符），空格字符表示空树，构造二叉链
表表示的二叉树 T
? scanf (&ch);
? if ( ch==‘ ‘ ) T=NULL; else {
? if(!T=(BiTNode *)malloc(sizeof(BiTNode)))) exit
(OVERFLOW);
? T->data=ch; //生成根结点
? CreateBiTree(T->lchild);//构造左子树
? CreateBiTree(T->rchild);//构造右子树 }
? Return OK; }//CreateBiTree
46北京邮电大学自动化学院
3、遍历二叉树的非递归算法
? （ 1）先序遍历非递归算法
? 当找到没有左孩子的结点时，从栈顶退出某结点的右
孩子，此时该结点的左子树已遍历完
? 再按上述过程遍历该结点的右子树。
? 使用栈实现先序遍历二叉树的基本思想是：
? 从二叉树的根结点开始，沿左支一直走到没有左孩子的结点
为止，在走的过程中访问所遇到的结点，并把非空右孩子进
栈。
47北京邮电大学自动化学院
? void inorder(JD *r)//先序遍历二叉树非递归算法 //
? { int i=0; JD *p,*s[M]; p=r;
3、遍历二叉树的非递归算法
? do { while(p!=NULL)
? { printf("%d\t",p->data);
? s[i++]=p->rc;
? if ( i > 0) p=s[--i];
? }while( i>0 || p!=NULL); }
? if (p->rc!=NULL)
? p=p->lc; }
48北京邮电大学自动化学院
（ 2）中序遍历二叉树的非递归算法
? 使用栈实现中序遍历的二叉树的基本思想与先序遍历类
同，只是在沿左支向前走的过程中将所遇到结点进栈，待
到遍历完左子树时，从栈顶退出结点并访问，然后再遍历
右子树。
49北京邮电大学自动化学院
? 非递归算法
A
B
C D
E F
G
p
i
P->A
(1)
A
B
C D
E F
G
p
i
P->A
P->B
(2)
A
B
C D
E F
G
p i
P->A
P->B
P->C
(3)
p=NUL
L
A
B
C D
E F
G
i
P->A
P->B
访问,C(4)
50北京邮电大学自动化学院
p A
B
C D
E F
G
i
P->A
访问,C B(5)
A
B
C D
E F
G
i
P->A
P->D
访问,C B
p
(6)
A
B
C D
E F
G
i
P->A
P->D
P->E
访问,C B
p
(7)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E
p (8)
51北京邮电大学自动化学院
A
B
C D
E F
G
i
P->A
P->D
P->G
访问,C B E
P=NULL
(9)
A
B
C D
E F
G
i
P->A
访问,C B E G D
p
(11)
A
B
C D
E F
G
i
P->A
P->F
访问,C B E G D
p
(12)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E G
p
(10)
52北京邮电大学自动化学院
A
B
C D
E F
G
i
P->A
访问,C B E G D F
p=NULL
(13)
A
B
C D
E F
G
i
访问,C B E G D F A
p
(14)
A
B
C D
E F
G
i
访问,C B E G D F A
p=NULL
(15)
53北京邮电大学自动化学院
（ 3）后序遍历二叉树的非递归算法
? 使用栈实现后序遍历的二叉树要比先序和中序遍历复杂一
些。每个结点要等到遍历左、右子树之后才得以访问，所
以在去遍历左、右子树之前，结点都需要进栈。
? 因此设两个栈，分别称为结点栈（ S1[M]）和标志栈
（ S2[M]），标志栈中存放进 S1栈结点的标记。标记,0”
表明结点在遍历左子树时进栈，标记,1”表明结点在遍历
右子树时进栈。
? 当它出栈时，需要判断是从遍历左子树后的返回（即遍历
完左子树，需要继续遍历右子树），还是从遍历右子树后
的返回（即遍历完右子树，需要访问这个结点）。
54北京邮电大学自动化学院
? 仅知二叉树的先序序列,abcdefg” 不能唯一确定一棵二叉
树，
? 如果同时已知二叉树的中序序列,cbdaegf”,则会如何？
? 二叉树的先序序列
? 二叉树的中序序列 左子树
左子树 右子树
右子树
根
根
4、由结点先序序列和中序序列构造对应的二叉树
55北京邮电大学自动化学院
? 根据先序遍历的定义，先序序列中的第一个元素一定是二
叉树的根结点。由中序遍历定义可知，中序序列中根结点
恰为左、右子树的中序序列的分界点。于是根结点元素把
中序序列划分两个子序列，左子树的中序序列和右子树的
中序序列。
? 然后根据左子树的中序序列结点个数在先序序列中找到对
应的左子树的先序序列和右子树的先序序列。
? 由此可建立一个根结点，再确定其左、右子树各自的中序
序列和先序序列。
? 然后用同样的方法分别找出其左、右子树的根结点及子树
根结点的左、右子树各自的中序序列和先序序列，依次类
推，直到所得左、右子树中包含一个结点为止。
4、由结点先序序列和中序序列构造对应的二叉树
56北京邮电大学自动化学院
? 上述过程是一个递归过程，其递归算法的思想是：先根据先序
序列的第一个元素建立根结点；
? 二叉树的先序序列
? 二叉树的中序序列 左子树
左子树 右子树
右子树
根
根
? 然后在中序序列中找到该元素，确定根结点的左、右子树的中
序序列；
? 再在先序序列中确定左、右子树的先序序列；
? 最后由左子树的先序序列与中序序列建立左子树，由右子树的
先序序列与中序序列建立右子树。
57北京邮电大学自动化学院
? 同样的道理，由二叉树的后序序列和中序序列也可唯一地
确定一棵二叉树。
? 因为，依据后序遍历和中序遍历的定义，后序序列的最后
一个结点，就如同先序序列的第一个结点一样，可将中序
序列分成两个子序列，分别为这个结点的左子树的中序序
列和右子树的中序序列，再拿出后序序列的倒数第二个结
点，并继续分割中序序列，如此递归下去，当倒着取取尽
后序序列中的结点时，便可以得到一棵二叉树。
4、由结点先序序列和中序序列构造对应的二叉树
58北京邮电大学自动化学院
a b c d e f g
c b d a e g f
例如, b f
a
b
c d
e
f
g
^ ^ ^ ^
^
^ ^
^
先序序列
中序序列
59北京邮电大学自动化学院
? 线索二叉树,以二叉链表作为存储结构时,只能找到结点的左
右孩子的信息,而不能在结点的任一序列的前驱与后继信息,这
种信息只有在遍历的动态过程中才能得到,为了能保存所需的
信息,可增加标志域 ;
lchild Ltag data Rtag rchild
6.3.2 线索二叉树
Ltag=
Rtag=
? 其中, 0 lchild 域指示结点的左孩子
1 lchild 域指示结点的前驱
? 以这种结构构成的二叉链表作为二叉树的存储结构,叫做线
索链表,其中指向结点前驱与后继的指针叫做线索，加上线
索的二叉树称之为线索二叉树。
0 rchild 域指示结点的右孩子
1 rchild 域指示结点的后驱
60北京邮电大学自动化学院
A
B D
C E
T
? 先序序列,ABCDE
? 先序线索二叉树
0 0
0 01 1
1 1 ^1 1
A
B
C
D
E
1、先序线索二叉树
61北京邮电大学自动化学院
A
B
C
D
E
A
B D
C E
T
? 中序序列,BCAED
? 中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
2、中 序线索二叉树
? 在线索树上进行遍历，只要先找到序列中的第一个结
点，然后依次找结点后继直至其后继为空时为止。
62北京邮电大学自动化学院
A
B
C
D
E
A
B D
C E
T
? 后序序列,CBEDA
? 后序线索二叉树
0 0
0 01 1
1 11 1^
3、后 序线索二叉树
63北京邮电大学自动化学院
? 在中序线索二叉树上查找任意结点的中序前驱结点，对于
中序线索二叉树上的任一结点，寻找其中序的前驱结点，
有以下两种情况：
4、线索二叉树的基本操作实现
? （ 1）如果该结点的左标志为 1，那么其左指针域所指向的
结点便是它的前驱结点；
? （ 2）如果该结点的左标志为 0，表明该结点有左孩子，根
据中序遍历的定义，它的前驱结点是以该结点的左孩子为
根结点的子树的最右结点，即沿着其左子树的右指针链向
下查找，当某结点的右标志为 1时，它就是所要找的前驱
结点。
64北京邮电大学自动化学院
? 如何在中序线索树中找结点的后继？树中所有叶子
结点的右链是线索，则右链域直接指示了结点的后
继，如结点 b的后继为结点 *（ P133）。树中所有非
终端结点的右域均为指针，则无法得到后继的信
息。
? 根据中序遍历的规律可知，结点的后继应是遍历其右
子树时访问的第 1个结点，即右子树最左下的结点。
例如结点 × 的后继，它的后继结点为 c （ P133 ） ；
4、线索二叉树的基本操作实现
65北京邮电大学自动化学院
? 在后序线索二叉树上查找结点后继？
? （ 1）若结点 x是二叉树的根，则其后继为空；
? 例如：结点 B的后继为 C结点,C结点的后继为结点 D，
结点 D的后继为结点 E。 E结点的后继为结点 F,F结点
的后继为 G。（ P133)
4、线索二叉树的基本操作实现
? （ 2）若结点 x是其双亲的右孩子或其双亲的左孩子且
其双亲没有右子树，则其后继为双亲结点；
? （ 3）若结点 x是其双亲结点的左孩子，且其双亲有右
子树，则其后继为双亲的右子树按后序遍历列出的第 1
个结点。
66北京邮电大学自动化学院
? 在中序线索二叉树上查找值为 x的结点
? 利用在中序线索二叉树上寻找后继结点和前驱结点的算
法，就可以遍历到二叉树的所有结点。比如，先找到按
某序遍历的第一个结点，然后再依次查询其后继；或先
找到按某序遍历的最后一个结点，然后再依次查询其前
驱。这样，既不用栈也不用递归就可以访问到二叉树的
所有结点。
? 在中序线索二叉树上查找值为 x的结点，实质上就是在
线索二叉树上进行遍历，将访问结点的操作具体写为那
结点的值与 x比较的语句。
4、线索二叉树的基本操作实现
67北京邮电大学自动化学院
5、二叉树的线性化
? 由于线索化的实质是将二叉链表中的空指针改为指向前驱
或后继的线索，而前驱或后继的信息只有在遍历时才能得
到，因此线索化的过程即为在遍历过程中修改空指针的过
程。
? 为了记下遍历过程中访问结点的先后关系，附设一个指针
pre始终指向刚刚访问过的结点，若指针 p指向当前访问的
结点，则 pre指向它的前驱。由此得到中序遍历建立中序
线索化链表的算法。
68北京邮电大学自动化学院
A
B
C
D
E
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
头结点：
lt=0,lc指向根结点
rt=1,rc指向遍历序列中最后一个结点
遍历序列中第一个结点的 lc域和最后
一个结点的 rc域都指向头结点
A
B D
C E
T
中序序列,BCAED
中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
69北京邮电大学自动化学院
6.4 树和森林
? 一、树的存储结构
? 1、双亲表示法
? 2、孩子表示法
? 3、孩子兄弟表示法
70北京邮电大学自动化学院
a
b c
d e f
hg i
1、双亲表示法
? 假设以一组连续空间存储树的结点，同时在每个结点中附设一
个指示器指示其双亲结点在链表中的位置。用这种存储方法，
容易找到双亲结点及所有的祖先，但找孩子却比较麻烦，需要
顺序扫描数组。
6
1
2
3
4
5
7
8
9
a
c
d
e
f
g
h
i
b
data
0
1
2
2
3
5
5
5
1
parent
71北京邮电大学自动化学院
? typedef struct PTNode {//结点结构
? ElemType data;
? int parent; // 双亲位置域
? } PTNode;
? #define MAX_TREE_SIZE 100
? typedef struct {//树结构
? PTNode nodes[MAX_TREE_SIZE];
? int r,n; // 根结点的位置和结点个数
? } PTree;
data parent? 结点结构,
72北京邮电大学自动化学院
a
b c
d e f
hg i
2、孩子表示法
? 把每个结点的孩子结点排列起来，看成是一个线性表，且以单
链表作存储结构，则 n个结点有 n个孩子链表（叶子结点的孩
子链表为空表）。而 n个头指针又组成一个线性表，为了便于
查找，采用顺序存储结构。
6
1
2
3
4
5
7
8
9
a
c
d
e
f
g
h
i
b
data fc
2 3
4 5
97 8
6
^
^
^
^
^
^
^
^
^
73北京邮电大学自动化学院
a
b c
d e f
hg i
? 与双亲表示法相反，孩子表示法便于那些涉及孩子的操作的实
现，却不适合双亲操作。
带双亲的孩子链表
6
1
2
3
4
5
7
8
9
a
c
d
e
f
g
h
i
b
data fc
2 3
4 5
97 8
6
^
^
^
^
^
^
^
^
^
0
1
2
2
3
5
5
5
1
parent
? 我们可以把双亲表示法和孩子表示法结合起来，即将双亲表示
和孩子链表结合在一起。下图就是这种存储结构的一个例子。
74北京邮电大学自动化学院
typedef struct node
{ datatype data;
struct node *fch,*nsib;
}JD;
a
b c
d e f
hg i
a
b c
d e f
g h i
^
^
^
^ ^ ^
^ ^ ^ ^
? 实现：用二叉链表作树的存储结构，链表中每个结点的两
个指针域分别指向其第一个孩子结点和下一个兄弟结点,
3、孩子兄弟表示法（二叉树表示法）
75北京邮电大学自动化学院
A
CB E
D
树
A
B
C
D E
二叉树
A ^
^ B
C
^ D ^
^ E ^
A ^
^ B C
^ D ^
^ E ^
A ^
^ B
C
^ D ^ ^ E ^
对应
二、森林与二叉树的转换
76北京邮电大学自动化学院
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B
C
D
E
F
G H
I
树转换成的二叉树其右子树一定为空
1、树转换二叉树
? 加线,在兄弟之间加一连线
? 抹线,对每个结点，除了其左孩子外，去除其与其余孩子之
间的关系，
? 旋转,以树的根结点为轴心，将整树顺时针转 45°
77北京邮电大学自动化学院
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
IA
B C D
E F G H I
2、将 二叉 树转换成树
? 加线,若 p结点是双亲结点的左孩子，则将 p的右孩子，右
孩子的右孩子,…… 沿分支找到的所有右孩子，都与 p的双
亲用线连起来,
? 抹线,抹掉原二叉树中双亲与右孩子之间的连线
? 调整,将结点按层次排列，形成树结构
78北京邮电大学自动化学院
A
B C D
E
F
G
H I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F G
H
I
J
3、森林转换二叉树
? （ 1）将各棵树分别转换成二叉树,
? （ 2）将每棵树的根结点用线相连,
? （ 3）以第一棵树根结点为二叉树的根，再以根结点为
轴心，顺时针旋转，构成二叉树型结构
79北京邮电大学自动化学院
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B C D
E
F
G
H I
J
4、二叉树转换成森林
? 抹线,将二叉树中根结点与其右孩子连线，及沿右分支搜索
到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树,
? 还原,将孤立的二叉树还原成
80北京邮电大学自动化学院
三、树和森林的遍历
? 1、树的遍历
A
CB E
D
树
? 一种是 后根（次序）遍历,即先依次后根遍历每棵子
树，然后访问根结点。
? 例题,先根序列,A B C D E
? 后根序列,B D C E A
? 两种次序遍历树的方法：一种是 先根（次序）遍历
树,即先访问树的根结点，然后依次先根遍历根的每
棵子树；
81北京邮电大学自动化学院
2、森林的遍历
? 先序遍历,ABCDEFGHIJ A
B C D
E
F
G
H I
J
? 中序遍历,BCDAFEHJIG
? 访问森林中第一棵树的根结点；
? 先序遍历第一棵树中根结点的子树森林
? 先序遍历除去第一棵树之后剩余的树构成的森林
? 中序遍历森林中第一棵树的根结点的子树森林
? 访问第一棵树的根结点；
? 中序遍历除去第一棵树之后剩余的树构成的森林
82北京邮电大学自动化学院
6.5 赫夫曼树及其应用
? 一、最优二叉树（哈夫曼树）
? 2、树的路径长度,从树根到每一个结点的路径长度之和。
? 3、结点的带权路径长度,从结点到树根之间的路径长度
与结点上权的乘积。
? 1、路径长度,从树中一个结点到另一个结点之间的分支
构成这两个结点间的路径，路径上的分支数目称为路径长
度。
83北京邮电大学自动化学院
? 4、树的带权路径长度,树中所有叶子结点的带权路径长
度之和，通常
—结点到根的路径长度—
—权值—其中：
记作：
k
k
n
k
kk
l
w
lwwp l ?
?
?
1
? 5、假设有 n个权值 {w1,w2,……w n}，试 构造一棵有 n个叶
子结点的二叉树，每个叶子的权值为 wi,则其中带权路径
长度 WPL最小的二叉树称为最优二叉树或 哈夫曼树
(Huffman)—— 带权路径长度最短的树。
? 一、最优二叉树（哈夫曼树）
84北京邮电大学自动化学院
? 例如 有 4个结点，权值分别为 7,5，
2,4，构造有 4个叶子结点的二叉树
a b c d
7 5 2 4
WPL=7*2+5*2+2*2+4*2=36
d
c
a b
2
4
7 5
WPL=7*3+5*3+2*1+4*2=46
a
b
c d
7
5
2 4
WPL=7*1+5*2+2*3+4*3=35
?
?
? n
k
KK LWW P L
1
85北京邮电大学自动化学院
等级
分数段
比例
ABCDE
0~59 60~69 70~79 80~89 90~100
0.05 0.15 0.40 0.30 0.10
a<60
a<90
a<80
a<70
E
Y
N
D
Y
N
C
Y
N
B
Y
N
A
将百分制转换成五分制的程序
70?a<80
a<60
C
Y
N
B
Y
N
D
Y
N
E
Y
N
A
80?a<90
60?a<70
? 则 80%的数据需要进行
三次或三次以上的比较
才能的出结果。
a b
? 假设以 5,15,40,30
和 10为树构造一棵有五
个叶子结点的哈夫曼
数，则得到 (b)的判定过
程。
86北京邮电大学自动化学院
E A
D
E
C
a<80
a<70
a<60
a<90
E
Y
N
D
Y
NC
Y
N B
Y
N
A
? 它可使大部分的数据经过较少的比
较次数得出结果。但由于每个判定
框有两次比较，将这两次分开，得
到（ c）所示的判定树。
c
? 现假设现有 10000个输入
数据，若按图（ a）所示的
判定过程进行操作，则总
共需要进行 31500次比
较；而若按图（ c）的判定
过程进行操作，则总共仅
需要进行 22000次比较。
将百分制转换成五分制的程序
87北京邮电大学自动化学院
6、如何构造哈夫曼树？
? （ 1）根据给定的 n个权值 {w1,w2,……w n}构造 n棵二叉树的集
合 F={T1,T2,…… T n}，其中每棵二叉树 Ti中只有一个带权
为 wi的根结点，其左右子树均空。
? （ 4） 重复 （ 2）和（ 3）,直到只含一棵树为止，这棵树即
哈夫曼树。
? （ 3） 在森林中删除这两棵树，同时将新得到的二叉树加
入森林中。
? （ 2） 在森林中选取两棵根结点权值最小的树作左右子
树，构造一棵新的二叉树，并且置新二叉树根结点权值为
其左右子树根结点权值之和。
? 构造 Huffman树步骤
88北京邮电大学自动化学院
a
7
b
5
c
2
d
4
a
7
b
5
c
2
d
4
6
a7
b5
c2 d4
6
11
a
7
b
5
c
2
d
4
6
11
18
? 例如，下图展示了赫夫曼树的构造过程。其中，根结点
上标注的数字是所赋的权。
6、如何构造哈夫曼树？
89北京邮电大学自动化学院
? 1、例题
? 例如，假设要传送的电文为,ABACCDA”，电文中只含
有 A,B,C,D四种字符，只需要两个字符的串便可分
辨。假设 A,B,C,D的编码分别为 00,01,10和 11，则
上述七个字符的电文代码为,00010010101100”，总长度
为 14，对方接收时，可按二位一分进行译码。
二、哈夫曼编码
? 在传送电文时，我们总是希望传送时间尽可能短，这就要
求电文代码尽可能短，显然，这种编码方案产生的电文代
码不够短。
90北京邮电大学自动化学院
? 如果对每个字符设计长度不等的编码，且让电文中出现次
数较多的字符采用尽可能短的编码，则传送电文的总长便
可减少。例如设计 A,B,C,D的编码分别为 0,00,1和
01，则上述七个字符的电文可转换成总长为 9的字符串
,000011010”。
? 但是，这样的电文无法翻译。例如传送过去的字符串中前
四个字符的子串,0000”就可有多种译法,AAAA”或
,ABA”，也可以是,BB”。
? 因此，若要设计长短不等的编码，则必须是任一个字符的
编码都不是另一个字符的编码的前缀，这种编码称做前缀
编码。
二、哈夫曼编码
91北京邮电大学自动化学院
C
B
A
D
0 1
1
10
0
? 编码
? 假设有一棵如下图所示的二叉树，其 4个叶子结点分别表
示 A,B,C,D这 4个字符，且约定左分支表示字符,0”，
右分支表示字符,1”，从根结点到叶子结点的路径上分支
字符组成的字符串作为该结点字符的编码。
? A（ 0）
? B（ 10）
? C（ 110）
? D（ 111）
2、利用二叉树来设计二进制的前缀编码
92北京邮电大学自动化学院
3、如何得到使电子总长最短的二进制前缀编码
? 假设每种字符在电文中出现的次数为 wi，其编码长度为
li，电文中只有 n中字符，则电文总长为
?
?
n
i
iilw
1
?
?
n
i
iilw
1
? 对应到二叉树上，若置 wi为叶子结点的权,li恰为根到叶子的
路径长度。则 恰为二叉树上带权路径长度。
? 由此可见，设计电文总长度最短的二进制前缀编码即以 n种字
符出现的频率作权，设计一棵哈夫曼树的问题，由此得到的
二进制前缀编码便称为哈夫曼编码。
? 如何选定结点结构？
93北京邮电大学自动化学院
? 由于在构成哈夫曼树之后，为求编码需从叶子结点出发走一条
从叶子到根的路径；而为译码需从根出发走一条从根到叶子的
路径。则对每个结点而言，既需知双亲的信息，又需要知孩子
结点的信息。
? 编码：把一棵二叉树中每个结点左分支标上,0”，右分支标上
,1”。从叶子结点开始，顺着双亲域 pa反推上去一直到根结
点，并将路径上的,0”或,1”连接而得的序列就是叶子结点所
对应的字符的二进制编码的逆序。
? 译码：由于每个字符对应一个叶子结点，则任何一个字符的编
码不是另一个字符的编码的前缀，因此，只要顺序扫描电文，
就很容易译出相应的电文。
3、如何得到使电子总长最短的二进制前缀编码
94北京邮电大学自动化学院
? 具体译法是：从哈夫曼树的根结点出发，用待译码的二进制
位串中逐位取码，与二叉树分支上标明的,0”，,1”相匹
配，确定一条到达叶子结点的路径。若码是,0”，则向左
走，否则向右走到下一层的结点，一旦到达叶子结点，则译
出一个字符。再重新从根结点出发，从二进制位串中的下一
位开始继续译码直至二进制电文结束。
? 例题 1：已知某系统在通讯联络中只可能出现八种字符，其概率
分布分别为 0.05,0.29,0.07,0.08,0.14,0.23,0.11，试设
计哈夫曼编码。
? 设权 W=（ 5,29,7,8,14,23,3,11）,n=8,m=15，按
上述算法可构造一棵哈夫曼树，其存储结构 HT的初始状态如后
图所示，其终结状态如后图所示，所得哈夫曼编码。
3、如何得到使电子总长最短的二进制前缀编码
95北京邮电大学自动化学院
? 设置一个结构数组保存哈夫曼树中各结点的信息,
? 其中,weight域保存结点的权值,lchild和 rchild域分别保
存该结点的左、右孩子结点在数组中的序号，从而建立起
结点之间的关系。
? 构造哈夫曼树时，首先将由 n个字符形成的 n个叶结点存放
到数组的前 n个分量中，然后根据前面介绍的哈夫曼方法
的基本思想，不断将两个小子树合并为一个较大的子树，
每次构成的新子树的根结点顺序放到 HuffNode数组中的前
n个分量的后面。
3、如何得到使电子总长最短的二进制前缀编码
rchild weight lchild parent
96北京邮电大学自动化学院
例 w={5,29,7,8,14,23,3,11}
5 1429 7 8 23 3 11
1429 7 8 23 11
35
8
87
151429 23
35
811
11
35
8
191429 23
87
15
11
35
8
1929 23
14
87
15
29
29
14
87
15
29
11
35
8
1923
42
11
35
8
1923
42
29
14
87
15
29
58
11
35
8
1923
42
29
14
87
15
29
58
100
97北京邮电大学自动化学院
11
35
8
1923
42
29
14
87
15
29
58
100
5 9 0 0
29 14 0 0
7 10 0 0
8 10 0 0
14 12 0 0
23 12 0 0
3 9 0 0
11 11 0 0
8 11 1 7
15 12 3 4
19 13 8 9
29 14 5 10
42 15 6 11
58 15 2 12
100 0 13 14
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Weight parent lchild rchild
5 0 1 1 0
29 1 0
7 1 1 1 0
8 1 1 1 1
14 1 1 0
23 0 0
3 0 1 1 1
11 0 1 0
98北京邮电大学自动化学院
? 例题 2：要传输的电文是 {CAS； CAT； SAT； AT}
? 要传输的字符集 D={C,A,S,T,; }
? 字符出现频率 w={2,4,2,3,3}
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T, 00;, 01
A, 10
C, 110
S, 111
99北京邮电大学自动化学院
? 译码,从 Huffman树根开始，从待译码电文中逐位取码。若编
码是,0”，则向左走；若编码是,1”，则向右走，一旦到达
叶子结点，则译出一个字符；再重新从根出发，直到电文结束
? 例 电文是 {CAS;CAT;SAT;AT}
? 其编码, 11010111011101000011111000011000”
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T, 00;, 01
A, 10
C, 110
S, 111
? 电文为,1101000”
? 译文只能是,CAT”
100北京邮电大学自动化学院
? 1,掌握树的相关概念、树的表示和树的性质。
? 2,熟悉二叉树的各种存储结构的特点及适用范围。
? 3,遍历二叉树是二叉树各种操作的基础。掌握各种遍历策
略的递归算法，灵活运用遍历算法实现二叉树的其它操
作。
? 4,掌握根据先序遍历和中序遍历构造二叉树。
? 5,熟悉树的各种存储结构及其特点，掌握树和森林与二叉
树的转换方法。掌握 1 至 2 种建立二叉树和树的存储结构
的方法。
? 6,了解最优树的特性，掌握建立最优二叉树和哈夫曼编码
的方法。
第六章 学习要点
101北京邮电大学自动化学院
第六章 作业
? 一、单项选择题
? 1、由于二叉树中每个结点的度最大为 2，所以二叉树是一种
特殊的树，这种说法 B 。
? （ A）正确 （ B）错误
? 2、某二叉树的先序遍历序列和后序遍历序列正好相反，则
该二叉树一定是 B 。
? （ A）空或只有一个结点 （ B） 完全二叉树
? （ C）二叉排序树 （ D） 高度等于其节点数
102北京邮电大学自动化学院
? 3、深度为 5的二叉树至多有 C 个结点。
? （ A） 16 （ B） 32 （ C） 31 （ D） 10
? 4、根据使用频率为 5个字符设计的哈夫曼编码不可能是 D
? （ A） 111,110,10,01,00
? （ B） 000,001,010,011,1
? （ C） 100,11,10,1,0
? （ D） 001,000,01,11,10
第五章 作业
103北京邮电大学自动化学院
? 二、填空题
? 1、树和二叉树的主要差别是, 。
? 2、深度为 k的完全二叉树至少有 个结点，至多有
个结点，若按自上而下，从左到右次序给结点编号
（从 1开始），则编号最小的叶子结点的编号是 。
? 3、一棵二叉树的第 i(i?1)层最多有 个结点；一棵有 n
（ n>0）个结点的满二叉树共有 个叶子结点和 个
非叶子结点。
第五章 作业
104北京邮电大学自动化学院
? 1、已知二叉树的先序、中序和后序序列分别如下，其中有
一些看不清的字母用 *表示，请构造出一棵符合条件的二叉
树并画出该二叉树。
? 先序序列是,*BC**FG
? 中序序列是,CB*EAG*
? 后序序列是,*EDB*FA A
B C D
E F G H I
? 2、将右图所示的树转化为二叉
树，并写出先序遍历，中序遍
历和后序遍历的结果。
? 3、设给定权集 w={2,3,4,7,8,9}，试构造关于 w的一
棵哈夫曼树，并求其加权路径长度 WPL。
105北京邮电大学自动化学院
? 1、编程与上机题，基本要求
? 用二叉链表作为存储结构，建立一棵二叉树。
? 分别按先序、中序、后序和层次顺序遍历二叉树。
? 编写交换二叉树中所有结点的左、右孩子的非递归算
法。
第六章 上机题
