数据结构与算法分析第5讲 树与二叉树

1、四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 Chapter 5 Tree / 0号单元存储根结点 SqBiTree bt; 二叉树的顺序存储表示二叉树的顺序存储表示 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 完全二叉树的完全二叉树的 一般二叉树的一般二叉树的 数组表示数组表示 数组表示数组表示 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 A B C D E F A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1 4 0 13 2 6 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 单支树单支树 四川大学四川大学 计算

2、机学院计算机学院 游洪跃游洪跃 A D E B C F root lchild data rchild 结点结构结点结构 二叉链表二叉链表 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree; lchild data rchild 结点结构结点结构: C 语言的类型描述如下语言的类型描述如下: : 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学

3、院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 A D E B C F root 三叉链表三叉链表 parent lchild data rchild 结点结构结点结构 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 typedef struct TriTNode / 结点结构结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree; parent lchild data rchild

4、结点结构结点结构: C 语言的类型描述如下语言的类型描述如下: : 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 二叉链表的静态结构二叉链表的静态结构 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 顺着某一条搜索路径顺着某一条搜索路径巡访巡访二叉树二叉树 中的结点，使得每个结点中的结点，使得每个结点均被访问一均被访问一 次次，而且，而且仅被访问一次仅被访问一次 问题的提出问题的提出 “访问访问”的含义可以很广，如：输出结的含义可以很广，如：输出结 点的信息等点的信息等 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 “

5、遍历遍历”是任何类型均有的操作，是任何类型均有的操作， 对线性结构而言，只有一条搜索路对线性结构而言，只有一条搜索路 径径( (因为每个结点均只有一个后继因为每个结点均只有一个后继) )， 故不需要另加讨论。而二叉树是非故不需要另加讨论。而二叉树是非 线性结构，每个结点有两个后继，线性结构，每个结点有两个后继， 则存在如何遍历即按什么样的则存在如何遍历即按什么样的搜索搜索 路径路径遍历的问题遍历的问题 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 对对“二叉树二叉树”而言，可以有三而言，可以有三 条搜索路径条搜索路径 1先上后下先上后下的按层次遍历的按层次遍历 2先左先左（子树）（子树

6、）后右后右（子树）的遍历（子树）的遍历 3先右先右（子树）（子树）后左后左（子树）的遍历（子树）的遍历 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 设设 访问根结点访问根结点 记作记作 V 遍历根的左子树遍历根的左子树 记作记作 L 遍历根的右子树遍历根的右子树 记作记作 R 则可能的遍历次序有则可能的遍历次序有 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 对应

7、中缀表达式对应中缀表达式 ( (a+ +b) )c- -d/ /e 的二叉树的二叉树 a b cde - - + / 特点特点： 操作数操作数为叶子结点为叶子结点 运算符运算符为分支结点为分支结点 按给定的中缀表达式建相应二叉树按给定的中缀表达式建相应二叉树 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 a+b (a+b)c d/e d/e a+bc 分析表达式和二叉树的关系分析表达式和二叉树的关系 ab + a bc + a b c + (a+b)c ab cde - - + / 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪

8、跃 仅知二叉树的先序序列仅知二叉树的先序序列“abcdefg” 不不 能唯一确定一棵二叉树，能唯一确定一棵二叉树， 由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列如果同时已知二叉树的中序序列 “cbdaegf”，则会如何？，则会如何？ 二叉树的先序序列二叉树的先序序列 二叉树的中序序列二叉树的中序序列左子树左子树 左子树左子树 右子树右子树 右子树右子树 根根 根根 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 a b c d e f g c b d a e g f a a b b c c d d e e f f g g a b cd e f g

