Download presentation
Presentation is loading. Please wait.
1
Chapter 5 Tree & Binary Tree
2
树的类型定义 n(n≥0)个元素的有限集合
3
树的类型定义 数据对象 D： D是具有相同特性的数据元素的集合。 否则: (1) 在D中存在唯一的称为根的数据元素root；
(2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1, T2, …, Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。
4
基本操作： 查 找 类 插 入 类 删 除 类
5
查找类： Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点
Root(T) // 求树的根结点 Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历
6
插入类： InitTree(&T) // 初始化置空树 CreateTree(&T, definition) // 按定义构造树
Assign(T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树
7
删除类： DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树
ClearTree(&T) // 将树清空 DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树
8
基 本 术 语
9
结点 结点的度 树的度 叶子结点 分支结点 数据元素+若干指向子树的分支 分支的个数 树中所有结点的度的最大值 度为零的结点 度大于零的结点
D 分支结点 度大于零的结点 H I J M
10
孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点 (从根到结点的)路径 由从根到该结点所经分支和结点构成 A B C D E F
G H I J K L M 孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点
11
结点的层次 树的深度 假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1 树中叶子结点所在的最大 层次 A B C D E F
G H I J K L M 结点的层次 假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1 树的深度 树中叶子结点所在的最大 层次
12
森林 Tree = （root，F） 是m（m≥0）棵互 不相交的树的集合 任何一棵非空树是一个二元组 其中 root 被称为根结点
A 是m（m≥0）棵互 不相交的树的集合 B C D E F G H I J K L M 任何一棵非空树是一个二元组 Tree = （root，F） 其中 root 被称为根结点 F 被称为子树森林
13
有向树 (１) 有确定的根 (２) 树根和子树根之间为有向关系 有序树 子树之间存在确定的次序关系 无序树 子树之间不存在确定的次序关系
14
对比树型结构和线性结构的结构特点
15
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
线性结构 树型结构 第一个数据元素 (无前驱) 根结点 (无前驱) 最后一个数据元素 (无后继) 多个叶子结点 (无后继) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 其它数据元素 (一个前驱、 一个后继) 其它数据元素 (一个前驱、 多个后继)
16
二叉树的类型定义
17
二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成
A B E C F G D 左子树 H K
18
二叉树的五种基本形态 空树 只含根结点 左右子树均不为空树 N 右子树为空树 左子树为空树 N N N L R L R
19
二叉树的主要基本操作 查 找 类 插 入 类 删 除 类
20
Root(T) Value(T, e) Parent(T, e)
LeftChild(T, e) RightChild(T, e) LeftSibling(T, e) RightSibling(T, e) BiTreeEmpty(T) BiTreeDepth(T)
21
PreOrderTraverse(T, Visit())
InOrderTraverse(T, Visit()) PostOrderTraverse(T, Visit()) LevelOrderTraverse(T, Visit())
22
CreateBiTree(&T, definition) InsertChild(T, p, LR, c)
InitBiTree(&T) Assign(T, &e, value) CreateBiTree(&T, definition) InsertChild(T, p, LR, c)
23
ClearBiTree(&T) DestroyBiTree(&T) DeleteChild(T, p, LR)
24
二叉树 的重要特性
25
用归纳法证明： 归纳基： i = 1 层时，只有一个根结点： 归纳假设： 2i-1 = 20 = 1； 归纳证明：
性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1) 用归纳法证明： 归纳基： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点： 2i-1 = 20 = 1； 假设对所有的 j，1≤ j i，命题成立； 二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 ≤ 2i-2 2 = 2i-1 。
26
性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）。
证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 +2k-1 = 2k-1 。
27
证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2
而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。
28
两类特殊的二叉树： 满二叉树：指的是深度为k且含有2k-1个结点的二叉树。
3 4 5 6 7 8 9 10 11 12 13 14 15 完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。 a b c d e f g h i j
29
具有 n 个结点的完全二叉树的深度为 log2n +1 。
性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。 证明： 设完全二叉树的深度为 k 则根据第二条性质得 2k-1≤ n < 2k 即 k-1 ≤ log2 n < k 因为 k 只能是整数，因此， k =log2n + 1 。
30
性质 5 ： 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点； (2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。
31
二叉树的存储结构 一、二叉树的顺 序存储表示 二、二叉树的链 式存储表示
32
顺序存储表示 完全二叉树的 一般二叉树的 数组表示 数组表示
33
A 2 1 B D 6 4 E C 13 F A B D C E F
34
由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况
35
二叉链表 root 结点结构 lchild data rchild A B D C E F
36
链表表示
38
三叉链表 结点结构 root parent lchild data rchild A B D C E F
39
二叉链表的静态结构
40
(Binary Tree Traversal)
二叉树遍历 (Binary Tree Traversal)
41
问题的提出 顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次 “访问”的含义可以很广，如：输出结
点的信息等
42
“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题
43
对“二叉树”而言，可以有三条搜索路径 1．先上后下的按层次遍历 2．先左（子树）后右（子树）的遍历 3．先右（子树）后左（子树）的遍历
44
设 访问根结点 记作 V 遍历根的左子树 记作 L 遍历根的右子树 记作 R 则可能的遍历次序有 前序 VLR 逆前序 VRL 中序 LVR 逆中序 RVL 后序 LRV 逆后序 RLV 层次遍历
45
前序遍历 (Preorder Traversal)
若二叉树为空，则空操作 否则 访问根结点(V) 前序遍历左子树(L) 前序遍历右子树(R) 遍历结果 a * b - c d / e f
46
中序遍历 (Inorder Traversal)
若二叉树为空，则空操作 否则 中序遍历左子树(L) 访问根结点(V) 中序遍历右子树(R) 遍历结果 a + b * c - d - e / f 表达式语法树
47
后序遍历 (Postorder Traversal)
若二叉树为空，则空操作 否则 后序遍历左子树(L) 后序遍历右子树(R) 访问根结点(V) 遍历结果 a b c d - * + e f / -
48
层次遍历(Levelorder Traversal)
从上到下，从左到右 遍历结果 ＋／a* e f b -cd
49
按给定的表达式建相应二叉树 由前缀表达式建树 例如: -×+abc/de 由中缀表达式建树 例如：(a+b)×c–d/e 由后缀表达式建树
50
对应前缀表达式 ×+abc/de 的二叉树 - × / + c d e 特点： 操作数为叶子结点 运算符为分支结点 a b
51
对应中缀表达式 (a+b)×c-d/e 的二叉树 - × / + c d e 特点： 操作数为叶子结点 运算符为分支结点 a b
52
对应后缀表达式 ab+c×de/- 的二叉树 - × / + c d e 特点： 操作数为叶子结点 运算符为分支结点 a b
53
+ + + / + 分析表达式和二叉树的关系 a+b (a+b)×c × c a b b a a+b×c (a+b)×c – d/e - ×
54
由遍历序历生成二叉树 由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树 由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树
由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树 由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树 由二叉树的前序序列和后序序列不可唯一地确定一棵二叉树
55
仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，
由二叉树的先序和中序序列建树 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列 根 左子树 右子树 二叉树的中序序列 左子树 根 右子树
56
a a b c d e f g a b c d e f g c c b d a e g f b d e g f 先序序列 中序序列 ^ ^
57
前序序列{ABHFDECKG} 中序序列{HBDFAEKCG}
58
二叉树的计数 问题是有n个数据值，可能构造多少种不同的二叉树？ 我们可以固定前序排列，选择所有可能的中序排列
59
二叉树的计数 有0个, 1个, 2个, 3个结点的不同二叉树如下
60
计算具有n个结点的不同二叉树的棵数 Catalan函数 具有4个结点的不同二叉树
61
树的存储结构 一、双亲表示法 二、孩子表示法 三、孩子兄弟表示法
62
双亲表示法 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 A D B C E F G
data parent 0 A 1 B 2 C 3 D 4 E 5 F 6 G 5 A D B C E F G
63
孩子链表表示法 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 -1 2 4 A B C D E F
data firstchild 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 -1 2 4 A B C D E F 6 G
64
孩子兄弟表示法 root A B C E D F G A B C D A B C E D F G E F G
65
孩子兄弟表示法 data firstChild nextSibling
66
6.4 树和森林 树的存储结构 双亲表示法 typedef struct node { datatype data; int parent;
实现：定义结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难 typedef struct node { datatype data; int parent; }JD; JD t[M];
67
0号单元不用或 存结点个数 a b c d e f h g i 6 1 2 3 4 5 7 8 9 data parent 9 a c d e f g h i b 1 1 2 2 3 5 5 如何找孩子结点 5
68
空环域个数为n(k-1)+1,其中k为树的度。
孩子表示法 多重链表：每个结点有多个指针域，分别指向其子树的根 结点同构：结点的指针个数相等，为树的度D 结点不同构：结点指针个数不等，为该结点的度d 空环域个数为n(k-1)+1,其中k为树的度。 data child1 child2 ………. childD data degree child1 child2 ………. childd 孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表 孩子结点：typedef struct node { int child; //该结点在表头数组中下标 struct node *next; //指向下一孩子结点 }JD; 表头结点：typedef struct tnode { datatype data; //数据域 struct node *fc; //指向第一个孩子结点 }TD; TD t[M]; //t[0]不用
69
a b c d e f h g 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 ^ 6 ^ ^ 9 7 8 ^ ^ ^ ^ 如何找双亲结点 ^
70
带双亲的孩子链表 6 1 2 3 4 5 7 8 9 a c d e f g h i b data fc ^ parent a b c d e f h g i
71
孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 特点
操作容易 破坏了树的层次 typedef struct node { datatype data; struct node *fch, *nsib; }JD; a b c d e f h g i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
72
森林与二叉树 的转换
73
森林由三部分构成 B C D 1．森林中第一棵树的根结点 E F G H I J K 2．森林中第一棵树的子树森林
3．森林中其它树构成的森林
74
森林转化成二叉树 的规则
75
若F为空，即n = 0，则 对应的二叉树B为空二叉树 若F不空，则 对应二叉树B的根root(B)是F中第 一棵树T1的根root(T1)，其左子树为 B(T11, T12, …, T1m)，其中，T11, T12, …, T1m是root(T1)的子树；其右子 树为B(T2, T3, …, Tn)，其中，T2, T3, …, Tn是除T1外其它树构成的森林
76
二叉树转换为森林 的规则
77
如果B为空，则对应的森林F也为空 如果B非空，则 F中第一棵树T1的根为root；T1的根 的子树森林(T11, T12, …, T1m ) 是由 root的左子树LB转换而来，F 除了T1 之外其余的树组成的森林(T2, T3, …, Tn )是由root的右子树RB转换而成的 森林
78
森林与二叉树的转换
79
树 的 遍 历 深度优先遍历 树的先根次序遍历 树的后根次序遍历 广度优先遍历 树的层次次序遍历
80
森林的先根遍历 若森林F为空, 返回 否则: 访问F的第一棵树的根结点 先根次序遍历第一棵树的子树森林 先根次序遍历其它树组成的森林
81
森林的后根遍历 若森林F为空，返回 否则: 后根次序遍历第一棵树的子树森林 后根次序遍历其它树组成的森林 访问F的第一棵树的根结点
82
森林的层次遍历 若森林F为空，返回 否则: 依次遍历各棵树的根结点 依次遍历各棵树根结点的所有子女 依次遍历这些子女结点的子女结点
83
先根遍历 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
84
二叉树的类定义
85
template <class Type>
class BinTreeNode { private: BinTreeNode<Type> *LChild,*RChild; Type data; }; class BinaryTree { BinTreeNode<Type> *root;
86
二叉树前序遍历递归算法 template <class Type>
void BinaryTree<Type>:: PreOrder(BinTreeNode<Type>*current) { if ( current != NULL ) { cout << current→data; PreOrder ( current→LChild ); PreOrder ( current→RChild ); } }
87
二叉树中序遍历递归算法 template <class Type> void BinaryTree <Type>::
InOrder(BinTreeNode<Type>*current) { if ( current != NULL ) { InOrder ( current→LChild ); cout << current→data; InOrder ( current→RChild ); } }
88
二叉树后序遍历递归算法 template <class Type> void BinaryTree<Type>::
PostOrder(BinTreeNode<Type>*current) { if ( current != NULL ) { PostOrder ( current→LChild ); PostOrder ( current→RChild ); cout << current→data; } }
89
二叉树前序遍历 非递归算法
90
template <class Type>
void BinaryTree<Type>:: PreOrder(BinTreeNode<Type> *p ) { do { while ( p != NULL ) { cout << p->data; Push ( s, p ); p = p->LChild; } if ( !Empty ( s ) ) { p = pop ( s ); p = p->RChild; } }while ( ( !Empty ( s ) ) || ( p != NULL ) ) }
91
二叉树中序遍历 非递归算法
92
template <class Type>
void BinaryTree<Type>:: PreOrder(BinTreeNode<Type> *p ) { do { while ( p != NULL ) { Push ( s, p ); p = p->LChild; } if ( !Empty ( s ) ) { p = pop ( s ); cout << p->data; p = p->RChild; } }while ( ( !Empty ( s ) ) || ( p != NULL ) ) }
93
应用二叉树遍历的事例
94
利用二叉树遍历计算二叉树结点个数 template <class Type> void BinaryTree<Type>:: Size( BinTreeNode<Type> *current ) { if ( current != NULL ) return Size ( current→LChild )+ Size ( current→RChild )+1; else return 0; }
95
计算二叉树的高度 template <class Type> int BinaryTree<Type>:: Depth ( BinTreeNode <Type> *t ) { if ( t == NULL ) return 0; else return 1+ Max( Depth( t→LChild ), Depth( t→RChild ) ); }
103
线索二叉树
104
遍历二叉树的结果是， 求得结点的一个线性序列 A 先序序列 B A B C D E F G H K E F C 中序序列
B D C A H G K F E G D 后序序列 D C B H K G F E A H K
105
包含 “线索” 的存储结构，称作 “线索链表”
指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索” A B C D E F G H K 包含 “线索” 的存储结构，称作 “线索链表” ^ B E ^ 与其相应的二叉树， 称作 “线索二叉树” C ^ ^ D ^
106
对线索链表中结点的约定 在二叉链表的结点中增加两个标志域 LTag和RTag,并作如下规定: 若该结点的左子树不空，
则LChild域的指针指向其左孩子， 且左标志LTag的值为0 否则，LChild域的指针指向其“前驱”， 且左标志LTag的值为1
107
若该结点的右子树不空， 则RChild域的指针指向其右孩子， 且右标志RTag的值为0 否则，RChild域的指针指向其“后继”， 且右标志RTag的值为1 如此定义的二叉树的存储结构称作“线索链表”
108
LTag = 0, LChild为指针,指向左孩子 LTag = 1, LChild为线索,指向前驱 RTag = 0, RChild为指针,指向右孩子 RTag = 1, RChild为线索,指向后继
109
猜一猜,是哪一种线索二叉树
110
前序序列 A B D C E 后序序列 D B E C A
111
带表头结点的中序线索二叉树
112
寻找当前结点 在中序下的后继
113
if (pRTag==1) if (pRChild!=T.root) 后继为 pRChild else 无后继
else //pRTag==0 后继为当前结点右 子树的中序下的第 一个结点 else 出错情况 A B C D E F G H I J K L
114
寻找当前结点 在中序下的前趋
115
if (pLTag==1) if (pLChild!=T.root) 前驱为pLChild else 无前驱
else //pLTag==0 前驱为当前结点左 子树的中序下的最 后一个结点 else 出错情况 A B C D F E H I G K J L
116
哈 夫 曼 树 (Huffman Tree) 与 哈 夫 曼 编 码
117
结点间路径长度(Path Length) 连接两结点的路径上的分支数 结点的路径长度 从根结点到该结点的路径上分 支的数目
118
树的路径长度 树中每个结点的路径长度之和 树的带权路径长度 (Weighted Path Length,WPL) 树的各叶结点所带的权值与该 结点到根的路径长度的乘积的 和
119
在所有含n个叶子结点、并带相同 权值的m叉树中，必存在一棵其带权路 径长度取最小值的树，称为“最优树”, 或“哈夫曼树” (Huffman Tree)
120
具有不同带权路径长度的二叉树 哈夫曼树中，权值大的结点离根最近
121
WPL(T)= 72+52+23+43+92 =60 WPL(T)= 74+94+53+42+21 =89 2 4 7
WPL(T)= 72+52+23+43+9 =60 WPL(T)= 74+94+53+42+2 =89
122
构造哈夫曼树 (以二叉树为例)
123
根据给定的 n 个权值 {w1, w2, …, wn}，造 n 棵二叉树的集合 F = {T1, T2, … , Tn}， 其中每棵二叉树中均只含一个带权 值为 wi 的根结点，其左、右子树为 空树； (1)
124
在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和； (2)
125
从F中删去这两棵树，同时加入 刚生成的新树 (3) 重复 (2) 和 (3) 两步，直至 F 中只 含一棵树为止 (4)
126
已知权值 W={ 5, 6, 2, 9, 7 } 5 6 2 9 7 6 9 7 7 5 2 9 7 13 5 2 7 6
127
9 7 13 5 2 7 6 29 1 13 16 1 1 7 9 6 7 1 00 01 10 5 2 110 111
128
前缀编码 任何一个字符的编码都不是同一 字符集中另一个字符的编码的前缀 利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短
129
设给出一段报文 CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 } 若给每个字符以等长编码 A : 00 T : C : S : 11 则总编码长度为 ( ) * 2 = 36
130
以各字符出现概率{2,7,4,5}为各叶结点权值，建立哈夫曼树，得哈夫曼编码(不等长编码) A:0 T:10 C:110 S:111
总编码长度为 7*1+5*2+(2+4)*3=35 总编码长度正好等 于哈夫曼树的带 权路径长度WPL
131
哈夫曼算法 const unsigned int n=256; //字符数
const unsigned int m=256*2-1; //结点总数 struct HTNode{ //压缩用Huffman树结点 unsigned long weight; //字符频度（权值） unsigned int parent,lchild,rchild; }; struct Buffer{ //字节缓冲压缩用Huffman树 char ch; //字节 unsigned int bits; //实际比特数
132
哈夫曼算法(class HuffmanTree(1))
class HuffmanTree{ //Huffman树 public: void Code(); //编码 void UnCode(); //译码 private: HTNode HT[m+1]; //树结点表(HT[1]到HT[m]) char Leaf[n+1]; //叶结点对应字符(leaf[1]到leaf[n]) //叶结点对应编码(*HuffmanCode[1]到*HuffmanCode[n]) char *HuffmanCode[n+1]; unsigned int count; //频度大于零的字符数 //字符对应在树结点表的下标(char_index[0]到char_index[n-1]) unsigned int char_index[n]; unsigned long size; //被压缩文件长度 FILE *infp,*outfp; //输入/出文件 Buffer buf; //字符缓冲
133
哈夫曼算法(class HuffmanTree(2))
void Stat();//统计字符出现频度并过滤掉频度为零的字符 //在HT[0]~HT[k]中选择parent为-1，树值最小的两个结点s1,s2 void Select(unsigned int k, unsigned int &s1, unsigned int &s2); void Write(unsigned int bit); //向outfh中写入一个比特 void Write(unsigned int num,unsigned int k);//向outfh中写入k个比特 void WriteToOutfp(); //强行写入outfh void Read(unsigned int &bit); //从infh中读出一个比特 void Read(unsigned int &num,unsigned int k);//从infh中读出k个比特 //0~num-1之间的整数用二进位表示所需的位数 int NToBits(unsigned int num); //由编码文件中存储的树结构建立Huffman树 unsigned int CharToInt(char ch); //将字符转化为整型数 void CreateFromCodeFile(); //由被压缩文件建立Huffman树,将树结构存入编码文件的文件头部 // 中,并求每个字符的Huffman编码 void CreateFromSourceFile(); };
134
哈夫曼算法(CreateFromSourceFile()(1))
void HuffmanTree::CreateFromSourceFile() //由被压缩文件建立Huffman树,将树结构存入编码文件的文件头部中 //并求每个字符的Huffman编码 { Stat();//统计字符出现频度并过滤掉频度为零的字符 //由被压缩文件建立Huffman树 unsigned int i,s1,s2; for(i=1;i<=n;i++)HT[i].parent=HT[i].lchild=HT[i].rchild=0; for(i=count+1;i<=2*count-1;i++){//建立Huffman树 Select(i-1,s1,s2); //选择parent为0，权值最小的两个结点s1,s2 HT[s1].parent=HT[s2].parent=i; HT[i].parent=0;HT[i].lchild=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; }
135
哈夫曼算法(CreateFromSourceFile()(2))
//将树结构存入编码文件的文件头部中 unsigned int l; buf.bits=0; //清空缓冲区 buf.ch=0; rewind(outfp); fwrite(&size,sizeof(unsigned int),1,outfp); Write(count-1,8); for(i=1;i<=count;i++) fwrite(&Leaf[i],sizeof(char),1,outfp); l=NToBits(2*count-1); for(i=count+1;i<=2*count-1;i++){ Write(HT[i].lchild,l); Write(HT[i].rchild,l); }
136
哈夫曼算法(CreateFromSourceFile()(3))
//求每个字符的Huffman编码 unsigned int start,c,f,tem; char *cd; //编码临时变量 for(i=1;i<=n;i++) if(HuffmanCode[i]!=NULL){ delete []HuffmanCode[i]; //释放存储空间 HuffmanCode[i]=NULL; } cd=new char[count]; //分配求编码的工作空间 cd[count-1]='\0'; //编码结束符 for(i=1;i<=count;i++){ //逐位求Huffman编码 start=count-1; //编码结束符位置 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[c].parent) //从叶到根求编码 if(HT[f].lchild==c)cd[--start]='0'; else cd[--start]='1'; HuffmanCode[i]=new char[count-start]; //为第i个字符编码分配空间 strcpy(HuffmanCode[i],&cd[start]); //从cd复制编码到HuffmanCode delete []cd;
137
哈夫曼算法 void HuffmanTree::Code(){ //求字符的编码 //增加打开输入/出文件 char ch;
unsigned int i,c; for(i=0;i<=n;i++)HuffmanCode[i]=NULL; CreateFromSourceFile(); rewind(infp); ch=fgetc(infp); while(feof(infp)==0){ c=char_index[CharToInt(ch)]; for(i=0;i<strlen(HuffmanCode[c]);i++){ if(HuffmanCode[c][i]=='0')Write(0); else Write(1); } WriteToOutfp(); fclose(infp);fclose(outfp);
138
哈夫曼算法 fclose(infp);fclose(outfp); void HuffmanTree::UnCode(){ //译码,
//增加打开输入/出文 unsigned int bit,c,i; CreateFromCodeFile(); //建立Huffman树 Read(bit); for(i=0;i<size;i++){ c=2*count-1; //2*count-1为根结点的下标 while((HT[c].lchild!=0||HT[c].rchild!=0)&&feof(infp)==0){ if(bit==0)c=HT[c].lchild; else c=HT[c].rchild; } fputc(Leaf[c],outfp); //将字符写入outfp中 fclose(infp);fclose(outfp);
139
哈夫曼树推广（m叉哈夫曼树） 定理 对于度数只为m或0的正则m叉树，叶结点个数n0与度为m的结点数nm这间存在关系:
如n0=(m-1)*nm+1成立，则仿照一般的二叉哈夫曼树进行构造（只每次选出m棵根结点权值最小的m叉树合并为一棵新的m叉树） 如n0=(m-1)*nm+1不成立，则可添加若干个权为0的叶结点使其成立，然后再仿照一般的二叉哈夫曼树进行构造(在画m叉树时权为0的结点可不画出)
Similar presentations
