Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 1页
6.3 树和森林
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 2页
6.3.1 树和森林的定义
树的定义
– 定义：树 (tree)是 n(n>0)个结点的有限集 T,其中：
（ 1）有且仅有一个特定的结点，称为树的根 (root)
（ 2）当 n>1时，其余结点可分为 m(m>0)个互不相交的有限集 T1,T2,……T m,其中每一个集合本身又是一棵树，称为根的子树 (subtree)
– 特点：
树中至少有一个结点 —— 根
树中各子树是互不相交的集合
森林 (forest)—— m(m?0)棵互不相交的树的集合
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 3页
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根子树
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 4页基本术语
结点 (node)—— 表示树中的元素，包括数据项及若干指向其子树的分支
结点的度 (degree)—— 结点拥有的子树数
叶子 (leaf)—— 度为 0的结点
孩子 (child)—— 结点子树的根称为该结点的孩子
双亲 (parents)—— 孩子结点的上层结点叫该结点的 ~
兄弟 (sibling)—— 同一双亲的孩子
树的度 —— 一棵树中最大的结点度数
结点的层次 (level)—— 从根结点算起，根为第一层，它的孩子为第二层 ……
深度 (depth)—— 树中结点的最大层次数
有序树和无序树
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 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的祖先
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 6页基本操作：
查 找 类
Root(T) // 求树的根结点
Value(T,cur_e) // 求当前结点的元素值
Parent(T,cur_e) // 求当前结点的双亲结点
LeftChild(T,cur_e) // 求当前结点的最左孩子
RightSibling(T,cur_e) // 求当前结点的右兄弟
TreeDepth(T) // 求树的深度
TraverseTree( T,Visit() ) // 遍历
插 入 类
InitTree(&T) // 初始化置空树
CreateTree(&T,definition) // 按定义构造树
Assign(T,cur_e,value) // 给当前结点赋值
InsertChild(&T,&p,i,c) // 将以 c为根的树插入为结点 p的第 i棵子树
删 除 类
DeleteChild(&T,&p,i) // 删除结点 p的第 i棵子树
DeleteChild(&T,&p,i) // 删除结点 p的第 i棵子树
DeleteChild(&T,&p,i) // 删除结点 p的第 i棵子树
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 7页
6.3.2 树和森林的存储结构
1.双亲表示法,
A
B C D
E F
G
0 A -1
1 B 0
2 C 0
3 D 0
4 E 2
5 F 2
6 G 5
r=0
n=6
data parent
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 8页
C语言的类型描述,
#define MAX_TREE_SIZE 100
结点结构,
typedef struct PTNode {
Elem data;
int parent; // 双亲位置域
} PTNode;
树结构,
typedef struct {
PTNode nodes [MAX_TREE_SIZE];
int r,n; // 根结点的位置和结点个数
} PTree;
data parent
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 9页
A
B C D
E F
G
0 A
1 B
2 C
3 D
4 E
5 F
6 G
r=0
n=6
data firstchild
1 2 3
4 5
6
2.孩子链表表示法,
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 10页
C语言的类型描述,
孩子结点结构,
typedef struct CTNode {
int child;
struct CTNode *next;
} *ChildPtr;
双亲结点结构
typedef struct {
Elem data;
ChildPtr firstchild; // 孩子链的头指针
} CTBox;
树结构,
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n,r; // 结点数和根结点的位置
} CTree;
child next
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 11页
3.树的二叉链表 (孩子 -兄弟）存储表示法
A
B C D
E F
G
A
B
C
E D
F
G
root
A
B
C
E D
F
G
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 12页
C语言的类型描述,
结点结构,
typedef struct CSNode{
Elem data;
struct CSNode *firstchild,*nextsibling;
} CSNode,*CSTree
firstchild data nextsibling
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 13页将树转换成二叉树
加线：在兄弟之间加一连线
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
旋转：以树的根结点为轴心，将整树顺时针转 45°
A
B C D
E F G H I
A
B C D
E F G H I
A
B
C
D
E
F
G H
I
树转换成的二叉树其右子树一定为空
A
B C D
E F G H I
A
B C D
E F G H I
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 14页将 二叉 树转换成树
加线：若 p结点是双亲结点的左孩子，则将 p的右孩子，右孩子的右孩子，
沿分支找到的所有右孩子，都与 p的双亲用线连起来
抹线：抹掉原二叉树中双亲与右孩子之间的连线
调整：将结点按层次排列，形成树结构
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
IA
B C D
E F G H I
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 15页森林和二叉树的对应关系
设森林 F = ( T1,T2,…,Tn );
T1 = (root,t11,t12,…,t1m);
二叉树
B =( LBT,Node(root),RBT );
由森林转换成二叉树的转换规则为,
若 F = Φ，则 B = Φ；
否则，
由 ROOT( T1 ) 对应得到 Node(root)；
由 (t11,t12,…,t1m ) 对应得到 LBT；
由 (T2,T3,…,Tn ) 对应得到 RBT。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 16页森林和二叉树的对应关系
由二叉树转换为森林的转换规则为：
若 B = Φ,则 F = Φ；
否则，
由 Node(root) 对应得到 ROOT( T1 )；
由 LBT 对应得到 ( t11,t12,…,t1m)；
由 RBT 对应得到 (T2,T3,…,Tn)。
由此，树的各种操作均可对应二叉树的操作来完成。
应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为,左是孩子，右是兄弟。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 17页森林转换成二叉树
将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
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
JA
B
C
D
E
F
G
H
I
J
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 18页二叉树转换成森林
抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
还原：将孤立的二叉树还原成树
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
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 19页
6.3.3 树和森林的遍历树的遍历可有三条搜索路径,
先根 (次序 )遍历,若树不空，则先访问根结点，然后依次先根遍历各棵子树。
后根 (次序 )遍历,若树不空，则先依次后根遍历各棵子树，然后访问根结点。
按层次遍历,若树不空，则自上而下自左至右访问树中每个结点。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 20页
A
B C D
E F G
H
I J K
先根遍历时顶点的访问次序：
A B E F C D G H I J K
后根遍历时顶点的访问次序：
E F B C I J K H G D A
层次遍历时顶点的访问次序：
A B C D E F G H I J K
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 21页森林由三部分构成
1．森林中第一棵树的根结点；
2．森林中第一棵树的子树森林；
3．森林中其它树构成的森林。
B C D
E F G
H
I J K
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 22页森林的遍历
1,先序遍历若森林不空，则访问 森林中第一棵树的根结点；
先序遍历 森林中第一棵树的子树森林；
先序遍历 森林中 (除第一棵树之外 )其余树构成的森林。
即,依次从左至右 对森林中的每一棵 树 进行 先根遍历 。
A B C D E F G H I J
２．中序遍历若森林不空，则中序遍历 森林中第一棵树的子树森林；
访问 森林中第一棵树的根结点；
中序遍历 森林中 (除第一棵树之外 )其余树构成的森林。
即,依次从左至右 对森林中的每一棵 树 进行 后根遍历 。
B C D A F E H J I G
A
B C D
E
F
G
H I
J
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 23页
6.4 树的应用
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 24页
6.4.1 堆排序的实现
堆的定义,n个元素的序列 (k1,k2,…… kn)，当且仅当满足下列关系时，称之为堆或 (i=1,2,…..,?n/2?)ki?k2ik
i?k2i+1
ki?k2i
ki?k2i+1
例 （ 96,83,27,38,11,9）
例 （ 13,38,27,50,76,65,49,97）
96
27
91138
83
13
2738
49657650
97
可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中
n个元素的最小值或最大值
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 25页
堆排序,将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的 n-1个元素重又建成一个堆，则可得到 n个元素的次小值；重复执行，得到一个有序序列，这个过程叫 ~
堆排序需解决的两个问题：
– 如何由一个无序序列建成一个堆？
– 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？
第二个问题解决方法 —— 筛选
– 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 26页例,小顶堆,降序排序
13
2738
49657650
97
97
2738
49657650
13
输出,13
27
4938
97657650
13
输出,13
97
4938
27657650
13
输出,13 27
38
4950
27657697
13
输出,13 27
65
4950
27387697
13
输出,13 27 38
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 27页
49
6550
27387697
13
输出,13 27 38
76
6550
27384997
13
输出,13 27 38 49
50
6576
27384997
13
输出,13 27 38 49
97
6576
27384950
13
输出,13 27 38 49 50
65
9776
27384950
13
输出,13 27 38 49 50
97
6576
27384950
13
输出,13 27 38 49 50 65
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 28页
76
6597
27384950
13
输出,13 27 38 49 50 65
97
6576
27384950
13
输出,13 27 38 49 50 65 76
97
6576
27384950
13
输出,13 27 38 49 50 65 76 97
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 29页例 含 8个元素的无序序列（ 49,38,65,97,76,13,27,50）
49
6538
27137697
50
49
6538
27137650
97
49
1338
27657650
97
49
1338
27657650
97
13
2738
49657650
97
第一个问题解决方法
–方法：从无序序列的第?n/2?个元素
（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 30页算法 6.14
void HeapAdjust (HeapType &H,int s,int m) {
// 已知 H.r[s..m]中记录的关键字除 H.r[s].key之外均满足堆的定义，
//本函数依据关键字的大小对 H.r[s]进行调整，使 H.r[s..m]成为一个
//大顶堆 (对其中记录的关键字而言 )
rc = H.r[s]; // 暂存根结点的记录
for ( j=2*s; j<=m; j*=2 ) { // 沿 key较大的孩子结点向下筛选
if ( j<m && H.r[j].key<H.r[j+1].key ) ++j;
// j为 key较大孩子记录的下标
if ( rc.key >= H.r[j].key ) break; // 不需要调整
H.r[s] = H.r[j]; s = j; // 把大关键字记录往上调
}
H.r[s] = rc; // 回移筛选下来的记录
} // HeapAdjust
30
27
91138
83
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 31页算法 6.15
void HeapSort ( HeapType &H ) {
// 对顺序表 H进行堆排序。
for ( i=H.length/2; i>0; --i )
HeapAdjust ( H,i,H.length );//把 H.r[1..H.length]建成大顶堆
w=H.r[1] ; H.r[1]= H.r[H.length]; H.r[H.length]=w;
//交换 "堆顶 "和 "堆底 "的记录
for ( i=H.length-1; i>1; --i ) {
HeapAdjust(H,1,i);
// 从根开始调整，将 H.r[1..i] 重新调整为大顶堆
w=H.r[1]; H.r[1]=H.r[i]; H.r[i]=w;
// 将堆顶记录和当前的,堆底,记录相互交换
// 使已有序的记录堆积到底部
}
} // HeapSort
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 32页算法评价
时间复杂度：最坏情况下 T(n)=O(nlogn)
空间复杂度,S(n)=O(1)
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 33页二叉排序树
定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉排序树
10
183
8 122
7
3
中序遍历二叉排序树可得到一个关键字的有序序列
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 34页二叉排序树生成新结点插入原则：
若二叉排序树为空，则插入结点应为新的根结点；
否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子二叉排序树生成：
从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
10
183
8
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 35页插入算法例 {10,18,3,8,12,2,7,3}
10 10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 36页算法 6.16
void Insert_BST( BiTree &T,KeyType e ) {
// 在以 T为根指针的二叉排序树中插入记录 e
s = new BiTNode;; // 生成新的结点
s ->data = e; s->lchild = NULL; s->rchild = NULL;
// 新插入结点必为叶子结点
if (!T) T = s; // 插入的结点为根结点
else {
p = T;
while ( p) // 查找插入位置
if ( e,key< p->data,key)
{ f = p; p = p->lchild; } // 应插入在左子树中
else
{ f = p; p = p->rchild; } // 应插入在右子树中
if ( e.key < f->data.key ) f->lchild = s;
// 插入为 f 所指结点的左子树根
else f->rchild = s; / 插入为 f所指结点的右子树根
} //else
} // Insert_BST
10
183
8
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 37页算法 6.17
void BSTSort( SqTable &L )
// 利用二叉排序树对顺序表 L进行排序
BiTree T = NULL; // 初始化二叉排序树为空树
for ( i=1; i<L.length; ++i)
Insert_BST( T,L.r[i] ); // 按顺序表 L构造二叉排序树
i = 0;
InOrder( T,Output(T,L,i) ); // 中序遍历二叉排序树
// 通过函数指针引用 Output，将排序的记录由小到大输出至 L.r[i]
} // BSTSort
其中函数 Output的具体实现如下：
void Output ( BiTree T,SqTable &L,int & i ){
L.r[++i]=T->data;
}
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 38页
6.4.3 Huffman树及其应用
Huffman树又称最优树，是带权路径长度最短的树，它有着极为广泛的应用
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 39页基本术语
路径 (Path)：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度 (path Length),路径上的分支数目称之为路径长度。
树的路径长度,从树根到树中每个结点的路径长度之和称之为树的路径长度。
A
B C
D E
F G
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 40页基本术语
结点的带权路径长度 (Weight Path Length)：
结点的带权路径长度是从该结点到树根之间的路径长度与结点上权值的乘积。
树的带权路径长度,树中所有叶子结点的带权路径长度之和，通常记做：
WPL = w1*l1 + w2*l2 + … + wn*ln
其中,n为树中叶子结点的个数；
wi为第 i个叶子结点的权值；
l1为第 i个叶子结点的路径长度。
Huffman树,具有 n个结点的二叉树不止一棵，
但在所有取同一权值的二叉树中，必定存在一棵 WPL值最小的树，我们称这棵树为 Huffman树
（或称最优树）。
2
4
5 9
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 41页例如下图中的三棵树，都有 4个叶子结点，分别带权为 2,4,5,9，
它们的带权路径长度分别为：
⑴ WPL＝ 2× 2＋ 4× 2＋ 5× 2＋ 9× 2＝ 40；
⑵ WPL＝ 4× 2＋ 5× 3＋ 9× 3＋ 2× 1＝ 52；
⑶ WPL＝ 9× 1＋ 5× 2＋ 2× 3＋ 4× 3＝ 37。
其中⑶的 WPL值最小，可以证明它是 Huffman树。
2 4 5 9
2
4
5 9
5
9
2 4
(1) (2) (3)
具有相同叶子结点、不同带权路径长度的二叉树示例
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 42页哈夫曼树的应用
（ 1）判定树在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。
例 1 将学生百分成绩按分数段分级的程序。
若学生成绩分布是均匀的，可用图（ a)二叉树结构来实现。
a<60
a<70
a<80
a<90
不及格中等良好 优秀及格
Y N
Y N
Y N
Y N
(a)
输入 10000个数据，则需进行 31500次比较。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 43页分数 0— 59 60— 69 70— 79 80— 89 90— 99
比例 0.05 0.15 0.4 0.3 0.10
70≤a≤ 80
a<60
80≤a<90
60≤a<70
(b)
(c)
学生成绩分布不是均匀的情况：
以比例数为权构造一棵哈夫曼树,如 （ b)判断树所示 。
再将每一比较框的两次比较改为一次,可得到 （ c)判定树 。
输入 10000个数据，仅需进行 22000次比较。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 44页
Huffman树的构造按照 Huffman树的定义,Huffman最早提出了构造最优树的方法，其基本 思想 是：
⑴ 由给定的 n个权值构成 n棵二叉树的集合 F，其中每一棵二叉树中只有一个带权的根结点；
⑵ 在 F中选取两棵根结点权值最小的二叉树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点权值之和；
⑶ 在 F中删除这两棵二叉树，同时将新得到的二叉树加入到 F中；
⑷ 重复⑵和⑶，直到 F中只含一棵二叉树为止。
例
a
7
b5 c
2
d
4
a
7
b5
c
2
d
4
6
a
7
b5
c
2
d
4
6
11
a
7
b5
c
2
d
4
6
11
18
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 45页规定：
在构造 Huffman的过程中，为了规范起见，我们做出如下规定,
⑴ 集合中权值小的作为新构造的二叉树的左子树，权值大的作为新构造的二叉树的右子树；
⑵ 权值相等时，选取深度小的二叉树作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。
⑶ 按照给定权值出现的先后次序构造 Huffman树。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 46页
一棵有 n个叶子结点的 Huffman树有 2n-1个结点
采用顺序存储结构 —— 一维结构数组
typedef struct{
int weight;
int lchild,rchild;
}HTNode
typedef struct{
HTNode *HTree; //动态分配数组存储树结点
int root; //根结点的位置
}Huffman Tree;
Huffman树存储结构
weight lchild rchild
……
HTreeweight lchild rchild00
1
2
…
2n-1
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 47页算法 6.18
void CreateHuffmanTree(HuffmanTree &HT,int *w,int n) {
// w存放 n个权值 (均 >0)，构造赫夫曼树 HT
if (n<=1) return;
m = 2 * n - 1;
HT.HTree = new HTNode[m]; // 为赫夫曼树分配一组顺序空间
for (p=HT.Tree,i=1; i<=n; ++i,++p,++w) *p = { *w,-1,-1 };
// n个带权结点形成初始化的森林，每个结点的左、右孩子为空
for ( ;i<=m;++i,++p) *p ={0,-1,-1};//对尚未使用的结点赋初值
for (i=n;i<m;++i){ // 建赫夫曼树
Select(HT.Htree,i-1,s1,s2);
// 在 HT.Htree[0..i-1]当前可选的结点中选择权值
// 最小的两个结点，其序号分别为 s1和 s2。
HT.Htree [i].lchild = s1; HT.Htree[i].rchild = s2;
HT.Htree[i].weight = HT.Htree[s1].weight + HT.Htree[s2].weight;
//取左、右子树根结点权值之和
}
HT.root = m-1;
} // CreatHuffmanTree
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 48页前缀编码
前缀编码指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
利用赫夫曼树可以构造一种 不等长 的二进制编码，
并且构造所得的赫夫曼编码是一种最优前缀编码，
即使所传字符编码（电文）的总长度最短。
a
0
b0
c0 d1
1
1
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 49页方法：
（ 1） 用 { 2,4,2,3,3 }作为叶子结点的权值生成一棵哈夫曼树,并将对应权值 wi的叶子结点注明对应的字符；
（ 2） 约定左分支表示字符,0”,右分支表示字符 ‘ 1’
（ 3） 从叶子结点开始,顺着双亲反推上去,直到根结点,
路径上的 ‘ 0’或 ‘ 1’连接的序列就是结点对应的字符的二进制编码的逆序 。
哈夫曼编码 -----利用哈夫曼树构造通讯中电文编码 （ 前缀码 ）
例：要传输的电文是 {CAS； CAT； SAT； AT}
要传输的字符集是 D={C,A,S,T,； }
每个字符出现的频率是 W={ 2,4,2,3,3 }
14
6 8
3 3 4 4
2 2
0
00
0
1
11
1
T ; A
C S
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 50页
14
6 8
3 3 4 4
2 2
0
00
0
1
11
1
T ; A
C S
各字符编码是 T ； A C S
00 01 10 110 111
{CAS； CAT； SAT； AT}电文编码：
11010111011101000011111000011000
注意：编码的总长度恰好为哈夫曼树的带权路径长 。
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 1页
6.3 树和森林
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 2页
6.3.1 树和森林的定义
树的定义
– 定义：树 (tree)是 n(n>0)个结点的有限集 T,其中：
（ 1）有且仅有一个特定的结点，称为树的根 (root)
（ 2）当 n>1时，其余结点可分为 m(m>0)个互不相交的有限集 T1,T2,……T m,其中每一个集合本身又是一棵树，称为根的子树 (subtree)
– 特点：
树中至少有一个结点 —— 根
树中各子树是互不相交的集合
森林 (forest)—— m(m?0)棵互不相交的树的集合
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 3页
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根子树
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 4页基本术语
结点 (node)—— 表示树中的元素，包括数据项及若干指向其子树的分支
结点的度 (degree)—— 结点拥有的子树数
叶子 (leaf)—— 度为 0的结点
孩子 (child)—— 结点子树的根称为该结点的孩子
双亲 (parents)—— 孩子结点的上层结点叫该结点的 ~
兄弟 (sibling)—— 同一双亲的孩子
树的度 —— 一棵树中最大的结点度数
结点的层次 (level)—— 从根结点算起，根为第一层，它的孩子为第二层 ……
深度 (depth)—— 树中结点的最大层次数
有序树和无序树
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 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的祖先
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 6页基本操作：
查 找 类
Root(T) // 求树的根结点
Value(T,cur_e) // 求当前结点的元素值
Parent(T,cur_e) // 求当前结点的双亲结点
LeftChild(T,cur_e) // 求当前结点的最左孩子
RightSibling(T,cur_e) // 求当前结点的右兄弟
TreeDepth(T) // 求树的深度
TraverseTree( T,Visit() ) // 遍历
插 入 类
InitTree(&T) // 初始化置空树
CreateTree(&T,definition) // 按定义构造树
Assign(T,cur_e,value) // 给当前结点赋值
InsertChild(&T,&p,i,c) // 将以 c为根的树插入为结点 p的第 i棵子树
删 除 类
DeleteChild(&T,&p,i) // 删除结点 p的第 i棵子树
DeleteChild(&T,&p,i) // 删除结点 p的第 i棵子树
DeleteChild(&T,&p,i) // 删除结点 p的第 i棵子树
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 7页
6.3.2 树和森林的存储结构
1.双亲表示法,
A
B C D
E F
G
0 A -1
1 B 0
2 C 0
3 D 0
4 E 2
5 F 2
6 G 5
r=0
n=6
data parent
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 8页
C语言的类型描述,
#define MAX_TREE_SIZE 100
结点结构,
typedef struct PTNode {
Elem data;
int parent; // 双亲位置域
} PTNode;
树结构,
typedef struct {
PTNode nodes [MAX_TREE_SIZE];
int r,n; // 根结点的位置和结点个数
} PTree;
data parent
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 9页
A
B C D
E F
G
0 A
1 B
2 C
3 D
4 E
5 F
6 G
r=0
n=6
data firstchild
1 2 3
4 5
6
2.孩子链表表示法,
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 10页
C语言的类型描述,
孩子结点结构,
typedef struct CTNode {
int child;
struct CTNode *next;
} *ChildPtr;
双亲结点结构
typedef struct {
Elem data;
ChildPtr firstchild; // 孩子链的头指针
} CTBox;
树结构,
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n,r; // 结点数和根结点的位置
} CTree;
child next
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 11页
3.树的二叉链表 (孩子 -兄弟）存储表示法
A
B C D
E F
G
A
B
C
E D
F
G
root
A
B
C
E D
F
G
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 12页
C语言的类型描述,
结点结构,
typedef struct CSNode{
Elem data;
struct CSNode *firstchild,*nextsibling;
} CSNode,*CSTree
firstchild data nextsibling
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 13页将树转换成二叉树
加线：在兄弟之间加一连线
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
旋转：以树的根结点为轴心，将整树顺时针转 45°
A
B C D
E F G H I
A
B C D
E F G H I
A
B
C
D
E
F
G H
I
树转换成的二叉树其右子树一定为空
A
B C D
E F G H I
A
B C D
E F G H I
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 14页将 二叉 树转换成树
加线：若 p结点是双亲结点的左孩子，则将 p的右孩子，右孩子的右孩子，
沿分支找到的所有右孩子，都与 p的双亲用线连起来
抹线：抹掉原二叉树中双亲与右孩子之间的连线
调整：将结点按层次排列，形成树结构
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
IA
B C D
E F G H I
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 15页森林和二叉树的对应关系
设森林 F = ( T1,T2,…,Tn );
T1 = (root,t11,t12,…,t1m);
二叉树
B =( LBT,Node(root),RBT );
由森林转换成二叉树的转换规则为,
若 F = Φ，则 B = Φ；
否则，
由 ROOT( T1 ) 对应得到 Node(root)；
由 (t11,t12,…,t1m ) 对应得到 LBT；
由 (T2,T3,…,Tn ) 对应得到 RBT。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 16页森林和二叉树的对应关系
由二叉树转换为森林的转换规则为：
若 B = Φ,则 F = Φ；
否则，
由 Node(root) 对应得到 ROOT( T1 )；
由 LBT 对应得到 ( t11,t12,…,t1m)；
由 RBT 对应得到 (T2,T3,…,Tn)。
由此，树的各种操作均可对应二叉树的操作来完成。
应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为,左是孩子，右是兄弟。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 17页森林转换成二叉树
将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
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
JA
B
C
D
E
F
G
H
I
J
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 18页二叉树转换成森林
抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
还原：将孤立的二叉树还原成树
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
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 19页
6.3.3 树和森林的遍历树的遍历可有三条搜索路径,
先根 (次序 )遍历,若树不空，则先访问根结点，然后依次先根遍历各棵子树。
后根 (次序 )遍历,若树不空，则先依次后根遍历各棵子树，然后访问根结点。
按层次遍历,若树不空，则自上而下自左至右访问树中每个结点。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 20页
A
B C D
E F G
H
I J K
先根遍历时顶点的访问次序：
A B E F C D G H I J K
后根遍历时顶点的访问次序：
E F B C I J K H G D A
层次遍历时顶点的访问次序：
A B C D E F G H I J K
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 21页森林由三部分构成
1．森林中第一棵树的根结点；
2．森林中第一棵树的子树森林；
3．森林中其它树构成的森林。
B C D
E F G
H
I J K
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 22页森林的遍历
1,先序遍历若森林不空，则访问 森林中第一棵树的根结点；
先序遍历 森林中第一棵树的子树森林；
先序遍历 森林中 (除第一棵树之外 )其余树构成的森林。
即,依次从左至右 对森林中的每一棵 树 进行 先根遍历 。
A B C D E F G H I J
２．中序遍历若森林不空，则中序遍历 森林中第一棵树的子树森林；
访问 森林中第一棵树的根结点；
中序遍历 森林中 (除第一棵树之外 )其余树构成的森林。
即,依次从左至右 对森林中的每一棵 树 进行 后根遍历 。
B C D A F E H J I G
A
B C D
E
F
G
H I
J
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 23页
6.4 树的应用
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 24页
6.4.1 堆排序的实现
堆的定义,n个元素的序列 (k1,k2,…… kn)，当且仅当满足下列关系时，称之为堆或 (i=1,2,…..,?n/2?)ki?k2ik
i?k2i+1
ki?k2i
ki?k2i+1
例 （ 96,83,27,38,11,9）
例 （ 13,38,27,50,76,65,49,97）
96
27
91138
83
13
2738
49657650
97
可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中
n个元素的最小值或最大值
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 25页
堆排序,将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的 n-1个元素重又建成一个堆，则可得到 n个元素的次小值；重复执行，得到一个有序序列，这个过程叫 ~
堆排序需解决的两个问题：
– 如何由一个无序序列建成一个堆？
– 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？
第二个问题解决方法 —— 筛选
– 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 26页例,小顶堆,降序排序
13
2738
49657650
97
97
2738
49657650
13
输出,13
27
4938
97657650
13
输出,13
97
4938
27657650
13
输出,13 27
38
4950
27657697
13
输出,13 27
65
4950
27387697
13
输出,13 27 38
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 27页
49
6550
27387697
13
输出,13 27 38
76
6550
27384997
13
输出,13 27 38 49
50
6576
27384997
13
输出,13 27 38 49
97
6576
27384950
13
输出,13 27 38 49 50
65
9776
27384950
13
输出,13 27 38 49 50
97
6576
27384950
13
输出,13 27 38 49 50 65
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 28页
76
6597
27384950
13
输出,13 27 38 49 50 65
97
6576
27384950
13
输出,13 27 38 49 50 65 76
97
6576
27384950
13
输出,13 27 38 49 50 65 76 97
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 29页例 含 8个元素的无序序列（ 49,38,65,97,76,13,27,50）
49
6538
27137697
50
49
6538
27137650
97
49
1338
27657650
97
49
1338
27657650
97
13
2738
49657650
97
第一个问题解决方法
–方法：从无序序列的第?n/2?个元素
（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 30页算法 6.14
void HeapAdjust (HeapType &H,int s,int m) {
// 已知 H.r[s..m]中记录的关键字除 H.r[s].key之外均满足堆的定义，
//本函数依据关键字的大小对 H.r[s]进行调整，使 H.r[s..m]成为一个
//大顶堆 (对其中记录的关键字而言 )
rc = H.r[s]; // 暂存根结点的记录
for ( j=2*s; j<=m; j*=2 ) { // 沿 key较大的孩子结点向下筛选
if ( j<m && H.r[j].key<H.r[j+1].key ) ++j;
// j为 key较大孩子记录的下标
if ( rc.key >= H.r[j].key ) break; // 不需要调整
H.r[s] = H.r[j]; s = j; // 把大关键字记录往上调
}
H.r[s] = rc; // 回移筛选下来的记录
} // HeapAdjust
30
27
91138
83
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 31页算法 6.15
void HeapSort ( HeapType &H ) {
// 对顺序表 H进行堆排序。
for ( i=H.length/2; i>0; --i )
HeapAdjust ( H,i,H.length );//把 H.r[1..H.length]建成大顶堆
w=H.r[1] ; H.r[1]= H.r[H.length]; H.r[H.length]=w;
//交换 "堆顶 "和 "堆底 "的记录
for ( i=H.length-1; i>1; --i ) {
HeapAdjust(H,1,i);
// 从根开始调整，将 H.r[1..i] 重新调整为大顶堆
w=H.r[1]; H.r[1]=H.r[i]; H.r[i]=w;
// 将堆顶记录和当前的,堆底,记录相互交换
// 使已有序的记录堆积到底部
}
} // HeapSort
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 32页算法评价
时间复杂度：最坏情况下 T(n)=O(nlogn)
空间复杂度,S(n)=O(1)
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 33页二叉排序树
定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉排序树
10
183
8 122
7
3
中序遍历二叉排序树可得到一个关键字的有序序列
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 34页二叉排序树生成新结点插入原则：
若二叉排序树为空，则插入结点应为新的根结点；
否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子二叉排序树生成：
从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
10
183
8
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 35页插入算法例 {10,18,3,8,12,2,7,3}
10 10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 36页算法 6.16
void Insert_BST( BiTree &T,KeyType e ) {
// 在以 T为根指针的二叉排序树中插入记录 e
s = new BiTNode;; // 生成新的结点
s ->data = e; s->lchild = NULL; s->rchild = NULL;
// 新插入结点必为叶子结点
if (!T) T = s; // 插入的结点为根结点
else {
p = T;
while ( p) // 查找插入位置
if ( e,key< p->data,key)
{ f = p; p = p->lchild; } // 应插入在左子树中
else
{ f = p; p = p->rchild; } // 应插入在右子树中
if ( e.key < f->data.key ) f->lchild = s;
// 插入为 f 所指结点的左子树根
else f->rchild = s; / 插入为 f所指结点的右子树根
} //else
} // Insert_BST
10
183
8
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 37页算法 6.17
void BSTSort( SqTable &L )
// 利用二叉排序树对顺序表 L进行排序
BiTree T = NULL; // 初始化二叉排序树为空树
for ( i=1; i<L.length; ++i)
Insert_BST( T,L.r[i] ); // 按顺序表 L构造二叉排序树
i = 0;
InOrder( T,Output(T,L,i) ); // 中序遍历二叉排序树
// 通过函数指针引用 Output，将排序的记录由小到大输出至 L.r[i]
} // BSTSort
其中函数 Output的具体实现如下：
void Output ( BiTree T,SqTable &L,int & i ){
L.r[++i]=T->data;
}
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 38页
6.4.3 Huffman树及其应用
Huffman树又称最优树，是带权路径长度最短的树，它有着极为广泛的应用
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 39页基本术语
路径 (Path)：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度 (path Length),路径上的分支数目称之为路径长度。
树的路径长度,从树根到树中每个结点的路径长度之和称之为树的路径长度。
A
B C
D E
F G
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 40页基本术语
结点的带权路径长度 (Weight Path Length)：
结点的带权路径长度是从该结点到树根之间的路径长度与结点上权值的乘积。
树的带权路径长度,树中所有叶子结点的带权路径长度之和，通常记做：
WPL = w1*l1 + w2*l2 + … + wn*ln
其中,n为树中叶子结点的个数；
wi为第 i个叶子结点的权值；
l1为第 i个叶子结点的路径长度。
Huffman树,具有 n个结点的二叉树不止一棵，
但在所有取同一权值的二叉树中，必定存在一棵 WPL值最小的树，我们称这棵树为 Huffman树
（或称最优树）。
2
4
5 9
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 41页例如下图中的三棵树，都有 4个叶子结点，分别带权为 2,4,5,9，
它们的带权路径长度分别为：
⑴ WPL＝ 2× 2＋ 4× 2＋ 5× 2＋ 9× 2＝ 40；
⑵ WPL＝ 4× 2＋ 5× 3＋ 9× 3＋ 2× 1＝ 52；
⑶ WPL＝ 9× 1＋ 5× 2＋ 2× 3＋ 4× 3＝ 37。
其中⑶的 WPL值最小，可以证明它是 Huffman树。
2 4 5 9
2
4
5 9
5
9
2 4
(1) (2) (3)
具有相同叶子结点、不同带权路径长度的二叉树示例
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 42页哈夫曼树的应用
（ 1）判定树在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。
例 1 将学生百分成绩按分数段分级的程序。
若学生成绩分布是均匀的，可用图（ a)二叉树结构来实现。
a<60
a<70
a<80
a<90
不及格中等良好 优秀及格
Y N
Y N
Y N
Y N
(a)
输入 10000个数据，则需进行 31500次比较。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 43页分数 0— 59 60— 69 70— 79 80— 89 90— 99
比例 0.05 0.15 0.4 0.3 0.10
70≤a≤ 80
a<60
80≤a<90
60≤a<70
(b)
(c)
学生成绩分布不是均匀的情况：
以比例数为权构造一棵哈夫曼树,如 （ b)判断树所示 。
再将每一比较框的两次比较改为一次,可得到 （ c)判定树 。
输入 10000个数据，仅需进行 22000次比较。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 44页
Huffman树的构造按照 Huffman树的定义,Huffman最早提出了构造最优树的方法，其基本 思想 是：
⑴ 由给定的 n个权值构成 n棵二叉树的集合 F，其中每一棵二叉树中只有一个带权的根结点；
⑵ 在 F中选取两棵根结点权值最小的二叉树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点权值之和；
⑶ 在 F中删除这两棵二叉树，同时将新得到的二叉树加入到 F中；
⑷ 重复⑵和⑶，直到 F中只含一棵二叉树为止。
例
a
7
b5 c
2
d
4
a
7
b5
c
2
d
4
6
a
7
b5
c
2
d
4
6
11
a
7
b5
c
2
d
4
6
11
18
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 45页规定：
在构造 Huffman的过程中，为了规范起见，我们做出如下规定,
⑴ 集合中权值小的作为新构造的二叉树的左子树，权值大的作为新构造的二叉树的右子树；
⑵ 权值相等时，选取深度小的二叉树作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。
⑶ 按照给定权值出现的先后次序构造 Huffman树。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 46页
一棵有 n个叶子结点的 Huffman树有 2n-1个结点
采用顺序存储结构 —— 一维结构数组
typedef struct{
int weight;
int lchild,rchild;
}HTNode
typedef struct{
HTNode *HTree; //动态分配数组存储树结点
int root; //根结点的位置
}Huffman Tree;
Huffman树存储结构
weight lchild rchild
……
HTreeweight lchild rchild00
1
2
…
2n-1
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 47页算法 6.18
void CreateHuffmanTree(HuffmanTree &HT,int *w,int n) {
// w存放 n个权值 (均 >0)，构造赫夫曼树 HT
if (n<=1) return;
m = 2 * n - 1;
HT.HTree = new HTNode[m]; // 为赫夫曼树分配一组顺序空间
for (p=HT.Tree,i=1; i<=n; ++i,++p,++w) *p = { *w,-1,-1 };
// n个带权结点形成初始化的森林，每个结点的左、右孩子为空
for ( ;i<=m;++i,++p) *p ={0,-1,-1};//对尚未使用的结点赋初值
for (i=n;i<m;++i){ // 建赫夫曼树
Select(HT.Htree,i-1,s1,s2);
// 在 HT.Htree[0..i-1]当前可选的结点中选择权值
// 最小的两个结点，其序号分别为 s1和 s2。
HT.Htree [i].lchild = s1; HT.Htree[i].rchild = s2;
HT.Htree[i].weight = HT.Htree[s1].weight + HT.Htree[s2].weight;
//取左、右子树根结点权值之和
}
HT.root = m-1;
} // CreatHuffmanTree
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 48页前缀编码
前缀编码指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
利用赫夫曼树可以构造一种 不等长 的二进制编码，
并且构造所得的赫夫曼编码是一种最优前缀编码，
即使所传字符编码（电文）的总长度最短。
a
0
b0
c0 d1
1
1
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 49页方法：
（ 1） 用 { 2,4,2,3,3 }作为叶子结点的权值生成一棵哈夫曼树,并将对应权值 wi的叶子结点注明对应的字符；
（ 2） 约定左分支表示字符,0”,右分支表示字符 ‘ 1’
（ 3） 从叶子结点开始,顺着双亲反推上去,直到根结点,
路径上的 ‘ 0’或 ‘ 1’连接的序列就是结点对应的字符的二进制编码的逆序 。
哈夫曼编码 -----利用哈夫曼树构造通讯中电文编码 （ 前缀码 ）
例：要传输的电文是 {CAS； CAT； SAT； AT}
要传输的字符集是 D={C,A,S,T,； }
每个字符出现的频率是 W={ 2,4,2,3,3 }
14
6 8
3 3 4 4
2 2
0
00
0
1
11
1
T ; A
C S
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 50页
14
6 8
3 3 4 4
2 2
0
00
0
1
11
1
T ; A
C S
各字符编码是 T ； A C S
00 01 10 110 111
{CAS； CAT； SAT； AT}电文编码：
11010111011101000011111000011000
注意：编码的总长度恰好为哈夫曼树的带权路径长 。