9、 先序序列先序序列 中序序列中序序列 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 ! )!2( 1 1 1 1 2 nn n nn b C n n n 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 树的存储结构树的存储结构 一、双亲表示法一、双亲表示法 二、孩子表示法二、孩子表示法 三、孩子兄弟表示法三、孩子兄弟表示法 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 A BC D EF G 0 A -1 1 B

10、 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 data parent 双亲表示法双亲表示法 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 A BCD EF G 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 data firstchild 1 2 3 4 5 6 孩子链表表示法孩子链表表示法 -1 0 0 0 2 2 4 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 A BCD EF G A B C E D F G root A B C E D F G 孩子兄弟表示法孩子兄弟表示法 四川大学四川大学 计算机学院计算机学院

11、 游洪跃游洪跃 data firstChildnextSibling 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 树和森林树和森林 树的存储结构树的存储结构 双亲表示法双亲表示法 实现：定义结构数组存放树的结点，每个结点含两个域：实现：定义结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难特点：找双亲容易，找孩子难 typedef struct node datatype data; int parent; JD; JD tM; 四川大

12、学四川大学 计算机学院计算机学院 游洪跃游洪跃 a bc def hgi a c d e f g h i b 0 1 2 2 3 5 5 5 1 09 6 0 1 2 3 4 5 7 8 9 dataparent 0号单元不用或 存结点个数 如何找孩子结点 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 孩子表示法孩子表示法 多重链表：每个结点有多个指针域，分别指向其子树的根多重链表：每个结点有多个指针域，分别指向其子树的根 结点同构：结点的指针个数相等，为树的度结点同构：结点的指针个数相等，为树的度D 结点不同构：结点指针个数不等，为该结点的度结点不同构：结点指针个数不等，为该结点的度

13、d 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 tM; /t0不用 四川大学四川大学 计算机学院计算机学院

14、 游洪跃游洪跃 a bc def hgi 6 0 1 2 3 4 5 7 8 9 a c d e f g h i b datafc 2 3 4 5 9 7 8 6 如何找双亲结点 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 带双亲的孩子链表 6 1 2 3 4 5 7 8 9 a c d e f g h i b datafc 2 3 4 5 9 7 8 6 0 1 2 2 3 5 5 5 1 parent a bc def hgi 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 孩子兄弟表示法（二叉树表示法）孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中

15、每个结点的两个实现：用二叉链表作树的存储结构，链表中每个结点的两个 指针域分别指向其第一个孩子结点和下一个兄弟结点指针域分别指向其第一个孩子结点和下一个兄弟结点 特点特点 操作容易操作容易 破坏了树的层次破坏了树的层次 typedef struct node datatype data; struct node *fch, *nsib; JD; a bc def hgi a b c d e f g h i 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 B C D E F G H I J K 1森林中第一棵森林中第一棵 树的根结点树的

16、根结点 2森林中第一棵森林中第一棵 树的子树森林树的子树森林 3森林中其它树森林中其它树 构成的森林构成的森林 森林由三部分构成森林由三部分构成 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算

17、机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 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 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 算法的递归描述算法的递归描述 void Preorder (BiTree T, void( *visit)(TElemType / 访问结点 Preorder(T-lchi

18、ld, visit); / 遍历左子树 Preorder(T-rchild, visit);/ 遍历右子树 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 中序遍历算法的非递归描述中序遍历算法的非递归描述 BiTNode *GoFarLeft(BiTree T, Stack *S) if (!T ) return NULL; while (T-lchild ) Push(S, T); T = T-lchild; return T; 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 void Inorder_I(BiTree T, void (*visit) (TelemType t

19、= GoFarLeft(T, S); / 找到最左下的结点 while(t) visit(t-data); if (t-rchild) t = GoFarLeft(t-rchild, S); else if ( !StackEmpty(S ) / 栈不空时退栈 t = Pop(S); else t = NULL; / 栈空表明遍历结束 / while / Inorder_I 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 遍历算法的应用举例遍历算法的应用举例 1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 (先序遍历先序遍历) 2、求二叉树的深度、求二叉树的深度(后序遍历后序

20、遍历) 3、复制二叉树、复制二叉树(后序遍历后序遍历) 4 4、建立二叉树的存储结构、建立二叉树的存储结构 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 算法基本思想算法基本思想: : 先序(或中序或后序)遍历二叉树，在 遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数” 的参数，的参数，并将算法中“访问结点”的操 作改为：若是叶子，则计数器增若是叶子，则计数器增1 1。 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 void CountLeaf (BiTree T, in

21、t / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 求二叉树的深度求二叉树的深度(后序遍历后序遍历) 算法基本思想算法基本思想: : 从二叉树深度的定义可知，二叉树的二叉树的 深度应为其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。 由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度， 算法中“访问结点”的操作为：求得左、求得左、 右子树深度的最大值，然后加右子树深度的最大值，然后加 1

22、 1 。 首先分析二叉树的深度二叉树的深度和它的左左、右子右子 树深度树深度之间的关系。 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval; 四川大学四川大学 计算机学院计算机学院 游洪跃

23、游洪跃 复制二叉树复制二叉树 其基本操作为：生成一个结点。其基本操作为：生成一个结点。 根元素根元素 T 左子树左子树右子树右子树 根元素根元素 NEWT 左子树左子树右子树右子树 左子树左子树 右子树右子树 (后序遍历后序遍历) 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(1); T- data = item; T- lchild = lptr; T-

24、 rchild = rptr; return T; 生成一个二叉树的结点生成一个二叉树的结点 (其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr) 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/复制左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/复制右子树 else

25、 newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr); return newT; / CopyTree 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 A B C D E F G HK D C B H K G F E A 例如：下列二叉树例如：下列二叉树 的复制过程如下：的复制过程如下： newT 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 4 4、建立二叉树的存储、建立二叉树的存储 结构结构 不同的定义方法相应有不同的不同的定义方法相应有不同的 存储结构的建立算法存储结构的建立算法 四川大学四川大学 计算机

26、学院计算机学院 游洪跃游洪跃 以字符串的形式以字符串的形式 根根 左子树左子树 右子树右子树 定义一棵二叉树定义一棵二叉树 例如: A B C D 以空白字符“ ”表示 A(B( ,C( , ),D( , ) 空树空树 只含一个根结点只含一个根结点 的二叉树的二叉树 A 以字符串“A ”表示 以下列字符串表示 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 Status CreateBiTree(BiTree if (ch= ) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-dat

27、a = ch; / 生成根结点 CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树 return OK; / CreateBiTree 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 A B C D A BCD 上页算法执行过程举例如下： A T B C D 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 Linked Binary Tree Binary tree class: template template class Binary_tree public: / Add methods here.p

28、rotected: / Add auxiliary function 原型原型prototypes here. Binary_node *root; ; Binary node class: template struct Binary_node / data members: Entry data; Binary_node *left; Binary_node *right; / constructors: Binary_node(); Binary_node(const Entry ; 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 Binary Tree Class templat

29、e class Binary_tree public: Binary_tree(); bool empty() const; void preorder(void (*visit)(Entry void inorder(void (*visit)(Entry void postorder(void (*visit)(Entry int size() const; void clear(); int height() const; void insert(const Entry Binary_tree (const Binary_tree Binary_tree Binary_tree(); p

30、rotected: / Add auxiliary function prototypes here. Binary_node *root; ; 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 Constructor: template Binary tree : Binary_tree( ) /* Post: An empty binary tree has been created. */ root = NULL; Empty: template bool Binary_tree : empty( ) const /* Post: A result of true is return

31、ed if the binary tree is empty. Otherwise, false is returned. */ return root = NULL; 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 Inorder traversal: template void Binary_tree : inorder(void (*visit)(Entry Most Binary tree methods described by 递归recursive processes can be 实现 implemented by calling an 辅助auxiliary recur

32、sive function that applies to 子树subtrees. 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 Inorder traversal: template void Binary_tree : Recursive_inorder(Binary node *sub_root, void (*visit)(Entry (*visit)(sub root-data); recursive inorder(sub root-right, visit); 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 线索二叉树线索二叉树 四川大学四川大学 计算机学院计算机学

33、院 游洪跃游洪跃 遍历二叉树的结果是，遍历二叉树的结果是， 求得结点的一个线性序列求得结点的一个线性序列 A B C D E F G HK 先序序列先序序列 A B C D E F G H K 中序序列中序序列 B D C A H G K F E 后序序列后序序列 D C B H K G F E A 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 指向该线性序列中的指向该线性序列中的“前驱前驱” 和和 “后继后继” 的指针，称作的指针，称作“线线 索索” 与其相应的二叉树，与其相应的二叉树， 称作称作 “线索二叉树线索二叉树” 包含包含 “线索线索” 的存储的存储 结构，称作结构，称作

34、“线索链线索链 表表” A B C D E F G H K D C B E 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 对对线索链表线索链表中结点的约定中结点的约定 在二叉链表的结点中在二叉链表的结点中增加两个标志域增加两个标志域 LTag和和RTag,并作如下规定并作如下规定: 若该结点的左子树不空，若该结点的左子树不空， 则则LChild域的指针指向其域的指针指向其左孩子左孩子， 且左标志且左标志LTag的值为的值为0 否则，否则，LChild域的指针指向其域的指针指向其“前驱前驱”， 且左标志且左标志LTag的值为的值为1 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃

35、若该结点的右子树不空，若该结点的右子树不空， 则则RChild域的指针指向其域的指针指向其右孩子右孩子， 且右标志且右标志RTag的值为的值为0 否则，否则，RChild域的指针指向其域的指针指向其“后继后继”， 且右标志且右标志RTag的值为的值为1 如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作 “线索链表线索链表” 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 带表头结点的中序线索二叉树带表头结点的中序线索二叉树 四川大学四川大学 计算机学院计算机学院 游洪跃

36、游洪跃 哈哈 夫夫 曼曼 树树 与与 哈哈 夫夫 曼曼 编编 码码 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 结点的路径长度结点的路径长度 从根结点到该结点的路径上分从根结点到该结点的路径上分 支的数目支的数目 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 树的路径长度树的路径长度 树中每个结点的路径长度之和树中每个结点的路径长度之和 1 0 n i ii lwWPL 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 在所有含在所有含n n个叶子结点、并带相同个叶子结点、并带相同 权值的权值的m m叉树中，必存在一棵其叉树中，必存在一棵其带权路带权路 径长度取最小值径长

37、度取最小值的树，称为的树，称为“最优树最优树”, 或或“哈夫曼树哈夫曼树” 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 具有不同带权路径长度的二叉树具有不同带权路径长度的二叉树 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 WPL(T)= 7 2+5 2+2 3+ 4 3+9 2 =60 WPL(T)= 7 4+9 4+5 3+ 4 2+2 1 =89 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 根据给定的根据给定的 n 个权值个权值 w1, w2, , wn，造，造 n 棵二叉树的集合棵二叉树的集合 F = T

38、1, T2, , Tn， 其中每棵二叉树中均只含一个带权其中每棵二叉树中均只含一个带权 值为值为 wi 的根结点，其左、右子树为的根结点，其左、右子树为 空树；空树； 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 在在 F 中选取其根结点的权值为最中选取其根结点的权值为最 小的两棵二叉树，分别作为左、小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之为其左、右子树根结点的权值之 和；和； 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 从从F中删去这两棵树，

39、同时加入中删去这两棵树，同时加入 刚生成的新树刚生成的新树 重复重复 和和 两步，直至两步，直至 F 中只中只 含一棵树为止含一棵树为止 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 0 00 0 1 1 1 1 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 哈夫曼算法 const unsigned int n=256;/字符数字符数 const unsigned

40、int m=256*2-1;/结点总数结点总数 struct HTNode/压缩用压缩用Huffman树结点树结点 unsigned long weight;/字符频度（权值）字符频度（权值） unsigned int parent,lchild,rchild; ; struct Buffer/字节缓冲压缩用字节缓冲压缩用Huffman树树 unsigned char ch;/字节字节 unsigned int bits;/实际比特数实际比特数 ; 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 哈夫曼算法哈夫曼算法(class HuffmanTree(1) class HuffmanT

41、ree/Huffman树树 public: void Code();/编码编码 void UnCode();/译码译码 private: HTNode HTm+1;/树结点表树结点表(HT1到到HTm) char Leafn+1;/叶结点对应字符叶结点对应字符(leaf1到到leafn) /叶结点对应编码叶结点对应编码(*HuffmanCode1到到*HuffmanCoden) char *HuffmanCoden+1; unsigned int count;/频度大于零的字符数频度大于零的字符数 /字符对应在树结点表的下标字符对应在树结点表的下标(char_index0到到char_inde

42、xn-1) unsigned int char_indexn; unsigned long size; /被压缩文件长度被压缩文件长度 FILE *infp,*outfp;/输入输入/出文件出文件 Buffer buf;/字符缓冲字符缓冲 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 哈夫曼算法(class HuffmanTree(2) void Stat();/统计字符出现频度并过滤掉频度为零的字符 /在HT1HTk中选择parent为-1，树值最小的两个结点s1,s2 void Select(unsigned int k, unsigned int void Write(unsig

43、ned int bit);/向outfh中写入一个比特 void Write(unsigned int num,unsigned int k);/向outfh中写入k个比特 void WriteToOutfp();/强行写入outfh void Read(unsigned int /从infh中读出一个比特 void Read(unsigned int /从infh中读出k个比特 /0num-1之间的整数用二进位表示所需的位数 int NToBits(unsigned int num); /由编码文件中存储的树结构建立Huffman树 void CreateFromCodeFile(); /由

44、被压缩文件建立Huffman树,将树结构存入编码文件的文件头部 / 中,并求每个字符的Huffman编码 void CreateFromSourceFile(); ; 四川大学四川大学 计算机学院计算机学院 游洪跃游洪跃 哈夫曼算法哈夫曼算法(CreateFromSourceFile()(1) void HuffmanTree:CreateFromSourceFile() /由被压缩文件建立Huffman树,将树结构存入编码文件的文件头部中 /并求每个字符的Huffman编码 Stat();/统计字符出现频度并过滤掉频度为零的字符 /由被压缩文件建立Huffman树 unsigned int i,s1,s2; for(i=1;i=n;i+)HTi.parent=HTi.lchild=HTi.rchild=0; for(i=count+1;i=2*count-1;i+)/建立Huffman树 Select(i-1,s1,s2); /选择parent为0，权值最小的两个结点s1,s2 HTs1.parent=HTs2.parent=i; HTi.parent=0;HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; 四川大