,数据结构,
第六章 (下 )
数据结构
tjm
静态双亲链表的类型定义参见 P135
6.4 树和森林
6.4.1 树的存储结构
双亲表示法
实现：定义数组存放树的结点，每个结点含两个域：
数据域：存放结点本身信息。
双亲域：指示本结点的双亲结点在数组中的位置。
特点：找双亲容易，找孩子难。
数据结构
tjm
a
b c
d e f
hg i
－ 1
0
1
1
2
4
4
4
0
a
c
d
e
f
g
h
i
b
data parent
5
0
1
2
3
4
6
7
8
数据结构
tjm
a
b c
d e f
hg i
1 2 ^
3 4 ^
86 7 ^
5 ^
5
0
1
2
3
4
6
7
8
a
c
d
e
f
g
h
i
b
^
^
^
^
^
data fc
孩子链表表示法 （ 类型定义参见 P136）
每个结点的孩子结点用单链表存储，再用含 n个
元素的数组指向每个孩子链表。
数据结构
tjm
5
0
1
2
3
4
6
7
8
a
c
d
e
f
g
h
i
b
data fc
1 2
3 4
86 7
5
^
^
^
^
^
^
^
^
^
－ 1
0
1
1
2
4
4
4
0
parent
a
b c
d e f
hg i
带双亲的孩子链表
数据结构
tjm
a
b c
d e f
hg ia
b c
d e f
g h i
^
^
^
^ ^ ^
^ ^ ^ ^
孩子兄弟表示法（二叉树表示法）
实现：用二叉链表作树的存储
结构，链表中每个结点的两个
指针域分别指向其第一个孩子
结点和下一个兄弟结点。
数据结构
tjm
A
CB E
D
树
A
B
C
D E
二叉树
A ^
^ B C
^ D ^
^ E ^
A ^
^ B
C
^ D ^ ^ E ^
6.4.2 森林与二叉树的转换
A ^
^ B
C
^ D ^
^ E ^
数据结构
tjm
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树转换成的二叉树其右子树一定为空。
加线：在兄弟之间加一连线。
抹线：对每个结点，除了其左孩子外，抹掉其与
其余孩子之间的连线。
旋转：将树作适当的旋转即可。
将树转换成二叉树
数据结构
tjm
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
将 二叉 树转换成树
加线：若某 结点是双亲结点的左孩子，则将 该结点
的右孩子，右孩子的右孩子,…… 沿分支找到的所
有右孩子，都与 该结点 的双亲用线连起来。
抹线：抹掉原二叉树中双亲与右孩子之间的连线。
调整：将结点按层次排列，形成树结构。
数据结构
tjm
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
森林转换成二叉树
将各棵树分别转换成二叉树。
将每棵树的根结点用线相连。
以第一棵树根结点为二叉树的根，再以根结点为
轴心，顺时针旋转，构成二叉树型结构。
数据结构
tjm
A
B
C
D
E
F GH
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
二叉树转换成森林
抹线：将二叉树中根结点与其右孩子连线，及沿右
分支搜索到的所有右孩子间连线全部抹掉，使之变
成孤立的二叉树。
还原：将孤立的二叉树还原成树。
数据结构
tjm
6.4.3 树的遍历
（ 1） 树的先根遍历
树的后根遍历
（ 2） 森林的先序遍历
森林的中序遍历
若给定树的先根和后根序列则可唯一地确定一棵树。
数据结构
tjm
6.6 哈夫曼树及其应用
6.6.1 最优二叉树（哈夫曼树）
从树中一个结点到另一个结点之间的分支构成这
两个结点间的路径。
路径长度：路径上的分支数。
树的路径长度：从树根到每个结点的路径长度之
和。
结点的带权路径长度：从该结点到树根之间的路
径长度与结点上权的乘积。
数据结构
tjm
树的带权路径长度：树中所有叶子结点的
带权路径长度之和。记作：
结点到根的路径长度—
权值—其中：
k
k
n
k
kk
l
w
lww p l ?
?
?
1
设有 n个权值 {w1,w2,…… wn},构造一棵有 n个
叶子结点的二叉树，第 i个叶子的权值为 wi,则
wpl最小的二叉树叫 最优二叉树（哈夫曼树）,
即 带权路径长度最短的树 。
数据结构
tjm
例, 有 4个结点，权值分别为 7,5,2,4，构造有 4
个叶子结点的二叉树。
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 4WPL=7*1+5*2+2*3+4*3=35
?
?
? n
k
KK LWW P L
1
a b c d
7 5 2 4
WPL=7*2+5*2+2*2+4*2=36
数据结构
tjm
等级
分数段 比例
ABCDE
0~59 60~69 70~79 80~8990~1000.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
E A
D
B
C
a<80
a<70
a<60 a<90
E
Y
N
D
Y
NCY 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
比较 20500次
比较 22000次
比较 31500次
假设输入
10000个数
数据结构
tjm
Huffman树的 构造
构造 Huffman树步骤：
根据给定的 n个权值 {w1,w2,…… wn},构造 n棵只有
根结点的二叉树 。
在森林中选取两棵根结点权值最小的树作左右子
树，构造一棵新的二叉树，置新二叉树根结点权
值为其左右子树根结点权值之和。
在森林中删除这两棵树，同时将新得到的二叉树
加入森林中。
重复上述两步，直到只含一棵树为止，这棵树即
哈夫曼树。
数据结构
tjm
例：
a7 b5 c2 d4
a7 b5
c2 d4
6 a7
b5
c2 d4
11
a7
b5
c2 d4
18
a7
b5
c2 d4
数据结构
tjm
例,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
191429 23
87
15
11
35
1929 23
14
87
29
29
14
87
29
11
35
23
42
11
35
23
42
29
14
87
58
11
35
23 29
14
87
100
11
35
23 29
14
87
数据结构
tjm
lch weight rch parent
1
2
3
4
5
6
7
0
0
0
0
0
0
0
7
5
2
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
lch weight rch parent
1
2
3
4
5
6
7
0
0
0
0
3
0
0
7
5
2
4
6
0
0
0
0
0
0
4
0
0
0
0
5
5
0
0
0
i
s1=3,s2=4
一棵有 n个叶子结点的 Huffman树有 2n-1个结点，采用
顺序存储结构 —— 一维结构数组 。
Huffman算法实现：
算法 参见 P147算法 6.12。
例：
a7 b5 c2 d4
数据结构
tjm
lch weight rch parent
1
2
3
4
5
6
7
0
0
0
0
3
2
0
7
5
2
4
6
11
0
0
0
0
0
4
5
0
0
6
5
5
6
0
0
i
s1=2,s2=5
lch weight rch parent
1
2
3
4
5
6
7
0
0
0
0
3
2
1
7
5
2
4
6
11
18
0
0
0
0
4
5
6
7
6
5
5
6
7
0i
s1=1,s2=6
1
2
3
4
0
0
0
1
1
11
1 1
数据结构
tjm
例：要传输的字符集 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
6.6.2 哈夫曼编码
编码,根据字符出现频率构造 Huffman树，然后将
树中结点引向其左孩子的分支标, 0”,引向其右
孩子的分支标, 1” ；每个字符的编码即为从根到
每个叶子的路径上得到的 0,1序列。
如：电文是 {CAS;CAT;SAT;AT}
其编码是, 11010111011101000011111000011000”
数据结构
tjm
如, 电文为, 1101000”
译文只能是,CAT”
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
译码,从 Huffman树根开始，从待译码电文中逐位
取码。若编码是, 0”,则向左走；若编码是, 1”,
则向右走，一旦到达叶子结点，则译出一个字符；
再重新从根出发，直到电文结束。
第六章 (下 )
数据结构
tjm
静态双亲链表的类型定义参见 P135
6.4 树和森林
6.4.1 树的存储结构
双亲表示法
实现：定义数组存放树的结点，每个结点含两个域：
数据域：存放结点本身信息。
双亲域：指示本结点的双亲结点在数组中的位置。
特点：找双亲容易，找孩子难。
数据结构
tjm
a
b c
d e f
hg i
－ 1
0
1
1
2
4
4
4
0
a
c
d
e
f
g
h
i
b
data parent
5
0
1
2
3
4
6
7
8
数据结构
tjm
a
b c
d e f
hg i
1 2 ^
3 4 ^
86 7 ^
5 ^
5
0
1
2
3
4
6
7
8
a
c
d
e
f
g
h
i
b
^
^
^
^
^
data fc
孩子链表表示法 （ 类型定义参见 P136）
每个结点的孩子结点用单链表存储，再用含 n个
元素的数组指向每个孩子链表。
数据结构
tjm
5
0
1
2
3
4
6
7
8
a
c
d
e
f
g
h
i
b
data fc
1 2
3 4
86 7
5
^
^
^
^
^
^
^
^
^
－ 1
0
1
1
2
4
4
4
0
parent
a
b c
d e f
hg i
带双亲的孩子链表
数据结构
tjm
a
b c
d e f
hg ia
b c
d e f
g h i
^
^
^
^ ^ ^
^ ^ ^ ^
孩子兄弟表示法（二叉树表示法）
实现：用二叉链表作树的存储
结构，链表中每个结点的两个
指针域分别指向其第一个孩子
结点和下一个兄弟结点。
数据结构
tjm
A
CB E
D
树
A
B
C
D E
二叉树
A ^
^ B C
^ D ^
^ E ^
A ^
^ B
C
^ D ^ ^ E ^
6.4.2 森林与二叉树的转换
A ^
^ B
C
^ D ^
^ E ^
数据结构
tjm
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树转换成的二叉树其右子树一定为空。
加线：在兄弟之间加一连线。
抹线：对每个结点，除了其左孩子外，抹掉其与
其余孩子之间的连线。
旋转：将树作适当的旋转即可。
将树转换成二叉树
数据结构
tjm
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
将 二叉 树转换成树
加线：若某 结点是双亲结点的左孩子，则将 该结点
的右孩子，右孩子的右孩子,…… 沿分支找到的所
有右孩子，都与 该结点 的双亲用线连起来。
抹线：抹掉原二叉树中双亲与右孩子之间的连线。
调整：将结点按层次排列，形成树结构。
数据结构
tjm
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
森林转换成二叉树
将各棵树分别转换成二叉树。
将每棵树的根结点用线相连。
以第一棵树根结点为二叉树的根，再以根结点为
轴心，顺时针旋转，构成二叉树型结构。
数据结构
tjm
A
B
C
D
E
F GH
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
二叉树转换成森林
抹线：将二叉树中根结点与其右孩子连线，及沿右
分支搜索到的所有右孩子间连线全部抹掉，使之变
成孤立的二叉树。
还原：将孤立的二叉树还原成树。
数据结构
tjm
6.4.3 树的遍历
（ 1） 树的先根遍历
树的后根遍历
（ 2） 森林的先序遍历
森林的中序遍历
若给定树的先根和后根序列则可唯一地确定一棵树。
数据结构
tjm
6.6 哈夫曼树及其应用
6.6.1 最优二叉树（哈夫曼树）
从树中一个结点到另一个结点之间的分支构成这
两个结点间的路径。
路径长度：路径上的分支数。
树的路径长度：从树根到每个结点的路径长度之
和。
结点的带权路径长度：从该结点到树根之间的路
径长度与结点上权的乘积。
数据结构
tjm
树的带权路径长度：树中所有叶子结点的
带权路径长度之和。记作：
结点到根的路径长度—
权值—其中：
k
k
n
k
kk
l
w
lww p l ?
?
?
1
设有 n个权值 {w1,w2,…… wn},构造一棵有 n个
叶子结点的二叉树，第 i个叶子的权值为 wi,则
wpl最小的二叉树叫 最优二叉树（哈夫曼树）,
即 带权路径长度最短的树 。
数据结构
tjm
例, 有 4个结点，权值分别为 7,5,2,4，构造有 4
个叶子结点的二叉树。
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 4WPL=7*1+5*2+2*3+4*3=35
?
?
? n
k
KK LWW P L
1
a b c d
7 5 2 4
WPL=7*2+5*2+2*2+4*2=36
数据结构
tjm
等级
分数段 比例
ABCDE
0~59 60~69 70~79 80~8990~1000.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
E A
D
B
C
a<80
a<70
a<60 a<90
E
Y
N
D
Y
NCY 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
比较 20500次
比较 22000次
比较 31500次
假设输入
10000个数
数据结构
tjm
Huffman树的 构造
构造 Huffman树步骤：
根据给定的 n个权值 {w1,w2,…… wn},构造 n棵只有
根结点的二叉树 。
在森林中选取两棵根结点权值最小的树作左右子
树，构造一棵新的二叉树，置新二叉树根结点权
值为其左右子树根结点权值之和。
在森林中删除这两棵树，同时将新得到的二叉树
加入森林中。
重复上述两步，直到只含一棵树为止，这棵树即
哈夫曼树。
数据结构
tjm
例：
a7 b5 c2 d4
a7 b5
c2 d4
6 a7
b5
c2 d4
11
a7
b5
c2 d4
18
a7
b5
c2 d4
数据结构
tjm
例,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
191429 23
87
15
11
35
1929 23
14
87
29
29
14
87
29
11
35
23
42
11
35
23
42
29
14
87
58
11
35
23 29
14
87
100
11
35
23 29
14
87
数据结构
tjm
lch weight rch parent
1
2
3
4
5
6
7
0
0
0
0
0
0
0
7
5
2
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
lch weight rch parent
1
2
3
4
5
6
7
0
0
0
0
3
0
0
7
5
2
4
6
0
0
0
0
0
0
4
0
0
0
0
5
5
0
0
0
i
s1=3,s2=4
一棵有 n个叶子结点的 Huffman树有 2n-1个结点，采用
顺序存储结构 —— 一维结构数组 。
Huffman算法实现：
算法 参见 P147算法 6.12。
例：
a7 b5 c2 d4
数据结构
tjm
lch weight rch parent
1
2
3
4
5
6
7
0
0
0
0
3
2
0
7
5
2
4
6
11
0
0
0
0
0
4
5
0
0
6
5
5
6
0
0
i
s1=2,s2=5
lch weight rch parent
1
2
3
4
5
6
7
0
0
0
0
3
2
1
7
5
2
4
6
11
18
0
0
0
0
4
5
6
7
6
5
5
6
7
0i
s1=1,s2=6
1
2
3
4
0
0
0
1
1
11
1 1
数据结构
tjm
例：要传输的字符集 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
6.6.2 哈夫曼编码
编码,根据字符出现频率构造 Huffman树，然后将
树中结点引向其左孩子的分支标, 0”,引向其右
孩子的分支标, 1” ；每个字符的编码即为从根到
每个叶子的路径上得到的 0,1序列。
如：电文是 {CAS;CAT;SAT;AT}
其编码是, 11010111011101000011111000011000”
数据结构
tjm
如, 电文为, 1101000”
译文只能是,CAT”
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
译码,从 Huffman树根开始，从待译码电文中逐位
取码。若编码是, 0”,则向左走；若编码是, 1”,
则向右走，一旦到达叶子结点，则译出一个字符；
再重新从根出发，直到电文结束。
