下一页
计算机软件基础
The software basic
of computer
主讲：赵英良
西安交通大学
计算机教学实验中心
第 4单元
非线性数据结构
树、二叉树
下一页
上一页
停止放映
第 2 页
上一单元内容提要
一、栈
栈、栈顶指针
顺序存储、共享栈、链栈、入栈、出栈操作
二、队列
队列、顺序存储、队头指针、队尾指针、约定
循环队列、链式队列（带头结点）、入队、出队
三、串
串、长度、空串（空格串）、子串、主串、
位置、子串位置、串相等、串的操作、
串的存储结构、紧缩存储、非紧缩存储
四、数组：行、列优先顺序存储，矩阵的压缩存储
下一页
上一页
停止放映
第 3 页
一、树型结构及其基本概念
? 树形结构是以分支关系来
定义的层次结构 。 在客观
世界中树形结构广泛存在,
并应用于：
– 人类社会的族谱, 家谱,
行政区域划分管理；
– 各种社会组织机构；
– 在计算机领域中, 用树
表示源程序的语法结构；
– 在 OS中, 文件系统, 目
录等组织结构也是用树
来表示的 。
西安交大
电信学院管理学院 医学院……
信通系 电子系 计算机系 计教中心
……
计 01 计 02 计 12
张三 李四 王五
下一页
上一页
停止放映
第 4 页
1.树的定义 （逻辑结构）
? 树是一种数据结构：
Tree=（ D,R）
其中：
D 是具有相同特性的 n个数据元素的集合；
R 是 D上逻辑关系的集合, 且满足：
– 在 D中存在唯一的称为根的数据元素, 没
有前趋；
– D中其余数据元素都有且只有一个前趋；
– D中所有元素, 或有若干个互不相同的后
继 （ 子树 ）, 或无后继 （ 叶结点 ） ；
则称 Tree为树 。
下一页
上一页
停止放映
第 5 页
树的定义 （递归结构）
? 树是一个或多个结点组成的有限集合
T,有一个特定结点称为 根, 其余结
点分为 m（ m?0） 个互不相交的集合
T1,T2,…,Tm。 每个集合又是一棵
树, 被称为这个根的 子树 。
? 树是一种递归结构, 可以包含一个结
点, 该结点包含不相交的树的指针
（ 即子树 ） 。
下一页
上一页
停止放映
第 6 页
2.树的表示形式
(1) 一般形式
(2) 嵌套形式
(3) 凹入形式
(4) 广义表形式
下一页
上一页
停止放映
第 7 页
树的表示 (一般形式 )
A
B C D
E F
K L
G H I J
M
A
(a) (b)
(a)只有根结点的树 (b)一般的树
下一页
上一页
停止放映
第 8 页
树的表示 (嵌套形式 )
A
C
G
B
F
E
K L M
H D
J I
下一页
上一页
停止放映
第 9 页
树的表示 (凹入形式 )
A
B
E
K
L
C
D
F
G
H
I
J
M
下一页
上一页
停止放映
第 10 页
树的表示 (广义表形式 )
( A ( B ( E (K,L),F),C(G),D( H (M),I,J )))
第一层
第二层
第三层
第四层
下一页
上一页
停止放映
第 11 页
3.基本术语（一）
? 结点 包括一个数据元素及若干个指向其它
子树的分支；例如, A,B,C,D等 。
? 叶结点 无后继结点为叶；如 K,L,M。
? 支结点 度不为 0的结点为支结点；如 B,C，
D等 。
? 根结点 无前趋的结点为根；例如, A结点 。
? 结点度 结点拥有的子树数数目；例如, A
的度为 3。
? 树的度 树中结点的最大度数；上述树的度
为 3。
下一页
上一页
停止放映
第 12 页
基本术语 （二）
? 子结点 某结点子树的根为该结点的子结点；
例如, 结点 A的子结点为 B,C,D。
? 父结点 相对于某结点子树的根, 称该结点为
子树根的父结点；例如子结点 C,B,D的父结
点为 A。
? 兄弟结点 同一父亲的孩子之间互为兄弟结点
（ Sibling） ； H,I,J互为兄弟 。
? 路径 结点的序列 n1,n2,…,nk(K?1)是一条
路径,
? 长度 长度等于路径中结点数 -1.
下一页
上一页
停止放映
第 13 页
基本术语 （三）
? 阶层 （ 层次 ） 结点的特性值, 根结点的阶
层为 1,子结点为 2,依次类推 。 如阶层 1有
结点 A,阶层 2有结点 B,C,D。
? 高度 （ 深度 ） 一棵树的最大 阶层值为树 的高
度或深度 。 例如, 结点 A到 M的高度为 4。
? 森林 0棵或多棵互不相交的树的集合 。 对
树中每个结点而言, 其子树的集合即为森林 。
? 有序 如果将树中结点的各子树看成从左至
右是有顺序的 （ 即不能互换 ）, 则称该树为
有序树 。 否则, 称为无序树 。
下一页
上一页
停止放映
第 14 页
4.树的操作
? PARENT（ n,T） 得到树中 n的父亲结点；
? ROOT（ T） 求树的根, 返回树根的位置 。
? CHILD（ T,x,i） 求树 T中结点 x的第 i个孩子
结点 。
? CREATE（ x,T1,T2,…,Tk) 生成一个结点 x,
下带子树 T1,T2,…,Tk。
? DELETE(x,i) 删除结点 x的第 i个子树 。
? TRAVERSE（ T） 遍历树 T。 按次序依此访问树
中各个结点, 且使每个结点只能被访问一次 。
下一页
上一页
停止放映
第 15 页
5.树的实现 (存储结构 )
? 数组实现方法 （ 双亲表示法 ）
? 链表实现方式 （ 孩子表示法 ）
? 二叉链表实现方式 （ 孩子兄弟表
示法 ）
下一页
上一页
停止放映
第 16 页
树的实现 (存储结构 )
?(1)数组实现方法（双亲表示法）
用数组存储树的结点信息, 在每个结点中附设一个指示器指示其
双亲结点在数组中的位置 。 结构描述：
#define MAXSIZE 100
typedef struct PTNode{
TElemType data；
int parent ；
} PTNode；
typedef struc {
PTNode nodes[MAXSIZE]；
int n；
} Ptree；
结点数据元素包含：数据, 父结点位置
下一页
上一页
停止放映
第 17 页
双亲表示法举例
1
2 3
4 5 6
7 8 9
结点序号
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
0 1 1 2 2 3 5 5 5
方法特点：
找根容易，找子结点难，
要遍历整个数组。
下一页
上一页
停止放映
第 18 页
树的存储结构（二）
? (2)链表实现方式（孩子表示法）
把每个结点的孩子结点排列起来，组成一个线性表，且以单链
表作为存储结构，则 n个结点有 n个孩子链表。
? 结构描述为：
typedef struct CTNode{ typedef struct {
int child； CTBox nodes[MAXSIZE]；
struct CTNode *next,int n,r；
} *Childptr； } Ctree；
typedef struct {
TElemType data；
Childptr firstchild；
} CTBox；
结点元素：数据、指向第一个孩子的指针
孩子结点：孩子、指向下一个孩子的指针
下一页
上一页
停止放映
第 19 页
孩子表示法举例
1
2 3
4 5 6
7 8 9
1
2
3
4
5
6
7
8
9
2 3 ^
4 5 ^
6 ^
^
^
^
^
^
7 8 9 ^
方法特点,
便于实现对孩子的操
作,却不便于对父亲
的操作,
下一页
上一页
停止放映
第 20 页
树的存储结构（三）
?(3)二叉链表实现方式 （ 孩子兄弟表
示法 ）
以二叉链表作为树的存储结构 。 链表中结
点的两个链域分别指向该结点的第一个孩
子结点和下一个兄弟结点 。
结构描述为：
typedef struct CSNode{
ElemType data；
struct CSNode *firstchild,
*netsibling；
} CSNode,* CSTree；
下一页
上一页
停止放映
第 21 页
孩子兄弟表示法举例
1
2 3
4 5 6
7 8 9
1
2
^
3
7
4 5 6
8 9
^
^
^
^^
^ ^^
方法特点,
这种存储结构便于实
现各种树的操作,
^
又称, 左子女右兄弟,
表示法。
下一页
上一页
停止放映
第 22 页
二、二叉树
? 1.定义 二叉树是另一种树形结构：
Binary_Tree =( D,R)
其中, D 是具有相同性质的数据元素的集合 ;
R 是在 D上某个两元关系的集合,且满足,
– D中存在唯一称为根的数据元素,没有前趋 ;
– D中其余元素都有且仅有一个前趋 ;
– 每个结点至多只有两个子树 ;
– D中元素,或有两个互不相交后继,或无后继 ;
– 左, 右子树分别又是一棵二叉树 。
下一页
上一页
停止放映
第 23 页
二叉树定义（二）
? 定义
n个结点的集合 （ n?0）
T 的度 ? 2
T = 所有子树都有左, 右之分
（ 次序不能任意颠到 ）
– 二叉树不一定是树
– 二叉树可以为空；而树则不能为空；
– 二叉树的结点最多只有两个直接后继
– 二叉树的结点的子树分左子树和右子树, 而树
则无此区分 。
– 二叉树是有序树 二叉树的度 <=2
下一页
上一页
停止放映
第 24 页
二叉树的五种基本形态
（ a）
（ b）
（ c）
（ d）
（ e）
O 空结点
O 单个结点
O
O
右子树为空
的二叉树
O
O
左子树为空
的二叉树
O
O O
左、右子树
非空的二叉
树
下一页
上一页
停止放映
第 25 页
二叉树与树的区别
? 表达形式 （ 对 3个结点 ）
普通树
二叉树
（ a） （ b） （ c） （ d） （ e）
O
O O
O
O
O有两种不同形式
（ a） （ b）
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O有五种不同形式
下一页
上一页
停止放映
第 26 页
2、二叉树的性质
? 性质一
二叉树的第 i层上至多有 2i-1 个结点 （ i ? 1） 。
利用归纳法证明：
– i=1时, 只有一个结点, 对的；
– 假设对所有的 j,1? j ? i,命题成立,
即在第 j层上, 至多有 2j-1 个结点 。
– 由归纳假设, 第 i-1层上至多有 2i-2 个结点 。 由于二
叉树的每个结点的度至多为 2,故第 i层上的最大结点
数为第 i-1层上的最大
结点数的 2倍, 即 2X2i-2 = 2i-1。
1
2 3
4 5 6 7
8 9 10 11 12 13
下一页
上一页
停止放映
第 27 页
二叉树的性质（二）
? 性质二
深度为 k的二叉树上最多含有 2k-1个结点
（ k ? 1） 。
由性质一可见, 深度为 k的二叉树的最大结
点数为：
? （ 第 i层上的最大结点数 ）
= ? 2i-1 = 2k - 1
k
i=1
i=1
k
1
2 3
4 5 6 7
8 9 10 11 12 13
下一页
上一页
停止放映
第 28 页
3、二叉树的存储结构
? (1) 顺序存储 （ 一维数组 ）
? 用数组存放
存储描述为：
#define MAXSIZE 100；
typedef TElemType SBTree[MAXSIZE]；
SBTree bt；
? 查找不便 。
a1 a2 a3 a4,.,an
下一页
上一页
停止放映
第 29 页
(2)记录数组结构
? 存储结构描述,
#define MAXSIZE 100;
typedef struct SBNode {
TElemType data ;
int Lchild,Rchild;
} SBNode;
typedef struct｛
SBNode nodes[MAXSIZE];
} SBTree;
下一页
上一页
停止放映
第 30 页
记录数组结构举例
1
2 6
3 4
5
1 2 6
2 3 4
3 0 5
4 0 0
5 0 0
6 0 0
结点 左子 右子
特点,
找子方便,找父
结点不便,
下一页
上一页
停止放映
第 31 页
(3)二叉链表存储结构
data leftp rightp
左指针 数据 右指针
A
B
C D
E F
G
A
B
DC
E F
G
^
^^
^
^ ^
^ ^
特点,
找子易,找父难,
下一页
上一页
停止放映
第 32 页
(4)三叉链表存储结构
parent data rightp
左指针 数据 父结点 右指针
A
B
C D
E F
G
C ^^
^
^
^ ^
特点,
找子、找父都易 。
leftp^^A
B
D
E
G ^
F
下一页
上一页
停止放映
第 33 页
4、特殊二叉树
? (1)满二叉树
? 若 k为二叉树 T的深度, 且 T中共有 2k-1个
结点 （ k ? 1）, 则称 T为满二叉树 。
（ a） 满二叉树 （ b） 非满二叉树
O
O O
O O O O
O
O
O O
O
O
下一页
上一页
停止放映
第 34 页
满二叉树的性质
? 若对满二叉树从第 1层开始,自上而下, 从左至右
给每个结点从 1开始编号的话, 则称深度为 k的满
二叉树的结点编号满足,
– 对某结点 i（ 1? i ? 2k -1 -1）, 其左子树的
编号为 2*i（ 偶数 ）, 其右子树的编号为
2* i +1（ 奇数 ） ； （ 非叶结点 ）
– 若 i>1,则结点 i父结点的编号为 i/2(取整 )。
? 根据这一性质, 可用一维数组存储满二叉数的结
点数据 。 知道一个结点的编号, 经计算就能求出
左, 右子树的根及父结点的编号 。
? I—— 父结点,int(I/2),左子结点,2*I,右子结点,2*I+1
1
2 3
4 5 6 7
8 9 10 11 12 13
下一页
上一页
停止放映
第 35 页
满二叉树存储举例
1
4
32
5 76
1 2 3 4 5 6 7
1 2 3 4 5 6 7
?第 i个结点就存放在第 i个位置上；
?第 i个结点（ i>1)的父结点就存放在第
i/2个位置 ;
?第 i个结点（ i? 2k -1 - 1)的左子结点就存
放在 第 2*i的个位置 ;右子存放在第 2*i+1
位置,
下一页
上一页
停止放映
第 36 页
（ 2）完全二叉树
? 深度为 k的二叉树 T,每层结点数目若满足,
– 第 i层 (1 ? i ? k-1)上的结点个数均为 2i-1;
– 第 k层 从右边连续缺若干个结点 (即只能从右至
左不间断缺少 );
称这样的树为 完全二叉树 。
? （ a） 完全二叉树 （ b） 非完全二叉树
? 特点, 叶结点只可能出现在层次最大的两层上,
O
O O
O O O
O
O
O
O
O
下一页
上一页
停止放映
第 37 页
完全二叉树的性质
? 设完全二叉树的结点 总数为 n,深度为 k,某结点编
号为 i（ 1 ?i ? n ）, 则有：
– 若 i>1,则结点 i的双亲结点的编号为 i/2;
– 若 2* i ? n,则结点 i 的左子结点的编号为 2* i,
否则,结点 i为叶结点 ;
– 若 2* i +1? n,则结点 i 的右子结点的编号为
2*i+1,否则,结点 i为叶结点,
? 同理,完全二叉树也可以采用一维树组作为存储结
构,且方法完全同满二叉树,只不过 n ? 2k -1 罢了,
? I—— 父结点,int(I/2)，
? 左子结点,2*I ? n,右子结点,2*I+1 ? n
下一页
上一页
停止放映
第 38 页
（ 3）平衡二叉树
? 二叉树上任一结点的左子树深度减去右子
树深度的差值, 称为该结点的 平衡因子 。
? 任意结点 左, 右子树的深度之差的绝对值
?1, 这样的树称为 平衡二叉树 。
? （ a） 平衡二叉树 （ b） 非平衡二叉树
O
O
O
O
O
O
O
O
O
O O
O
O
O
下一页
上一页
停止放映
第 39 页
（ 4）二叉排序树定义（一）
? 二叉排序树
– 或者是空二叉树；
– 或者是：
? 左子树上所有结点的值均小于根结点的值；
? 右子树上所有结点的值均大于等于根结点
的值；
– 左, 右子树本身又是一棵二叉排序树 。
?？ 最后一句话可否去掉？
? 区别与有序树
下一页
上一页
停止放映
第 40 页
二叉排序树定义（二）
? X是二叉排序树 T中的一个结点；
– 所有的左后裔 小于 X；
– 所有的右后裔 大于等于 X；
– T可以为空树 ；
? T称为二叉排序树 。
（ a） 二叉排序树 （ b） 非二叉排序树
10
5
7 12
14
18
15
15
14 18
5
10
12
13
7
下一页
上一页
停止放映
第 41 页
5、二叉树的 遍 历
? 遍 历 （ Traversing） 是树形结构的一种重要
运算, 即按一定的次序系统地访问结构中的
所有结点, 使每个结点只被访问一次 。
? 遍 历的方法很多, 常用的有：
– 前序法 （ PreOrder）
– 中序法 （ InOrder）
– 后序法 （ PostOrder）
下一页
上一页
停止放映
第 42 页
前序法（ PreOrder）
? 方法描述：
– 从根结点 a开始访问,
– 接着访问左子结点 b，
– 最后访问右子结点 c。
? 即：
根
左子 右子
a
b c
A 访问根结点
B 先序遍历左子树
C 先序遍历右子树
下一页
上一页
停止放映
第 43 页
中序法（ InOrder）
? 方法描述：
– 从左子结点 b开始访问,
– 接着访问根结点 a，
– 最后访问右子结点 c。
? 即：
根
左子 右子
a
b c
A 中序遍历左子树
B 访问根结点
C 中序遍历右子树
下一页
上一页
停止放映
第 44 页
后序法（ PostOrder）
? 方法描述：
– 从左子结点 b开始访问,
– 接着访问右子结点 c，
– 最后访问根结点 a。
? 即：
根
左子 右子
a
b c
A 后序遍历左子树
B 后序遍历右子树
C 访问根结点
下一页
上一页
停止放映
第 45 页
二叉树的遍历举例
o
o o
o o
o
o
o o
A
B C
D E F
G H I
?前序遍历序列：
?中序遍历序列：
?后序遍历序列：
A B D E G C F H I
D B G E A C H F I
D G E B H I F C A
示例
下一页
上一页
停止放映
第 46 页
二叉树遍历算法 （递归算法）
?二叉链表的 C语言描述：
struct tnode {
int data；
struct tnode *lchild,*rchild ；
} ；
typedef struct tnode TNODE;
定义 结点 数据类型
下一页
上一页
停止放映
第 47 页
二叉树遍历算法 （递归、前序法程序）
? void preorder_t (TNODE *root)
{ if ( root != NULL )
{ printf(“%d \n”,root->data);
if (root->lc!=NULL)
preorder_t(root->lc);
if (root->rc!=NULL)
preorder_t(root->rc);
}
}
? 前序遍历二叉树的序列为：
A B C D E F
A
B
C D
E F
下一页
上一页
停止放映
第 48 页
二叉树 遍 历算法 （递归、前序法程序验证）
? 打印 A
– 取 A?.左子 (B)
– 打印 B
? 取 B?.左子 (C)
? 打印 C
– 取 C?.左子 (空 )
– 取 C?.右子 (空 )
? 取 B?.右子 (D)
? 打印 D
– 取 D?.左子 (E)
– 打印 E
? 取 E?.左子 (空 )
? 取 E?.右子 (空 )
– 取 D?.右子 (F)
– 打印 F
? 取 F?.左子 (空 )
? 取 F?.右子 (空 )
– 取 A?.右子 (空 )
? 结束
A
B C
D E
F
A
B
C D
E F
下一页
上一页
停止放映
第 49 页
二叉树 遍 历算法 （ 非递归算法 -前序法）
? 算法步骤,
– step1 初始化,置栈为空 (top=-1),
工作变量 p指向 root;
– step2 p非空 (p!=NULL)
或栈非空 (top!=-1)循环 ;
– step3 p非空循环 ; 访问 p(打印 p->data);
– step4 当前元素进栈,p取 p->lc(进左子树 );
执行 step3；
– step5 p为空, 栈非空, 则出栈,
p取 p->rc（ 进右子树 ）,返回 step2.
下一页
上一页
停止放映
第 50 页
二叉树 遍 历算法 （非递归算法 -前序法程序）
#define N m
void preorder_t(TNODE * root)
{ TNODE *p,*stack[N]; int top=-1;
p=root;
while ((p!= NULL)||(top!= -1))
{ while ( P!=NULL)
{ printf(“%d\n”,p->data);//访问节点
top ++; stack[top]=p; //进栈
p=p->lc; //进左子树
}
if ( top !=-1)
{ p=stack[top]; top - - ; //出栈
p=p->rc;//进右子树
}
}
}
下一页
上一页
停止放映
第 51 页
二叉树 遍 历算法 （非递归、前序法程序验证）
? 打印 A
– A进栈, 取 A?.左子 ( B )
– 打印 B
? B进栈，取 B?.左子 ( C )
? 打印 C
– C 进栈,取 C?.左子 ( 空 )
– C 退栈,取 C?.右子 ( 空 )
? B 退栈,取 B?.右子 ( D )
? 打印 D
– D进栈，取 D?.左子 ( E )
– 打印 E
? E进栈，取 E?.左子 ( 空 )
? E退栈,取 E?.右子 ( 空 )
– D退 栈，取 D?.右子 ( F )
– 打印 F
? F进栈，取 F?.左子 ( 空 )
? F退栈,取 F?.右子 ( 空 )
– A退 栈，取 A?.右子 ( 空 )
? 结束
F
E
D
CB
A
A
B
C D
E F
下一页
上一页
停止放映
第 52 页
6、表达式树及应用
? 在计算机中对表达式进行分析和计算是一项重要的任务 。
? 举例, 用二叉树表示表达式：
a + b * （ c - d ） － ｅ ／ｆ
前序遍历序列：－＋ａ＊ｂ－ｃｄ／ｅｆ
中序遍历序列：ａ＋ｂ＊ｃ－ｄ－ｅ／ｆ
后序遍历序列：ａｂｃｄ－＊＋ｅｆ／－
? 分析：
– 每个叶结点为运算对象；
– 每个非叶结点为运算符；
– 每个子树对应一个子表达式 。
? 表达式处理一般采用后序法, 也称, 逆波兰, 法 。
? 表达式处理规则：
– 见运算数入栈；
– 见运算符, 取两个栈顶元素运算后再压栈；
– 直到处理结束 。
－
＋ ／
－ e f＊
b －
c d
a
下一页
上一页
停止放映
第 53 页
后缀表达式的求法
1,设立 操作数栈 ;
2,设表达式的结束符为,#”,予设 运算符栈的 栈
底为,#”
3,若当前字符是操作数，则 直接发送给后缀式 ;
4,若当前运算符的优先数高于栈顶运算符，则
进栈 ;
5,否则，退出栈顶运算符发送给后缀式 ;
6.,(”对它之前后的运算符 起隔离作用,,)”可
视为自相应左括弧开始的表达式的结束符
下一页
上一页
停止放映
第 54 页
表达式树应用举例
（ 1） a b c d 入栈,
（ 2） 遇 ‘ -?,c d 出栈,
运算后再压栈；
（ 3） 遇 ‘ *’, （ c - d） 和 b 出栈,
运算后再压栈；
（ 4） 遇 ‘ +?,b*（ c-d） 和 a出栈,
运算后再压栈；
（ 5） e f 入栈；
（ 6） 遇 ‘ /?,f e 出栈,
运算后再压栈；
（ 7） 遇 ‘ -?,a+b*（ c-d）
和 e/f出栈,
运算后再压栈 。
d
c
b
a
（ 1） （ 2） c - d
b
a
（ 3） b*（ c-d）a
（ 5）
a+b*（ c-d）（ 4）
a+b*（ c-d）
f
e （ 6） e/f
a+b*（ c-d）
（ 7） a+b*（ c-d） - e/f
下一页
上一页
停止放映
第 55 页
三、树、森林与二叉树的转换
? 由于二叉树的存储结构比较简单,
处理起来也比较方便, 所以有时
需要把复杂的树, 转换为简单的
二叉树后再作处理 。
? 树转换成二叉树
? 森林转换成二叉树
下一页
上一页
停止放映
第 56 页
树转换成二叉树
? 操作算法：
– 保留一个结点的最左子结点；
– 抹掉其余兄弟结点与上级结点的连线；
– 将兄弟结点连在一起；
– 以根为轴, 顺时针旋转 45度角度 。
? 举例,o
o
o
o
o o o
o
o o
o o o o
加线 抹线
o
o o
o o o o
旋转
o
o
o
o
o o
o
下一页
上一页
停止放映
第 57 页
森林转换成二叉树
? 操作算法：
– 将森林中每棵树的树根连接起来；
– 将每棵树转换成对应的二叉树；
– 以森林中第一棵树的根为轴顺时针旋转 45度角度 。
? 举例 o
o o
o
o o
o o o
o
连线
o
o o
o
o o
o o o
o
抹线o o o
o o
o
o o o
o旋转
oo
o
oo oo
o
oo
下一页
上一页
停止放映
第 58 页
将二叉树还原成树
? 将二叉树还原成树的操作步骤为：
step1 若某结点是其双亲的左子，则
把该结点的右子、右子的右子,…,都
与该结点的双亲结点用线连起来；
step2 删除原二叉树中所有的双亲结
点与右子结点的连线；
step3 整理 1,2两步所得到的树或森
林，使之结构层次分明。
下一页
上一页
停止放映
第 59 页
举例
A
B
E C
F D
G
A
B
E C
F D
G
（ a）二叉树 （ b）加连线
A
B
E C
F D
G
（ c）删除与
右子的连线A
B
E
C
F
D
G （ d）还原后的树
下一页
上一页
停止放映
第 60 页
四、二叉排序树的生成
对给定数列 {a1,a2,…,an},根据二叉排序树特性,逐个将
结点插入到二叉排序中 。
具体操作步骤：
step1 a1是根结点；
step2 若 ai<aj,且 aj的左子为空,则将 ai插入到 aj的左子 ;
若 aj的左子非空,则继续寻找合适的插入位置 。
若 ai?aj,且 aj的右子为空, 则将 ai插入到 aj的右子；
否则继续沿右子树寻找合适的插入位置；
插入 ai 插入到 aj的左子 ai〈 aj
插入到 aj的右子 ai ? aj
step3 重复 step2，直到所有结点插入完为止。
下一页
上一页
停止放映
第 61 页
二叉排序树算法
二叉排序树结点结构：
struct tree {
char info；
struct tree *left, * right ；
}
算法描述,
? 输入结点非空循环,若是第 1个结点,令指针
ROOT指向该结点。
? 打印输出该二叉排序树；
? 输入一个值，在该树中查找，若找到输出该
结点值；否则，显示查找失败。
下一页
上一页
停止放映
第 62 页
二叉排序树生成算法
建立二叉树
Create_btree()
查询结点
Search_btree()
打印二叉树
Print_btree()
主程序
Btree.C
下一页
上一页
停止放映
第 63 页
主程序框图
开始
初始化
输入结点数据
！ ROOT
root=create_btee（） create_btree()
结束?
N
Y
打印该树
查找指定结点
Print_btree()
Search_btree()
下一页
上一页
停止放映
第 64 页
生成二叉排序树程序框图
Create_btree() 开始
r = 0？
Y
申请结点空间
r = 0？显示“溢出”
结束
根结点的处理 N
Y
N
r->left = 0;
r->right = 0;
r->info = info ;
非根结点
info<r->info?Y
t=r->left t=r->right
N
调用本函数
root?
返回
Y N
r->left=0
r->right=0
root->left=r
或
root->right=r
下一页
上一页
停止放映
第 65 页
查询二叉排序树算法框图
开始 Search_btree()
!root
Y
显示“空树”
返回
N
root->info!=key循环
key<root->info?
root=root->left root=root->right
root=0?
NY
查找成功,显示 返回
显示“失败”
root!=0?
循环结束?
N
Y
下一页
上一页
停止放映
第 66 页
打印算法框图
开始 Print_btree()
r=0?
Y
N
调用自身打印左子
打印当前结点值
调用自身打印右子
返回
下一页
上一页
停止放映
第 67 页
主程序 Btree.C
#include,stdio.h”
struct tree {
char info;
struct tree *left,*right;
}
main ( )
{ char *s,*c,key=??;
struct tree *create_btree(),*search_btree(),*root=0;
do {
printf(“Enter a letter:”);
gets(s);
if (!root)
root=create_btree(root,root,*s);
else
create_btrr(root,root,*s);
} while (*s) ;
下一页
上一页
停止放映
第 68 页
主程序 Btree.C(续）
print_btree(root,0);
key=?1?;
while ( key)
{
printf(“Enter a key to find:”);
scanf(“%s”,&c);
key=search_btree(root,c);
printf(“press to continue\n”);
}
} /* Btree.C 结束 */
下一页
上一页
停止放映
第 69 页
生成二叉排序树程序
struct tree create_btree(root,r,info)
struct tree *root,*r;
char info;
{ if (r = =0 )
{ r=malloc(sizeof(struct tree));
if ( r = = 0)
{ printf(“Out of memory\n”); exit(0); }
r->left= 0; r->right=0; r->info=info;
if (root)
{ if(info<root->info) root -> left=r;
else root->right=r;
}
else
{ r->right=0; r->left = 0; }
return r;
} /* if = = 0 接下页 */
下一页
上一页
停止放映
第 70 页
生成二叉排序树程序 （续）
if (info < r->info)
create_btree(r,r->left,info);
if(info>=r->info)
create_btree(r,r->right,info);
} /* create_btree(root,r,info) */
下一页
上一页
停止放映
第 71 页
struct tree *search_btree(root,key)
struct tree *root; char key;
{ if (!root)
{ printf(“Emptu btree\n”); return root; }
while(root->info!=key)
{ if(key<root->info)
root=root->left;
else
root=root->right;
if(root==0)
{ printf(“Search Failure\n”);
break ;
}
} /* while(root->info!=key) */
查询二叉排序树程序
下一页
上一页
停止放映
第 72 页
if (root !=0)
printf(“Successful search\n key=%c\n”,root->info);
return root ;
} /* *search_btree(root,key) */
查询二叉排序树程序（续）
下一页
上一页
停止放映
第 73 页
打印二叉排序树程序
print_btree(r,l)
struct tree *r;
int l;
{ int i;
if (r = = 0) return ;
print_tree(r->left,l+1);
for(i=0;i<l;i++)
printf(“,);
printf(“%c\n”,r->info);
print_btree(r->right,l+1);
}
下一页
上一页
停止放映
第 74 页
程序输入
输入,输出：
h ? b
d ? d
p ? e
r ? h
b ? p
e ? r
?
下一页
上一页
停止放映
第 75 页
举例
对数列 {10,18,3,4,9,13,25},生成二叉排序树 。
10
（ 1）
10
18
（ 2）
10
3 18
（ 3）
10
3 18
4 （ 4）
10
3
4
18
9（ 5）
（ 7）
10
3
9
4
18
13 25
10
3
4
9
18
13
（ 6）
示例
下一页
上一页
停止放映
第 76 页
平衡二叉排序树
在二叉排序树的动态生成过
程中, 由于数据本身的特性, 将
影响二叉排序树的性质, 例如 {3，
5,7,9,20}这样的数列, 生成
的二叉排序树就是一棵单枝树 。
因此, 在动态生成二叉排序树的
过程中, 要进行平衡化处理 。
平衡化处理就是在
不影响 二 叉 排序树特性的前题
下, 通过, 旋转, 处理, 使该结
点
的平衡因子不大于 2。
旋转分,LL,RR,LR和 RL
四种 。
3
5
7
9
20
下一页
上一页
停止放映
第 77 页
LL平衡化处理
由于在 A的左子树的左
子树上插入结点, 使 A
点失去平衡, 需进行
一次 LL旋转 （ 顺时针
旋转 ） 操作 。
程序实现为：
b = a?.lc
a?.lc = b?.rc
b?.rc = a
a?.bf = 0
b?.bf = 0
b为子树的新根
A
B
C
LL B
C A
示例
示意为：
下一页
上一页
停止放映
第 78 页
RR平衡化处理
由于在 A的右子树的右子
树上插入结点, 使 A点
失去平衡, 需进行一次
RR旋转 （ 逆时针旋转 ）
操作 。
程序实现为：
b = a?.rc
a?.rc = b?.lc
b?.lc = a
a?.bf = 0
b?.bf = 0
b为子树新根
A
B
C
RR B
A C
示例
示意为：
下一页
上一页
停止放映
第 79 页
LR平衡化处理
程序实现为：
b = a?.lc,c = b?.rc,a?.lc = c?.rc
b?.rc = c?.lc,c?.lc = b,c?.rc = a
A
B
C
C
B A
A
C
B
示例
由于在 A的左子树的右子树上插入结点, 使 A点失去平
衡, 需进行一次 LR旋转 （ 两次旋转 ;先逆时针,再顺
时针旋转 ） 操作 。
示意为：
下一页
上一页
停止放映
第 80 页
RL平衡化处理
由于在 A的右子树的左子树上插入结点, 使 A点失去平衡,
需进行一次 RL旋转 （ 两次旋转 ;先顺时针,再逆时针旋转 ）
操作 。
A
B
C
C
A B
A
C
B
程序实现为：
b = a?.rc,c = b?.lc,a?.rc = c?.lc
b?.lc = c?.rc,c?.lc = a,c?.rc = b
示意为：
示例
下一页
上一页
停止放映
第 81 页
平衡化处理举例
有数据序列 {13,24,37,90,53}
? 插入 13,树是平衡的 ;
? 插入 24,树仍为平衡 ;
? 插入 37,树不再平衡,
执行 RR旋转 ;
? 插入 90,树仍平衡 ;
? 插入 53,失去平衡,
执行 RL旋转,
13
(1)
13
24
(2)
13
24
37 3713
24
(3)
24
13 37
90
(4)
24
13 37
90
53
24
13 37
53
90
24
13 53
37 90
(5)
示例
下一页
上一页
停止放映
第 82 页
Huffman(哈夫曼）树及应用
? Huffman树的定义
? 构造 Huffman树
? Huffman编码
? Huffman编码的译码
下一页
上一页
停止放映
第 83 页
Huffman树的定义
? Huffman树也称为最优树，是一类带权路径最短
的二叉树。
? 树的带权路径长度定义为：
WPL = ∑ wklk
k = 1
n
其中：
n 是树中叶结点的个数
wi 是第 i个结点的权值
li 是第 i个结点的路径长度
下一页
上一页
停止放映
第 84 页
Huffman树举例
? 以下有三棵树：
（ a） （ b） （ c）
a
b
c d
a b c d
a
c
b
d7
7
7
5
5
52
2
2
4 4
4WPLa =7x2+5x2+2x2+4x2
= 36 WPL
b =7x3+5x3+2x1+4x2
= 46
WPLc =
7x1+5x2+2x3+4x3
= 35 √
? 事实证明按哈夫曼树构造二叉树，可得到很好的特
性，应用于实际问题，可提高处理效率。
下一页
上一页
停止放映
第 85 页
应用举例
? 由统计规律可知，考试成绩的分布符合正态分布：
-1 10
分数 0～ 59 60 ～ 69 70 ～ 79 80 ～ 89 90 ～ 100
比例数 0.05 0.15 0.40 0.3 0.10
? 根据正态分布规律，在 60 ～ 90之间的分数占 85%，
而不及格和优秀是少数。
下一页
上一页
停止放映
第 86 页
将百分制转换成五分制
? 判定树比较,a<60?
a<70?
a<80?
a<90?
不及格
及格
中等
良好 优秀
Y
Y
Y
Y
N N
N
N
a<80?
a<70? a<90?
a<60?
不及格
优秀良好中等及格不及格
Y
Y
Y N
N
N NY
(A)
(B)
? 若输入 1万个数据，按 A的判定过程进行操作，约需比较 3.2
万次，而按 B比较,则仅需 2.2万次。
下一页
上一页
停止放映
第 87 页
构造 Huffman树
? 构造 Huffman树算法步骤：
– 1）将 n个带权值 wi（ i≤n）的结点构成 n棵二叉树
的集合 T={T1,T2,……, Tn}，每棵二叉树只有一
个根结点。
– 2）在 T中选取两个权值最小的结点作为左右子树，
构成一个新的二叉树，其根结点的权值取左右子树
权值之和；
– 3）在 T中删除这两棵树，将新构成的树加入到 T中；
– 4）重复 2）,3）步的操作，直到 T中只含一棵树
为止，该树就是 Huffman树。
下一页
上一页
停止放映
第 88 页
构造 Huffman树举例
? 以权值分别为 7,5,2,4的结点 a,b,c,d构造 Huffman树。
T= { a b c d }
c d
T
32 4
6
b T3
T
2 65
11
b
T
2 65
11
c d2 4
18
a T27
11
T
1
6
18
a7
T
1
b T3
T
25
11
18
a7
T
1
b5
11
c d2
6
4（ d） T={ T1 }
（ c） T= { a T2 }
（ b） T= { a b T3 }
（ a） T= { a b c d }
代入 T2
代
入T
3
示例
下一页
上一页
停止放映
第 89 页
Huffman编码
? 编码：用二进制数的不同组合来表示字符的方法。
? 前缀编码：一种非等长度的编码 (任一个字符的编码
都不是另一个字符编码的前缀 )。
a
0
b
0
1
c d
0
1
1
编码,A（ 0）
B（ 01）
C（ 011）
D（ 111）
方法约定：
1）左分支为‘ 0’
2）右分支为‘ 1’
3）由叶到根路径上字符组
成的二进制串就是该叶结点
的编码。
? Huffman编码：一种非等长度的编码。以给定权
值的结点构造 Huffman树，按二进制前缀编码的
方式构成的编码为 Huffman编码。
下一页
上一页
停止放映
第 90 页
Huffman编码举例
? 在某系统的通信联络中可能出现 8种字符，其频率
分别为 0.05,0.29,0.07,0.08,0.14,0.23、
0.03,0.11，设权值分别为 {5,29,7,8,14，
23,3,11},n=8，其 Huffman树为：
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 91 页
Huffman编码存储结构
? 由于 Huffman树中没有度为 1的结点，则 n个叶结点
的 Huffman树共有 2n-1个结点。例如,4个结点的
Huffman树，共有 7个结点。因此可以用长度为 2n-1
的一维数组存放。
? 求 Huffman编码,从叶到根的编码。因此要知道每
个结点的父结点。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 92 页
Huffman编码的译码
? 从 Huffman编码树上不难看出，代码全部在叶结
点上，根据 Huffman编码，就能求出相应的字符。
该过程称为“译码”。
? 译码是根据从根到叶的 Huffman编码求相应的字
符。因此要知道每个结点的左右子结点。
? 例如，根据,1111”，就能求出对应的字符是,8”。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
下一页
上一页
停止放映
第 93 页
作业、思考题
1、思考题：
第 2章,1,9,12
1、本单元 作业：
5,6,7,11
2、作业要求：
– 作业命名方式为：
学号 _章数 _序号
00101001_ch02_1.doc
计算机软件基础
The software basic
of computer
主讲：赵英良
西安交通大学
计算机教学实验中心
第 4单元
非线性数据结构
树、二叉树
下一页
上一页
停止放映
第 2 页
上一单元内容提要
一、栈
栈、栈顶指针
顺序存储、共享栈、链栈、入栈、出栈操作
二、队列
队列、顺序存储、队头指针、队尾指针、约定
循环队列、链式队列（带头结点）、入队、出队
三、串
串、长度、空串（空格串）、子串、主串、
位置、子串位置、串相等、串的操作、
串的存储结构、紧缩存储、非紧缩存储
四、数组：行、列优先顺序存储，矩阵的压缩存储
下一页
上一页
停止放映
第 3 页
一、树型结构及其基本概念
? 树形结构是以分支关系来
定义的层次结构 。 在客观
世界中树形结构广泛存在,
并应用于：
– 人类社会的族谱, 家谱,
行政区域划分管理；
– 各种社会组织机构；
– 在计算机领域中, 用树
表示源程序的语法结构；
– 在 OS中, 文件系统, 目
录等组织结构也是用树
来表示的 。
西安交大
电信学院管理学院 医学院……
信通系 电子系 计算机系 计教中心
……
计 01 计 02 计 12
张三 李四 王五
下一页
上一页
停止放映
第 4 页
1.树的定义 （逻辑结构）
? 树是一种数据结构：
Tree=（ D,R）
其中：
D 是具有相同特性的 n个数据元素的集合；
R 是 D上逻辑关系的集合, 且满足：
– 在 D中存在唯一的称为根的数据元素, 没
有前趋；
– D中其余数据元素都有且只有一个前趋；
– D中所有元素, 或有若干个互不相同的后
继 （ 子树 ）, 或无后继 （ 叶结点 ） ；
则称 Tree为树 。
下一页
上一页
停止放映
第 5 页
树的定义 （递归结构）
? 树是一个或多个结点组成的有限集合
T,有一个特定结点称为 根, 其余结
点分为 m（ m?0） 个互不相交的集合
T1,T2,…,Tm。 每个集合又是一棵
树, 被称为这个根的 子树 。
? 树是一种递归结构, 可以包含一个结
点, 该结点包含不相交的树的指针
（ 即子树 ） 。
下一页
上一页
停止放映
第 6 页
2.树的表示形式
(1) 一般形式
(2) 嵌套形式
(3) 凹入形式
(4) 广义表形式
下一页
上一页
停止放映
第 7 页
树的表示 (一般形式 )
A
B C D
E F
K L
G H I J
M
A
(a) (b)
(a)只有根结点的树 (b)一般的树
下一页
上一页
停止放映
第 8 页
树的表示 (嵌套形式 )
A
C
G
B
F
E
K L M
H D
J I
下一页
上一页
停止放映
第 9 页
树的表示 (凹入形式 )
A
B
E
K
L
C
D
F
G
H
I
J
M
下一页
上一页
停止放映
第 10 页
树的表示 (广义表形式 )
( A ( B ( E (K,L),F),C(G),D( H (M),I,J )))
第一层
第二层
第三层
第四层
下一页
上一页
停止放映
第 11 页
3.基本术语（一）
? 结点 包括一个数据元素及若干个指向其它
子树的分支；例如, A,B,C,D等 。
? 叶结点 无后继结点为叶；如 K,L,M。
? 支结点 度不为 0的结点为支结点；如 B,C，
D等 。
? 根结点 无前趋的结点为根；例如, A结点 。
? 结点度 结点拥有的子树数数目；例如, A
的度为 3。
? 树的度 树中结点的最大度数；上述树的度
为 3。
下一页
上一页
停止放映
第 12 页
基本术语 （二）
? 子结点 某结点子树的根为该结点的子结点；
例如, 结点 A的子结点为 B,C,D。
? 父结点 相对于某结点子树的根, 称该结点为
子树根的父结点；例如子结点 C,B,D的父结
点为 A。
? 兄弟结点 同一父亲的孩子之间互为兄弟结点
（ Sibling） ； H,I,J互为兄弟 。
? 路径 结点的序列 n1,n2,…,nk(K?1)是一条
路径,
? 长度 长度等于路径中结点数 -1.
下一页
上一页
停止放映
第 13 页
基本术语 （三）
? 阶层 （ 层次 ） 结点的特性值, 根结点的阶
层为 1,子结点为 2,依次类推 。 如阶层 1有
结点 A,阶层 2有结点 B,C,D。
? 高度 （ 深度 ） 一棵树的最大 阶层值为树 的高
度或深度 。 例如, 结点 A到 M的高度为 4。
? 森林 0棵或多棵互不相交的树的集合 。 对
树中每个结点而言, 其子树的集合即为森林 。
? 有序 如果将树中结点的各子树看成从左至
右是有顺序的 （ 即不能互换 ）, 则称该树为
有序树 。 否则, 称为无序树 。
下一页
上一页
停止放映
第 14 页
4.树的操作
? PARENT（ n,T） 得到树中 n的父亲结点；
? ROOT（ T） 求树的根, 返回树根的位置 。
? CHILD（ T,x,i） 求树 T中结点 x的第 i个孩子
结点 。
? CREATE（ x,T1,T2,…,Tk) 生成一个结点 x,
下带子树 T1,T2,…,Tk。
? DELETE(x,i) 删除结点 x的第 i个子树 。
? TRAVERSE（ T） 遍历树 T。 按次序依此访问树
中各个结点, 且使每个结点只能被访问一次 。
下一页
上一页
停止放映
第 15 页
5.树的实现 (存储结构 )
? 数组实现方法 （ 双亲表示法 ）
? 链表实现方式 （ 孩子表示法 ）
? 二叉链表实现方式 （ 孩子兄弟表
示法 ）
下一页
上一页
停止放映
第 16 页
树的实现 (存储结构 )
?(1)数组实现方法（双亲表示法）
用数组存储树的结点信息, 在每个结点中附设一个指示器指示其
双亲结点在数组中的位置 。 结构描述：
#define MAXSIZE 100
typedef struct PTNode{
TElemType data；
int parent ；
} PTNode；
typedef struc {
PTNode nodes[MAXSIZE]；
int n；
} Ptree；
结点数据元素包含：数据, 父结点位置
下一页
上一页
停止放映
第 17 页
双亲表示法举例
1
2 3
4 5 6
7 8 9
结点序号
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
0 1 1 2 2 3 5 5 5
方法特点：
找根容易，找子结点难，
要遍历整个数组。
下一页
上一页
停止放映
第 18 页
树的存储结构（二）
? (2)链表实现方式（孩子表示法）
把每个结点的孩子结点排列起来，组成一个线性表，且以单链
表作为存储结构，则 n个结点有 n个孩子链表。
? 结构描述为：
typedef struct CTNode{ typedef struct {
int child； CTBox nodes[MAXSIZE]；
struct CTNode *next,int n,r；
} *Childptr； } Ctree；
typedef struct {
TElemType data；
Childptr firstchild；
} CTBox；
结点元素：数据、指向第一个孩子的指针
孩子结点：孩子、指向下一个孩子的指针
下一页
上一页
停止放映
第 19 页
孩子表示法举例
1
2 3
4 5 6
7 8 9
1
2
3
4
5
6
7
8
9
2 3 ^
4 5 ^
6 ^
^
^
^
^
^
7 8 9 ^
方法特点,
便于实现对孩子的操
作,却不便于对父亲
的操作,
下一页
上一页
停止放映
第 20 页
树的存储结构（三）
?(3)二叉链表实现方式 （ 孩子兄弟表
示法 ）
以二叉链表作为树的存储结构 。 链表中结
点的两个链域分别指向该结点的第一个孩
子结点和下一个兄弟结点 。
结构描述为：
typedef struct CSNode{
ElemType data；
struct CSNode *firstchild,
*netsibling；
} CSNode,* CSTree；
下一页
上一页
停止放映
第 21 页
孩子兄弟表示法举例
1
2 3
4 5 6
7 8 9
1
2
^
3
7
4 5 6
8 9
^
^
^
^^
^ ^^
方法特点,
这种存储结构便于实
现各种树的操作,
^
又称, 左子女右兄弟,
表示法。
下一页
上一页
停止放映
第 22 页
二、二叉树
? 1.定义 二叉树是另一种树形结构：
Binary_Tree =( D,R)
其中, D 是具有相同性质的数据元素的集合 ;
R 是在 D上某个两元关系的集合,且满足,
– D中存在唯一称为根的数据元素,没有前趋 ;
– D中其余元素都有且仅有一个前趋 ;
– 每个结点至多只有两个子树 ;
– D中元素,或有两个互不相交后继,或无后继 ;
– 左, 右子树分别又是一棵二叉树 。
下一页
上一页
停止放映
第 23 页
二叉树定义（二）
? 定义
n个结点的集合 （ n?0）
T 的度 ? 2
T = 所有子树都有左, 右之分
（ 次序不能任意颠到 ）
– 二叉树不一定是树
– 二叉树可以为空；而树则不能为空；
– 二叉树的结点最多只有两个直接后继
– 二叉树的结点的子树分左子树和右子树, 而树
则无此区分 。
– 二叉树是有序树 二叉树的度 <=2
下一页
上一页
停止放映
第 24 页
二叉树的五种基本形态
（ a）
（ b）
（ c）
（ d）
（ e）
O 空结点
O 单个结点
O
O
右子树为空
的二叉树
O
O
左子树为空
的二叉树
O
O O
左、右子树
非空的二叉
树
下一页
上一页
停止放映
第 25 页
二叉树与树的区别
? 表达形式 （ 对 3个结点 ）
普通树
二叉树
（ a） （ b） （ c） （ d） （ e）
O
O O
O
O
O有两种不同形式
（ a） （ b）
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O有五种不同形式
下一页
上一页
停止放映
第 26 页
2、二叉树的性质
? 性质一
二叉树的第 i层上至多有 2i-1 个结点 （ i ? 1） 。
利用归纳法证明：
– i=1时, 只有一个结点, 对的；
– 假设对所有的 j,1? j ? i,命题成立,
即在第 j层上, 至多有 2j-1 个结点 。
– 由归纳假设, 第 i-1层上至多有 2i-2 个结点 。 由于二
叉树的每个结点的度至多为 2,故第 i层上的最大结点
数为第 i-1层上的最大
结点数的 2倍, 即 2X2i-2 = 2i-1。
1
2 3
4 5 6 7
8 9 10 11 12 13
下一页
上一页
停止放映
第 27 页
二叉树的性质（二）
? 性质二
深度为 k的二叉树上最多含有 2k-1个结点
（ k ? 1） 。
由性质一可见, 深度为 k的二叉树的最大结
点数为：
? （ 第 i层上的最大结点数 ）
= ? 2i-1 = 2k - 1
k
i=1
i=1
k
1
2 3
4 5 6 7
8 9 10 11 12 13
下一页
上一页
停止放映
第 28 页
3、二叉树的存储结构
? (1) 顺序存储 （ 一维数组 ）
? 用数组存放
存储描述为：
#define MAXSIZE 100；
typedef TElemType SBTree[MAXSIZE]；
SBTree bt；
? 查找不便 。
a1 a2 a3 a4,.,an
下一页
上一页
停止放映
第 29 页
(2)记录数组结构
? 存储结构描述,
#define MAXSIZE 100;
typedef struct SBNode {
TElemType data ;
int Lchild,Rchild;
} SBNode;
typedef struct｛
SBNode nodes[MAXSIZE];
} SBTree;
下一页
上一页
停止放映
第 30 页
记录数组结构举例
1
2 6
3 4
5
1 2 6
2 3 4
3 0 5
4 0 0
5 0 0
6 0 0
结点 左子 右子
特点,
找子方便,找父
结点不便,
下一页
上一页
停止放映
第 31 页
(3)二叉链表存储结构
data leftp rightp
左指针 数据 右指针
A
B
C D
E F
G
A
B
DC
E F
G
^
^^
^
^ ^
^ ^
特点,
找子易,找父难,
下一页
上一页
停止放映
第 32 页
(4)三叉链表存储结构
parent data rightp
左指针 数据 父结点 右指针
A
B
C D
E F
G
C ^^
^
^
^ ^
特点,
找子、找父都易 。
leftp^^A
B
D
E
G ^
F
下一页
上一页
停止放映
第 33 页
4、特殊二叉树
? (1)满二叉树
? 若 k为二叉树 T的深度, 且 T中共有 2k-1个
结点 （ k ? 1）, 则称 T为满二叉树 。
（ a） 满二叉树 （ b） 非满二叉树
O
O O
O O O O
O
O
O O
O
O
下一页
上一页
停止放映
第 34 页
满二叉树的性质
? 若对满二叉树从第 1层开始,自上而下, 从左至右
给每个结点从 1开始编号的话, 则称深度为 k的满
二叉树的结点编号满足,
– 对某结点 i（ 1? i ? 2k -1 -1）, 其左子树的
编号为 2*i（ 偶数 ）, 其右子树的编号为
2* i +1（ 奇数 ） ； （ 非叶结点 ）
– 若 i>1,则结点 i父结点的编号为 i/2(取整 )。
? 根据这一性质, 可用一维数组存储满二叉数的结
点数据 。 知道一个结点的编号, 经计算就能求出
左, 右子树的根及父结点的编号 。
? I—— 父结点,int(I/2),左子结点,2*I,右子结点,2*I+1
1
2 3
4 5 6 7
8 9 10 11 12 13
下一页
上一页
停止放映
第 35 页
满二叉树存储举例
1
4
32
5 76
1 2 3 4 5 6 7
1 2 3 4 5 6 7
?第 i个结点就存放在第 i个位置上；
?第 i个结点（ i>1)的父结点就存放在第
i/2个位置 ;
?第 i个结点（ i? 2k -1 - 1)的左子结点就存
放在 第 2*i的个位置 ;右子存放在第 2*i+1
位置,
下一页
上一页
停止放映
第 36 页
（ 2）完全二叉树
? 深度为 k的二叉树 T,每层结点数目若满足,
– 第 i层 (1 ? i ? k-1)上的结点个数均为 2i-1;
– 第 k层 从右边连续缺若干个结点 (即只能从右至
左不间断缺少 );
称这样的树为 完全二叉树 。
? （ a） 完全二叉树 （ b） 非完全二叉树
? 特点, 叶结点只可能出现在层次最大的两层上,
O
O O
O O O
O
O
O
O
O
下一页
上一页
停止放映
第 37 页
完全二叉树的性质
? 设完全二叉树的结点 总数为 n,深度为 k,某结点编
号为 i（ 1 ?i ? n ）, 则有：
– 若 i>1,则结点 i的双亲结点的编号为 i/2;
– 若 2* i ? n,则结点 i 的左子结点的编号为 2* i,
否则,结点 i为叶结点 ;
– 若 2* i +1? n,则结点 i 的右子结点的编号为
2*i+1,否则,结点 i为叶结点,
? 同理,完全二叉树也可以采用一维树组作为存储结
构,且方法完全同满二叉树,只不过 n ? 2k -1 罢了,
? I—— 父结点,int(I/2)，
? 左子结点,2*I ? n,右子结点,2*I+1 ? n
下一页
上一页
停止放映
第 38 页
（ 3）平衡二叉树
? 二叉树上任一结点的左子树深度减去右子
树深度的差值, 称为该结点的 平衡因子 。
? 任意结点 左, 右子树的深度之差的绝对值
?1, 这样的树称为 平衡二叉树 。
? （ a） 平衡二叉树 （ b） 非平衡二叉树
O
O
O
O
O
O
O
O
O
O O
O
O
O
下一页
上一页
停止放映
第 39 页
（ 4）二叉排序树定义（一）
? 二叉排序树
– 或者是空二叉树；
– 或者是：
? 左子树上所有结点的值均小于根结点的值；
? 右子树上所有结点的值均大于等于根结点
的值；
– 左, 右子树本身又是一棵二叉排序树 。
?？ 最后一句话可否去掉？
? 区别与有序树
下一页
上一页
停止放映
第 40 页
二叉排序树定义（二）
? X是二叉排序树 T中的一个结点；
– 所有的左后裔 小于 X；
– 所有的右后裔 大于等于 X；
– T可以为空树 ；
? T称为二叉排序树 。
（ a） 二叉排序树 （ b） 非二叉排序树
10
5
7 12
14
18
15
15
14 18
5
10
12
13
7
下一页
上一页
停止放映
第 41 页
5、二叉树的 遍 历
? 遍 历 （ Traversing） 是树形结构的一种重要
运算, 即按一定的次序系统地访问结构中的
所有结点, 使每个结点只被访问一次 。
? 遍 历的方法很多, 常用的有：
– 前序法 （ PreOrder）
– 中序法 （ InOrder）
– 后序法 （ PostOrder）
下一页
上一页
停止放映
第 42 页
前序法（ PreOrder）
? 方法描述：
– 从根结点 a开始访问,
– 接着访问左子结点 b，
– 最后访问右子结点 c。
? 即：
根
左子 右子
a
b c
A 访问根结点
B 先序遍历左子树
C 先序遍历右子树
下一页
上一页
停止放映
第 43 页
中序法（ InOrder）
? 方法描述：
– 从左子结点 b开始访问,
– 接着访问根结点 a，
– 最后访问右子结点 c。
? 即：
根
左子 右子
a
b c
A 中序遍历左子树
B 访问根结点
C 中序遍历右子树
下一页
上一页
停止放映
第 44 页
后序法（ PostOrder）
? 方法描述：
– 从左子结点 b开始访问,
– 接着访问右子结点 c，
– 最后访问根结点 a。
? 即：
根
左子 右子
a
b c
A 后序遍历左子树
B 后序遍历右子树
C 访问根结点
下一页
上一页
停止放映
第 45 页
二叉树的遍历举例
o
o o
o o
o
o
o o
A
B C
D E F
G H I
?前序遍历序列：
?中序遍历序列：
?后序遍历序列：
A B D E G C F H I
D B G E A C H F I
D G E B H I F C A
示例
下一页
上一页
停止放映
第 46 页
二叉树遍历算法 （递归算法）
?二叉链表的 C语言描述：
struct tnode {
int data；
struct tnode *lchild,*rchild ；
} ；
typedef struct tnode TNODE;
定义 结点 数据类型
下一页
上一页
停止放映
第 47 页
二叉树遍历算法 （递归、前序法程序）
? void preorder_t (TNODE *root)
{ if ( root != NULL )
{ printf(“%d \n”,root->data);
if (root->lc!=NULL)
preorder_t(root->lc);
if (root->rc!=NULL)
preorder_t(root->rc);
}
}
? 前序遍历二叉树的序列为：
A B C D E F
A
B
C D
E F
下一页
上一页
停止放映
第 48 页
二叉树 遍 历算法 （递归、前序法程序验证）
? 打印 A
– 取 A?.左子 (B)
– 打印 B
? 取 B?.左子 (C)
? 打印 C
– 取 C?.左子 (空 )
– 取 C?.右子 (空 )
? 取 B?.右子 (D)
? 打印 D
– 取 D?.左子 (E)
– 打印 E
? 取 E?.左子 (空 )
? 取 E?.右子 (空 )
– 取 D?.右子 (F)
– 打印 F
? 取 F?.左子 (空 )
? 取 F?.右子 (空 )
– 取 A?.右子 (空 )
? 结束
A
B C
D E
F
A
B
C D
E F
下一页
上一页
停止放映
第 49 页
二叉树 遍 历算法 （ 非递归算法 -前序法）
? 算法步骤,
– step1 初始化,置栈为空 (top=-1),
工作变量 p指向 root;
– step2 p非空 (p!=NULL)
或栈非空 (top!=-1)循环 ;
– step3 p非空循环 ; 访问 p(打印 p->data);
– step4 当前元素进栈,p取 p->lc(进左子树 );
执行 step3；
– step5 p为空, 栈非空, 则出栈,
p取 p->rc（ 进右子树 ）,返回 step2.
下一页
上一页
停止放映
第 50 页
二叉树 遍 历算法 （非递归算法 -前序法程序）
#define N m
void preorder_t(TNODE * root)
{ TNODE *p,*stack[N]; int top=-1;
p=root;
while ((p!= NULL)||(top!= -1))
{ while ( P!=NULL)
{ printf(“%d\n”,p->data);//访问节点
top ++; stack[top]=p; //进栈
p=p->lc; //进左子树
}
if ( top !=-1)
{ p=stack[top]; top - - ; //出栈
p=p->rc;//进右子树
}
}
}
下一页
上一页
停止放映
第 51 页
二叉树 遍 历算法 （非递归、前序法程序验证）
? 打印 A
– A进栈, 取 A?.左子 ( B )
– 打印 B
? B进栈，取 B?.左子 ( C )
? 打印 C
– C 进栈,取 C?.左子 ( 空 )
– C 退栈,取 C?.右子 ( 空 )
? B 退栈,取 B?.右子 ( D )
? 打印 D
– D进栈，取 D?.左子 ( E )
– 打印 E
? E进栈，取 E?.左子 ( 空 )
? E退栈,取 E?.右子 ( 空 )
– D退 栈，取 D?.右子 ( F )
– 打印 F
? F进栈，取 F?.左子 ( 空 )
? F退栈,取 F?.右子 ( 空 )
– A退 栈，取 A?.右子 ( 空 )
? 结束
F
E
D
CB
A
A
B
C D
E F
下一页
上一页
停止放映
第 52 页
6、表达式树及应用
? 在计算机中对表达式进行分析和计算是一项重要的任务 。
? 举例, 用二叉树表示表达式：
a + b * （ c - d ） － ｅ ／ｆ
前序遍历序列：－＋ａ＊ｂ－ｃｄ／ｅｆ
中序遍历序列：ａ＋ｂ＊ｃ－ｄ－ｅ／ｆ
后序遍历序列：ａｂｃｄ－＊＋ｅｆ／－
? 分析：
– 每个叶结点为运算对象；
– 每个非叶结点为运算符；
– 每个子树对应一个子表达式 。
? 表达式处理一般采用后序法, 也称, 逆波兰, 法 。
? 表达式处理规则：
– 见运算数入栈；
– 见运算符, 取两个栈顶元素运算后再压栈；
– 直到处理结束 。
－
＋ ／
－ e f＊
b －
c d
a
下一页
上一页
停止放映
第 53 页
后缀表达式的求法
1,设立 操作数栈 ;
2,设表达式的结束符为,#”,予设 运算符栈的 栈
底为,#”
3,若当前字符是操作数，则 直接发送给后缀式 ;
4,若当前运算符的优先数高于栈顶运算符，则
进栈 ;
5,否则，退出栈顶运算符发送给后缀式 ;
6.,(”对它之前后的运算符 起隔离作用,,)”可
视为自相应左括弧开始的表达式的结束符
下一页
上一页
停止放映
第 54 页
表达式树应用举例
（ 1） a b c d 入栈,
（ 2） 遇 ‘ -?,c d 出栈,
运算后再压栈；
（ 3） 遇 ‘ *’, （ c - d） 和 b 出栈,
运算后再压栈；
（ 4） 遇 ‘ +?,b*（ c-d） 和 a出栈,
运算后再压栈；
（ 5） e f 入栈；
（ 6） 遇 ‘ /?,f e 出栈,
运算后再压栈；
（ 7） 遇 ‘ -?,a+b*（ c-d）
和 e/f出栈,
运算后再压栈 。
d
c
b
a
（ 1） （ 2） c - d
b
a
（ 3） b*（ c-d）a
（ 5）
a+b*（ c-d）（ 4）
a+b*（ c-d）
f
e （ 6） e/f
a+b*（ c-d）
（ 7） a+b*（ c-d） - e/f
下一页
上一页
停止放映
第 55 页
三、树、森林与二叉树的转换
? 由于二叉树的存储结构比较简单,
处理起来也比较方便, 所以有时
需要把复杂的树, 转换为简单的
二叉树后再作处理 。
? 树转换成二叉树
? 森林转换成二叉树
下一页
上一页
停止放映
第 56 页
树转换成二叉树
? 操作算法：
– 保留一个结点的最左子结点；
– 抹掉其余兄弟结点与上级结点的连线；
– 将兄弟结点连在一起；
– 以根为轴, 顺时针旋转 45度角度 。
? 举例,o
o
o
o
o o o
o
o o
o o o o
加线 抹线
o
o o
o o o o
旋转
o
o
o
o
o o
o
下一页
上一页
停止放映
第 57 页
森林转换成二叉树
? 操作算法：
– 将森林中每棵树的树根连接起来；
– 将每棵树转换成对应的二叉树；
– 以森林中第一棵树的根为轴顺时针旋转 45度角度 。
? 举例 o
o o
o
o o
o o o
o
连线
o
o o
o
o o
o o o
o
抹线o o o
o o
o
o o o
o旋转
oo
o
oo oo
o
oo
下一页
上一页
停止放映
第 58 页
将二叉树还原成树
? 将二叉树还原成树的操作步骤为：
step1 若某结点是其双亲的左子，则
把该结点的右子、右子的右子,…,都
与该结点的双亲结点用线连起来；
step2 删除原二叉树中所有的双亲结
点与右子结点的连线；
step3 整理 1,2两步所得到的树或森
林，使之结构层次分明。
下一页
上一页
停止放映
第 59 页
举例
A
B
E C
F D
G
A
B
E C
F D
G
（ a）二叉树 （ b）加连线
A
B
E C
F D
G
（ c）删除与
右子的连线A
B
E
C
F
D
G （ d）还原后的树
下一页
上一页
停止放映
第 60 页
四、二叉排序树的生成
对给定数列 {a1,a2,…,an},根据二叉排序树特性,逐个将
结点插入到二叉排序中 。
具体操作步骤：
step1 a1是根结点；
step2 若 ai<aj,且 aj的左子为空,则将 ai插入到 aj的左子 ;
若 aj的左子非空,则继续寻找合适的插入位置 。
若 ai?aj,且 aj的右子为空, 则将 ai插入到 aj的右子；
否则继续沿右子树寻找合适的插入位置；
插入 ai 插入到 aj的左子 ai〈 aj
插入到 aj的右子 ai ? aj
step3 重复 step2，直到所有结点插入完为止。
下一页
上一页
停止放映
第 61 页
二叉排序树算法
二叉排序树结点结构：
struct tree {
char info；
struct tree *left, * right ；
}
算法描述,
? 输入结点非空循环,若是第 1个结点,令指针
ROOT指向该结点。
? 打印输出该二叉排序树；
? 输入一个值，在该树中查找，若找到输出该
结点值；否则，显示查找失败。
下一页
上一页
停止放映
第 62 页
二叉排序树生成算法
建立二叉树
Create_btree()
查询结点
Search_btree()
打印二叉树
Print_btree()
主程序
Btree.C
下一页
上一页
停止放映
第 63 页
主程序框图
开始
初始化
输入结点数据
！ ROOT
root=create_btee（） create_btree()
结束?
N
Y
打印该树
查找指定结点
Print_btree()
Search_btree()
下一页
上一页
停止放映
第 64 页
生成二叉排序树程序框图
Create_btree() 开始
r = 0？
Y
申请结点空间
r = 0？显示“溢出”
结束
根结点的处理 N
Y
N
r->left = 0;
r->right = 0;
r->info = info ;
非根结点
info<r->info?Y
t=r->left t=r->right
N
调用本函数
root?
返回
Y N
r->left=0
r->right=0
root->left=r
或
root->right=r
下一页
上一页
停止放映
第 65 页
查询二叉排序树算法框图
开始 Search_btree()
!root
Y
显示“空树”
返回
N
root->info!=key循环
key<root->info?
root=root->left root=root->right
root=0?
NY
查找成功,显示 返回
显示“失败”
root!=0?
循环结束?
N
Y
下一页
上一页
停止放映
第 66 页
打印算法框图
开始 Print_btree()
r=0?
Y
N
调用自身打印左子
打印当前结点值
调用自身打印右子
返回
下一页
上一页
停止放映
第 67 页
主程序 Btree.C
#include,stdio.h”
struct tree {
char info;
struct tree *left,*right;
}
main ( )
{ char *s,*c,key=??;
struct tree *create_btree(),*search_btree(),*root=0;
do {
printf(“Enter a letter:”);
gets(s);
if (!root)
root=create_btree(root,root,*s);
else
create_btrr(root,root,*s);
} while (*s) ;
下一页
上一页
停止放映
第 68 页
主程序 Btree.C(续）
print_btree(root,0);
key=?1?;
while ( key)
{
printf(“Enter a key to find:”);
scanf(“%s”,&c);
key=search_btree(root,c);
printf(“press to continue\n”);
}
} /* Btree.C 结束 */
下一页
上一页
停止放映
第 69 页
生成二叉排序树程序
struct tree create_btree(root,r,info)
struct tree *root,*r;
char info;
{ if (r = =0 )
{ r=malloc(sizeof(struct tree));
if ( r = = 0)
{ printf(“Out of memory\n”); exit(0); }
r->left= 0; r->right=0; r->info=info;
if (root)
{ if(info<root->info) root -> left=r;
else root->right=r;
}
else
{ r->right=0; r->left = 0; }
return r;
} /* if = = 0 接下页 */
下一页
上一页
停止放映
第 70 页
生成二叉排序树程序 （续）
if (info < r->info)
create_btree(r,r->left,info);
if(info>=r->info)
create_btree(r,r->right,info);
} /* create_btree(root,r,info) */
下一页
上一页
停止放映
第 71 页
struct tree *search_btree(root,key)
struct tree *root; char key;
{ if (!root)
{ printf(“Emptu btree\n”); return root; }
while(root->info!=key)
{ if(key<root->info)
root=root->left;
else
root=root->right;
if(root==0)
{ printf(“Search Failure\n”);
break ;
}
} /* while(root->info!=key) */
查询二叉排序树程序
下一页
上一页
停止放映
第 72 页
if (root !=0)
printf(“Successful search\n key=%c\n”,root->info);
return root ;
} /* *search_btree(root,key) */
查询二叉排序树程序（续）
下一页
上一页
停止放映
第 73 页
打印二叉排序树程序
print_btree(r,l)
struct tree *r;
int l;
{ int i;
if (r = = 0) return ;
print_tree(r->left,l+1);
for(i=0;i<l;i++)
printf(“,);
printf(“%c\n”,r->info);
print_btree(r->right,l+1);
}
下一页
上一页
停止放映
第 74 页
程序输入
输入,输出：
h ? b
d ? d
p ? e
r ? h
b ? p
e ? r
?
下一页
上一页
停止放映
第 75 页
举例
对数列 {10,18,3,4,9,13,25},生成二叉排序树 。
10
（ 1）
10
18
（ 2）
10
3 18
（ 3）
10
3 18
4 （ 4）
10
3
4
18
9（ 5）
（ 7）
10
3
9
4
18
13 25
10
3
4
9
18
13
（ 6）
示例
下一页
上一页
停止放映
第 76 页
平衡二叉排序树
在二叉排序树的动态生成过
程中, 由于数据本身的特性, 将
影响二叉排序树的性质, 例如 {3，
5,7,9,20}这样的数列, 生成
的二叉排序树就是一棵单枝树 。
因此, 在动态生成二叉排序树的
过程中, 要进行平衡化处理 。
平衡化处理就是在
不影响 二 叉 排序树特性的前题
下, 通过, 旋转, 处理, 使该结
点
的平衡因子不大于 2。
旋转分,LL,RR,LR和 RL
四种 。
3
5
7
9
20
下一页
上一页
停止放映
第 77 页
LL平衡化处理
由于在 A的左子树的左
子树上插入结点, 使 A
点失去平衡, 需进行
一次 LL旋转 （ 顺时针
旋转 ） 操作 。
程序实现为：
b = a?.lc
a?.lc = b?.rc
b?.rc = a
a?.bf = 0
b?.bf = 0
b为子树的新根
A
B
C
LL B
C A
示例
示意为：
下一页
上一页
停止放映
第 78 页
RR平衡化处理
由于在 A的右子树的右子
树上插入结点, 使 A点
失去平衡, 需进行一次
RR旋转 （ 逆时针旋转 ）
操作 。
程序实现为：
b = a?.rc
a?.rc = b?.lc
b?.lc = a
a?.bf = 0
b?.bf = 0
b为子树新根
A
B
C
RR B
A C
示例
示意为：
下一页
上一页
停止放映
第 79 页
LR平衡化处理
程序实现为：
b = a?.lc,c = b?.rc,a?.lc = c?.rc
b?.rc = c?.lc,c?.lc = b,c?.rc = a
A
B
C
C
B A
A
C
B
示例
由于在 A的左子树的右子树上插入结点, 使 A点失去平
衡, 需进行一次 LR旋转 （ 两次旋转 ;先逆时针,再顺
时针旋转 ） 操作 。
示意为：
下一页
上一页
停止放映
第 80 页
RL平衡化处理
由于在 A的右子树的左子树上插入结点, 使 A点失去平衡,
需进行一次 RL旋转 （ 两次旋转 ;先顺时针,再逆时针旋转 ）
操作 。
A
B
C
C
A B
A
C
B
程序实现为：
b = a?.rc,c = b?.lc,a?.rc = c?.lc
b?.lc = c?.rc,c?.lc = a,c?.rc = b
示意为：
示例
下一页
上一页
停止放映
第 81 页
平衡化处理举例
有数据序列 {13,24,37,90,53}
? 插入 13,树是平衡的 ;
? 插入 24,树仍为平衡 ;
? 插入 37,树不再平衡,
执行 RR旋转 ;
? 插入 90,树仍平衡 ;
? 插入 53,失去平衡,
执行 RL旋转,
13
(1)
13
24
(2)
13
24
37 3713
24
(3)
24
13 37
90
(4)
24
13 37
90
53
24
13 37
53
90
24
13 53
37 90
(5)
示例
下一页
上一页
停止放映
第 82 页
Huffman(哈夫曼）树及应用
? Huffman树的定义
? 构造 Huffman树
? Huffman编码
? Huffman编码的译码
下一页
上一页
停止放映
第 83 页
Huffman树的定义
? Huffman树也称为最优树，是一类带权路径最短
的二叉树。
? 树的带权路径长度定义为：
WPL = ∑ wklk
k = 1
n
其中：
n 是树中叶结点的个数
wi 是第 i个结点的权值
li 是第 i个结点的路径长度
下一页
上一页
停止放映
第 84 页
Huffman树举例
? 以下有三棵树：
（ a） （ b） （ c）
a
b
c d
a b c d
a
c
b
d7
7
7
5
5
52
2
2
4 4
4WPLa =7x2+5x2+2x2+4x2
= 36 WPL
b =7x3+5x3+2x1+4x2
= 46
WPLc =
7x1+5x2+2x3+4x3
= 35 √
? 事实证明按哈夫曼树构造二叉树，可得到很好的特
性，应用于实际问题，可提高处理效率。
下一页
上一页
停止放映
第 85 页
应用举例
? 由统计规律可知，考试成绩的分布符合正态分布：
-1 10
分数 0～ 59 60 ～ 69 70 ～ 79 80 ～ 89 90 ～ 100
比例数 0.05 0.15 0.40 0.3 0.10
? 根据正态分布规律，在 60 ～ 90之间的分数占 85%，
而不及格和优秀是少数。
下一页
上一页
停止放映
第 86 页
将百分制转换成五分制
? 判定树比较,a<60?
a<70?
a<80?
a<90?
不及格
及格
中等
良好 优秀
Y
Y
Y
Y
N N
N
N
a<80?
a<70? a<90?
a<60?
不及格
优秀良好中等及格不及格
Y
Y
Y N
N
N NY
(A)
(B)
? 若输入 1万个数据，按 A的判定过程进行操作，约需比较 3.2
万次，而按 B比较,则仅需 2.2万次。
下一页
上一页
停止放映
第 87 页
构造 Huffman树
? 构造 Huffman树算法步骤：
– 1）将 n个带权值 wi（ i≤n）的结点构成 n棵二叉树
的集合 T={T1,T2,……, Tn}，每棵二叉树只有一
个根结点。
– 2）在 T中选取两个权值最小的结点作为左右子树，
构成一个新的二叉树，其根结点的权值取左右子树
权值之和；
– 3）在 T中删除这两棵树，将新构成的树加入到 T中；
– 4）重复 2）,3）步的操作，直到 T中只含一棵树
为止，该树就是 Huffman树。
下一页
上一页
停止放映
第 88 页
构造 Huffman树举例
? 以权值分别为 7,5,2,4的结点 a,b,c,d构造 Huffman树。
T= { a b c d }
c d
T
32 4
6
b T3
T
2 65
11
b
T
2 65
11
c d2 4
18
a T27
11
T
1
6
18
a7
T
1
b T3
T
25
11
18
a7
T
1
b5
11
c d2
6
4（ d） T={ T1 }
（ c） T= { a T2 }
（ b） T= { a b T3 }
（ a） T= { a b c d }
代入 T2
代
入T
3
示例
下一页
上一页
停止放映
第 89 页
Huffman编码
? 编码：用二进制数的不同组合来表示字符的方法。
? 前缀编码：一种非等长度的编码 (任一个字符的编码
都不是另一个字符编码的前缀 )。
a
0
b
0
1
c d
0
1
1
编码,A（ 0）
B（ 01）
C（ 011）
D（ 111）
方法约定：
1）左分支为‘ 0’
2）右分支为‘ 1’
3）由叶到根路径上字符组
成的二进制串就是该叶结点
的编码。
? Huffman编码：一种非等长度的编码。以给定权
值的结点构造 Huffman树，按二进制前缀编码的
方式构成的编码为 Huffman编码。
下一页
上一页
停止放映
第 90 页
Huffman编码举例
? 在某系统的通信联络中可能出现 8种字符，其频率
分别为 0.05,0.29,0.07,0.08,0.14,0.23、
0.03,0.11，设权值分别为 {5,29,7,8,14，
23,3,11},n=8，其 Huffman树为：
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 91 页
Huffman编码存储结构
? 由于 Huffman树中没有度为 1的结点，则 n个叶结点
的 Huffman树共有 2n-1个结点。例如,4个结点的
Huffman树，共有 7个结点。因此可以用长度为 2n-1
的一维数组存放。
? 求 Huffman编码,从叶到根的编码。因此要知道每
个结点的父结点。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 92 页
Huffman编码的译码
? 从 Huffman编码树上不难看出，代码全部在叶结
点上，根据 Huffman编码，就能求出相应的字符。
该过程称为“译码”。
? 译码是根据从根到叶的 Huffman编码求相应的字
符。因此要知道每个结点的左右子结点。
? 例如，根据,1111”，就能求出对应的字符是,8”。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
下一页
上一页
停止放映
第 93 页
作业、思考题
1、思考题：
第 2章,1,9,12
1、本单元 作业：
5,6,7,11
2、作业要求：
– 作业命名方式为：
学号 _章数 _序号
00101001_ch02_1.doc
