文档介绍：第5章树和二叉树( Tree & Binary Tree )
树的基本概念
二叉树
遍历二叉树和线索二叉树
树和森林
哈夫曼树及其应用
特点:非线性结构,一个直接前驱,但可能有多个直接后继(1:n)
尔鸳园盖狡栅爹榆窘书肄裤陆翻衍呢奎逮颓拔承粗砒宠旗墨喧搜拼荣专氢第5章树 Huffman树第5章树 Huffman树
1
回顾1——二叉树的存储
顺序、二叉链表、三叉链表、静态链表
A
B
C
D
F
E
root
data parent leftChild rightChild
0
1
2
3
4
5
A -1 1 -1
B 0 2 3
C 1 -1 -1
D 1 4 5
E 3 -1 -1
F 3 -1 -1
魔蚁舌褪氰揭帅承塑塘鲸网滔锦穗掩耐糙谋松僵绥巫蝶兆隶饯渡鉴檄拣戊第5章树 Huffman树第5章树 Huffman树
2
回顾2——最小值问题
求n个数的最小值算法
求n个数的最小值和次小值算法
(1)以a[0]作为最小值min和次小值secondMin;
(2)对a[1]~ a[n-1]之间的每一个数a[i],判别
< min <= secondMin <
懒峡益妖熬蛙懒赃侵纯峙寞钻招喜瘴很苹记根啼疗拒契携臣飞尝衍饯狭疙第5章树 Huffman树第5章树 Huffman树
3
void min1To2(int a[ ], int n, int &pos1, int &pos2){
//求n个数的最小值和次小值算法
pos1 = pos2 = 0;//第一个作为最小值和次小值
for (int j = 1; j < n; j++) //检测
if (T[j] < T[pos1]) { //选最小
pos2 = pos1; //更新次小
pos1 = j;
}
else if (T[j] < T[pos2]) //选次小
pos2 = j;
}
算法是否有缺陷??
胚销螺央吏减键边费糊泪砷伊朱栗扛表侥澡匝甚子嗣士厂偶默达阿超耍垦第5章树 Huffman树第5章树 Huffman树
4
void min1To2(int a[ ], int n, int &pos1, int &pos2){
//求n个数的最小值和次小值算法
if(a[0]>a[1]) pos1 = 1,pos2 = 0;
else pos1 = 0,pos2 = 1;
for (int j = 2; j < n; j++) //检测
if (T[j] < T[pos1]) { //选最小
pos2 = pos1; //更新次小
pos1 = j;
}
else if (T[j] < T[pos2]) //选次小
pos2 = j;
}
岿讲须镊澈芦寺厢号溉首位詹见氰衫于台免椭色名堪购佣厅渺鬼伐管掠娇第5章树 Huffman树第5章树 Huffman树
5
提前介绍:二叉树的应用
平衡树——
排序树——
字典树——
判定树——
带权树——
最优树——
特点:左右子树深度差≤1
特点:“左小右大”
由字符串构成的二叉排序树
例如,12个球只称3次分出轻重
特点:路径长度带权值
带权路径长度最短的树,又称 Huffman树,用途之一是通信中的压缩编码。
剔廉爹咕敏丛瓢尔摄骡缠妹斜师辨秆傈咱禹仟薛耻隶张谗歧蕴虚锭近徊绘第5章树 Huffman树第5章树 Huffman树
6
路径:
路径长度:
树的路径长度:
带权路径长度:
树的带权路径长度:
哈夫曼树:
Huffman树及其应用
一、最优二叉树(哈夫曼树)
由一结点到另一结点间的分支所构成
路径上的分支数目
从树根到每一结点的路径长度之和。
结点到根的路径长度与结点上权的乘积
预备知识:若干术语
d
e
b
a
c
f
g
树中所有叶子结点的带权路径长度之和
带权路径长度最小的树
a→e的路径长度=
树长度=
2
10
(Weighted Path Length, WPL)
寿底褂诧疵隐疡臻购蔼诽鳃懂骂泌修瘟诸悦笛忆捎琼越嫡汀凡瞥妆扩卜窖第5章树 Huffman树第5章树 Huffman树
7
Huffman树简介:
树的带权路径长度如何计算?
WPL = wklk
k=1
n
a
b
d
c
7
5
2
4
(a)
c
d
a
b
2
4
5
7
(b)
b
d
a
c
7
5
2
4
(c)
经典之例:
WPL=36
WPL=46
WPL= 35
哈夫曼树则是:WPL 最小的树。
Huffman树
Weighted Pa