第6章 树和二叉树.ppt

《第6章 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《第6章 树和二叉树.ppt（108页珍藏版）》请在三一文库上搜索。

1、第6章 树和二叉树,6.1 树的类型定义,6.2 二叉树的类型定义和实现,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.6 Huffman树与Huffman编码,6.5 树与等价问题,6.1 树的类型定义,树 是 n 个结点的有限集 D，当n1 时： 1) 有一个特定的结点 root 被称为根(结点); 2) 根以外的结点被分成 m (m0) 个不相交的有限集 T1, T2, , Tm，其中每个集合又是一棵树，称为根的子树。,树的定义是一个递归的定义，可以用广义表的形式描述： Tree = ( root, T1, T2, , Tm ) 其中 root 是结点类型，其余为树类型(广义表类

2、型)。,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素 (无前驱),一个首元素 (无前驱),最后一个数据元素 (无后继),多个尾元素 (无后继),其它数据元素 (一个前驱、一个后继),其它数据元素 (一个前驱、多个后继),基 本 术 语,结 点：数据元素+若干指向子树的分支。,结点的度：分支的个数。,树的度：树中所有结点的度的最大值。,叶子结点：度为零的结点。,分支结点：度大于零的结点。,(从根到结点的)路径：从根到该结点所经分支和结点构成的集合。,孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点,结点的层次：假设根结点的层次为 1，第 i 层的结点的子树的根结点

3、的层次为 i+1。,树的深度：树中叶子结点所在的最大层次。,森 林：是m (m0)棵互不相交的树的集合。,有向树：) 有确定的根； ) 树根和子树根之间为有向关系。,有序树：子树之间存在确定的次序关系。,无序树：子树之间不存在确定的次序关系。,就逻辑结构而言，树是二元组：,Tree = ( root, F ),F 是 m (m0) 棵子树的森林，F = ( T1, T2, , Tm )，其中 Ti = ( ri, Fi )； 当 m0 时，存在关系： RF = | i = 1, 2, , m , m 0 ,树的抽象数据类型定义如下：,ADT Tree ,若D为空集，则称为空树。否则: 1) 在

4、D中存在唯一的称为根的数据元素 root； 2) 当n 1时，其余结点可分为 m (m0)个互不相交的有限集T1, T2, , Tm，其中每个子集本身又是符合本定义的一棵树，称为根 root 的子树。,数据对象：,D 是具有相同特性的数据元素的集合。,数据关系：,基本操作：,初始化操作,InitTree( &T ) 操作结果：初始化置空树 。,DestroyTree( &T ) 初始条件：树 T 存在。 操作结果：销毁树 T 。,结构销毁操作,CreateTree( &T, definition ) 操作结果：按定义构造树 。,引用型操作,Root( T ) 初始条件：树 T 存在。 操作结果

5、：求树的根结点。,Parent( T, cur_e ) 初始条件：树 T 存在。 操作结果：用 cur_e 返回当前结点双亲的元素值。,Value( T, cur_e ) 初始条件：树 T 存在。 操作结果：用 cur_e 返回当前结点的元素值。,引用型操作（续）,RightSibling( T, cur_e ) 初始条件：树 T 存在。 操作结果：用 cur_e 返回当前结点右兄弟的元素值。,LeftSibling( T, cur_e ) 初始条件：树 T 存在。 操作结果：用 cur_e 返回当前结点左兄弟的元素值。,引用型操作（续）,TreeEmpty( T ) 初始条件：树 T 存在。

6、 操作结果：判定树是否为空树 。,TraverseTree( T, Visit( ) ) 初始条件：树 T 存在。 操作结果：按照某种顺序用Visit访问所有的结点。,TreeDepth( T ) 初始条件：树 T 存在。 操作结果：求树的深度。,加工型操作,DeleteChild( &T, &p, i ) 初始条件：树 T 存在，1 i Degree(p)。 操作结果：删除结点p的第i棵子树。,InsertChild( &T, &p, i, c ) 初始条件：树 T 存在，且 i 1。 操作结果：将以c为根的树插入为结点p的第i棵子树。,加工型操作（续）,ClearTree( &T ) 初始

7、条件：树 T 存在。 操作结果：清空树中的所有结点。, ADT Tree,Assign( T, &cur_e, value ) 初始条件：树 T 存在。 操作结果：用 value 给当前结点 cur_e 赋值。,6.2 二叉树的类型定义和实现,二叉树中每个结点至多只有 2 棵子树，二叉树的子树有左右之分。,二叉树的五种基本形态：,空树,左右子树均为空树,右子树为空树,左子树为空树,左右子树均不为空树,二叉树的抽象数据类型定义如下：,若D为空集，则称为空树。否则: 1) 在D中存在唯一的称为根的数据元素 root； 2) 当n 1时，其余结点可分为2个互不相交的有限集T1，T2，其中每一棵子集本

8、身又是一棵符合本定义的二叉树，T1称为根 root 的左子树，T2称为根 root 的右子树，,ADT BinaryTree ,数据对象：,D 是具有相同特性的数据元素的集合。,数据关系：,基本操作：,初始化操作,InitBiTree( &T ) 操作结果：初始化置空二叉树。,DestroyBiTree( &T ) 初始条件：二叉树 T 存在。 操作结果：销毁二叉树 T 。,结构销毁操作,CreateBiTree( &T, definition ) 操作结果：按定义构造二叉树。,引用型操作,Root( T ) 初始条件：二叉树 T 存在。 操作结果：求二叉树的根结点。,Parent( T, e

9、 ) 初始条件：二叉树 T 存在。 操作结果：用 e 返回当前结点双亲的元素值。,Value( T, e ) 初始条件：二叉树 T 存在。 操作结果：用 e 返回当前结点的元素值。,引用型操作（续）,LeftChild( T, e ) 初始条件：二叉树 T 存在。 操作结果：用 e 返回当前结点左孩子的元素值。,RightChild( T, e ) 初始条件：二叉树 T 存在。 操作结果：用 e 返回当前结点右孩子的元素值。,引用型操作（续）,RightSibling( T, e ) 初始条件：二叉树 T 存在。 操作结果：用 e 返回当前结点右兄弟的元素值。,LeftSibling( T,

10、e ) 初始条件：二叉树 T 存在。 操作结果：用 e 返回当前结点左兄弟的元素值。,引用型操作（续）,BiTreeEmpty( T ); 初始条件：二叉树 T 存在。 操作结果：判定二叉树是否为空树 。,BiTreeDepth( T ) 初始条件：二叉树 T 存在。 操作结果：求二叉树的深度。,PreOrderTraverse( T, Visit( ) ) 初始条件：二叉树 T 存在。 操作结果：按照先序用Visit遍历二叉树中的所有结点。,InOrderTraverse( T, Visit( ) ) 初始条件：二叉树 T 存在。 操作结果：按照中序用Visit遍历二叉树中的所有结点。,引用

11、型操作（续）,PostOrderTraverse( T, Visit( ) ) 初始条件：二叉树 T 存在。 操作结果：按照后序用Visit遍历二叉树中的所有结点。,LevelOrderTraverse( T, Visit( ) ) 初始条件：二叉树 T 存在。 操作结果：按照层次用遍历Visit二叉树中的所有结点。,引用型操作（续）,加工型操作,InsertChild( &T, &p, LR, c ) 初始条件：二叉树 T 存在。 操作结果：根据LR的值，将以c为根的树插入为结点p的子树。,DeleteChild( T, p, LR ); 初始条件：二叉树 T 存在。 操作结果：根据LR的值

12、，删除结点p的子树。,加工型操作（续）,ClearBiTree( &T ) 初始条件：二叉树 T 存在。 操作结果：清空二叉树中的所有结点。, ADT BinaryTree,Assign( T, &e, value ) 初始条件：二叉树 T 存在。 操作结果：用 value 给当前结点 e 赋值。,二叉树的重要特性,性质 1 在二叉树的第 i 层上至多有2i-1 个结点(i1),证明：用归纳法证明，,i = 1层时，只有一个根结点：2i-1=20=1；假设对所有的 j，1ji，命题成立，二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-22 = 2i-1 。,性质 2 深度为 k

13、 的二叉树上至多含 2k-1 个结点(k1)。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为20+21+ +2k-1 = 2k-1 。,性质 3 对任何一棵二叉树，若它含有 n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,证明：,设二叉树上结点总数 n = n0 + n1 + n2，二叉树上分支总数(总度数) b = n1+2n2，而 b = n-1 = n0 + n1 + n2 1，由此，n0 = n2 + 1。,除根结点外，每个结点指向双亲结点的分支只有一条。,两类特殊的二叉树：,满二叉树(Full Binary Tree) ：指的是深度为

14、 k 且含有 2k-1 个结点的二叉树。,完全二叉树(Complete Binary Tree) ：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,性质4 具有 n 个结点的完全二叉树的深度为 log2n +1,证明：,设完全二叉树的深度为 k ，则根据性质 2 得 2k-1 n 2k，log2n为递增函数， log2n k log2n+1，k 必须为整数，因此， k = log2n + 1 。,性质 5 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：,1) 若 i=1，则该结点是二叉树的根，无双亲

15、，否则，编号为 i/2 的结点为其双亲结点； 2) 若 2i n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点； 3) 若 2i+1 n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。,二叉树的存储结构,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0 号单元存储根结点 SqBiTree bt;,1. 二叉树的顺序存储表示,按照依次自上而下、自左至右的顺序，存储完全二叉树结点的元素值。 一般二叉树则按完全二叉树编号后存储，编号处无结点的位置不存储

16、。,例6-2 顺序表示下列二叉树,0,1,2,3,4,5,6,7,8,9,10,11,12,13,2. 二叉树的链式存储表示,二叉链表,结点结构:,typedef struct BiTNode / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; / 双亲指

17、针 TriTNode, *TriTree;,结点结构:,三叉链表,6.3 遍历二叉树和线索二叉树,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。,二叉树由根、左子树和右子树组成。对二叉树而言，可以有三条搜索路径： 1）先(根)序遍历：根 左子树 右子树(TLR) 2）中(根)序遍历：左子树 根 右子树(LTR) 3）后(根)序遍历：左子树 右子树 根(LRT),一. 遍历二叉树,若二叉树为空树，则空操作；否则， 1) 访问根结点； 2) 先序遍历左子树； 3) 先序遍历右子树。,1. 先(根)序的遍历算法:,访问路径描述：从根结点开始，沿着左子树方向依次访问

18、，当左子树遍历完成，从左子树退回时访问每个结点的右子树。,例6-3 先序遍历下列二叉树,遍历结果(先序序列)为,a b d e h I j k c f g,先序序列的特点：,1）首结点为根结点 2）无法区分左右子树,void Preorder( BiTree T, void (*visit)(TElemType / 遍历右子树 / Preorder,算法的递归描述：,void Preorder( BiTree T, void( *visit)(TElemType / while / Preorder,算法的非递归描述：,若二叉树为空树，则空操作；否则， 1) 中序遍历左子树； 2) 访问根结点

19、； 3) 中序遍历右子树。,2.中(根)序的遍历算法：,访问路径描述：沿着左子树方向找到最“左边”的结点作为起点，从左子树退回时依次访问每个结点及其右子树。,例6-4 中序遍历下列二叉树,遍历结果(中序序列)为,d b h e j i k a f c g,中序序列的特点：,1）无法确定根结点 2）若已知根结点，可区分左右子树,void Inorder( BiTree T, void( *visit)(TElemType / 遍历右子树 / Inorder,算法的递归描述：,void Inorder( BiTree T, void( *visit)(TElemType / while / Ino

20、rder,算法的非递归描述：,若二叉树为空树，则空操作；否则， 1) 后序遍历左子树； 2) 后序遍历右子树； 3) 访问根结点。,3.后(根)序的遍历算法：,访问路径描述：找到最“左边”的叶子结点作为起点，每次经过一个结点时需要判断：如果是从左子树返回，则进入右子树；如果从右子树返回，则访问该结点并后退。判断的方法是看该结点的右子树的根是否为刚刚访问的那个结点。,例6-5 后序遍历下列二叉树,遍历结果(后序序列)为,d h j k i e b f g c a,后序序列的特点：,1）尾结点为根结点 2）无法区分左右子树,void Postorder( BiTree T, void( *visi

21、t)(TElemType / 访问结点 / Postorder,算法的递归描述：,void Postorder( BiTree T, void( *visit)(TElemType / 用q保存刚访问的结点 / else / while / Postorder,算法的非递归描述：,例6- 6 写出二叉树的三种遍历序列,先序序列：ABDEGCFHI,中序序列：DBGEACHFI,后序序列：DGEBHIFCA,由二叉树的前序序列和中序序列可以唯一确定这棵二叉树。 由二叉树的后序序列和中序序列可以唯一确定这棵二叉树。 由二叉树的前序序列和后序序列不能唯一确定这棵二叉树。,结论：,例6- 7 已知一棵

22、二叉树的先序序列为 ABHFDECKG 和中序序列 HBDFAEKCG ，求这棵二叉树,1）根结点 A,2）左子树中序序列 HBDF，右子树中序序列 EKCG,3）左子树先序序列 BHFD，右子树先序序列 ECKG,先序遍历结果(先序序列) - + a * b - c d / e f,中序遍历结果(中序序列) a + b * ( c d ) e / f,后序遍历结果(中序序列) a b c d - * + e f / -,例6-8 分别以先序、中序和后序遍历下列二叉树,4.按层次的遍历算法：,访问路径描述：按照从上层到下层，每层从左至右的顺序遍历结点。,第 k 层结点的访问顺序为从坐至右，第

23、k+1 层按照相同的顺序遍历 k 层结点的孩子结点。,算法中用队列暂存第 k 层经过的结点,算法描述：,void LevelTravelTree(BiTree T, void(*visit)(TElemType / LevelTravelTree,二. 遍历算法的应用举例,. 统计二叉树中叶子结点的个数,算法基本思想:,遍历二叉树，“访问结点(visit)” 的操作为：计数。,void CountLeaf( BiTree T, int / if / CountLeaf,. 求二叉树的深度,算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加 1。 “访问结点(vi

24、sit)” 的操作为：求得左、右子树深度的最大值，然后加 1 。 遍历顺序为：后序。,首先分析二叉树的深度和它子树深度之间的关系：,int Depth( BiTree T ) if( !T ) depthval = 0; else depthL = Depth( T-lchild ); depthR = Depth( T-rchild ); depthval = 1 + (depthL depthR? depthL : depthR ); return depthval; / Depth,. 二叉树的创建,以字符串的形式输入二叉树：按照二叉树先序遍历的顺序输入二叉树中每个结点的元素。空结点也必

25、须输入。,空树以空格字符“”表示；,只含一个根结点的二叉树 ：以字符串“A”表示；,例6-9 以字符串“ABCD”表示二叉树 T,A (B (C () D (),Status CreateBiTree( BiTree / CreateBiTree,三. 线索二叉树,. 何谓线索二叉树？,遍历二叉树的结果是结点的一个线性序列。,先序序列: 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,B D C A H G K F E,遍历序列中表示线性关系指针称为“线索”。,在二叉链表的结点中增加两个标志域，并作如下规定：,

26、1）若该结点的左子树不空，则 lchild 指针指向其左子树，且左标志的值为 0；否则，lchild 指针指向其前驱，且左标志的值为 1。,2）若该结点的右子树不空，则 rchild 指针指向其右子树，且右标志域的值为 0；否则，rchild 指针指向其后继，且右标志的值为 1。,线索链表的 C 语言描述：,typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索,typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 P

27、ointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,以这种结点定义的二叉树的存储结构称作“线索链表”。 其二叉树称为“线索二叉树”。,在线索链表中定义头结点，其 lchild 指向二叉树的根结点，LTag 为 0；rchild 指向遍历序列中的最后一个结点，RTag 为 1。,对二叉树进行遍历，使其变为线索二叉树的过程叫做“线索化”。,遍历序列中首结点的 lchild 指向头结点，尾结点的 rchild 指向头结点。,. 线索链表的遍历算法:,例如: 对中序线索链表的遍历算法, 中序遍历的第一个结点 ？,左子树上最“左边的”没有左子树的结点。

28、, 在中序线索链表中结点的后继 ？,若无右子树，则为后继线索所指结点；,否则为其右子树进行中序遍历访问的第一个结点。,void InOrder_Thr( BiThrTree T, void (*Visit)(TElemType e) ) / 遍历头结点为 T 的中序线索链表 p = T-lchild; / p 指向根结点 while( p != T ) / 最后一个结点的 rchild 指向 T while( p-LTag = Link ) p = p-lchild; / 第一个结点 (*Visit)( p-data ); while( p-RTag = Thread / 进入右子树 / In

29、OrderTraverse_Thr,. 建立中序线索链表,BiThrNode *pre = NULL; void InThreading( BiThrTree p ) / 结点线索化 if( p ) InThreading( p-lchild ); / 左子树线索化 if( !p-lchild ) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if( !pre-rchild ) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading( p-rchild

30、 ); / 右子树线索化 / if / InThreading,Status InOrderThreading( BiThrTree / 处理最后一个结点,pre-RTag = Thread; Thrt-rchild = pre; return OK; / InOrderThreading,在算法中，pre 作为公用变量，在函数 InThreading 中的修改必须反应在算法中。这样，当 InThreading(T) 执行完毕时，pre 是其中序遍历序列中的最后一个结点，T 不变。,6.4 树和森林,一. 树的存储结构,. 双亲表示法,顺序存储结构，每个结点指示双亲结点的位置,0,1,2,3,

31、4,5,6,data,parent,r = 0 n = 6,typedef struct PTNode TElemType data; int parent; / 双亲位置域 PTNode;,#define MAX_TREE_SIZE 100,双亲表的 C 语言描述:,typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;,. 孩子链表表示法,顺序 + 链式存储结构，顺序存放结点，每个结点指向其孩子结点的单链表。,0,1,2,3,4,5,6,data,firstchild,r = 0 n = 6,type

32、def struct CTNode int child; struct CTNode *next; *ChildPtr; / 孩子结点结构,typedef struct ElemType data; ChildPtr firstchild; / 孩子链表的头指针 CTBox; / 双亲结点结构,typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;,孩子链表的 C 语言描述:,. 孩子-兄弟表示法(二叉树表示法),链式存储结构，用二叉链表作为存储结构。左指针指向第一个孩子结点，右指针指向右兄弟结点。,type

33、def struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;,二叉链表的 C 语言描述:,二. 树、森林和二叉树的对应关系,根据二叉链表表示法，任何一棵树和二叉树之间存在对应关系：树对应的二叉树的右子树为空。,设森林为：F = T1, T2, , Tm ， 二叉树为：B = ( root, LB, RB ),如果森林中的树的根结点之间看作是兄弟关系，则可以构建森林对应的二叉树。,由森林转换成二叉树的转换规则为:, 若 F = ，即 m = 0，则 B = ;, 若 F ，即

34、m 0，则 root = ROOT(T1)，LB为T1的子树森林 T11, T12, , T1n 对应的二叉树，RB为森林 T2, , Tm 对应的二叉树。,由二叉树转换为森林的转换规则为：, 若 B = ， 则 F = ；, ROOT(T1) = root；由 LB 对应得到 T11, T12, ，T1n ；由RB对应得到 T2, T3, , Tm 。,三. 树和森林的遍历,1. 树的遍历可有三条搜索路径:,按层次遍历:,先根(次序)遍历:,后根(次序)遍历:,若树不空，先访问根结点，然后依次先根遍历各棵子树。,若树不空，先依次后根遍历各棵子树，然后访问根结点。,若树不空，则自上而下自左至右

35、访问树中每个结点。,先根遍历时顶点的访问次序：,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,例6-10 遍历下列树的顶点序列分别是：,1第一棵树的根结点；,2第一棵树的子树森林；,3其它树构成的森林。,根据森林和二叉树的对应关系，森林由三部分构成：,2. 森林的遍历,1. 先序遍历, 若森林不空，则访问森林中第一棵树的根结点； 先序遍历森林中第一棵树的子树森林； 先序遍历森林中其余树构成的森林。,即：依次从左至右对森林中的每一棵树进行先根遍历。,2.

36、中序遍历, 若森林不空，则中序遍历第一棵树的子树森林； 访问森林中第一棵树的根结点； 中序遍历森林中其余树构成的森林。,即：依次从左至右对森林中的每一棵树进行后根遍历。,树的遍历和二叉树遍历的对应关系 ？,6.6 树与等价问题,一. 等价关系与等价类,等价关系：R 是集合 S 上的一个二元关系，满足自反性、对称性和传递性。,若 R 是 S 上的一个等价关系，则由 R 可以产生 S 的唯一划分 S1, S2, ，这些子集互不相交，其并集为 S，则子集 Si 称为 S 的R 等价类。,按给定的等价关系划分某几个为等价类，称为等价问题。,二. 划分等价类,假设集合 S 有 n 个元素，m 个形如 (

37、x, y) (x, yS) 的等价偶对确定了等价关系 R，求 S 的划分。,确定等价类的算法：,1）令 S 中的每个元素各自形成一个只含单成员的子集，记作 S1, S2, , Sn；,2）重复读入 m 个偶对，对每个读入的偶对 (x, y)，判定 x, y 所属子集 Si 和 Sj，则 Si Sj 取代 Si 和 Sj ；,3）当 m 个偶对都被处理后，剩余的非空子集即为 S 的 R 等价类。,划分等价类需要对集合进行三个基本操作：,构造只含一个元素的集合； 判定两个元素所在的子集； 合并两个互不相交的集合。,实现约定：,树型结构表示集合，结点表示元素； 根结点的成员兼作子集的名称,基本操作的

38、实现：,森林 F = T1, T2, , Tn 表示集合 S，树 Ti 表示每个子集 Si，每个结点代表每个元素，每棵树的根结点同时用来表示子集 Si。,判定某个元素属于某个集合：从某个元素(结点)出发，向上逐级找到根结点。,集合的合并：将一棵树根结点的双亲指向另一棵树的根结点。,采用双亲表示法作为存储结构,typedef PTree MFSet;,int find_mfset( MFSet S, int i ) / 找到元素 i 所在的集合(根) if( i S.n ) return -1; for( j = i; S.nodej.parent 0; j = S.nodesj.parent)

39、; return j; / find_mfset,查找和合并函数,int merge_mfset( MFSet / find_mfset,若每次将成员多的根结点指向成员少的根结点，则全部操作的时间复杂度高。,在“并”之前先判断子集中成员的数目，令成员少的根结点指向成员多的根结点,改进：,修改存储结构：根结点 parent 为子集成员数量的负数。,修改后的合并函数,int mix_mfset(MFSet / find_mfset,例6-11 设集合 S = x | 1 x n 是正整数 ，R 是 S 上的一个等价关系。,R = ( 1, 2 ), ( 3, 4 ), ( 5, 6 ), ( 7,

40、 8 ), ( 1, 3 ), ( 5, 7 ), ( 1, 5 ) ,求 S 的等价类。,1）开始,分为 n 棵树，每个结点都是根结点,2）处理 ( 1, 2 ), ( 3, 4 ), ( 5, 6 ), ( 7, 8 ) 之后,3）处理 ( 1, 3 ), ( 5, 7 ) 之后,4）处理 ( 1, 5 ) 之后,改进查找子集算法，当所查元素 i 不在树的第二层时，增加“压缩路径”功能，从根结点到 i 路径上的元素都变为根结点的孩子结点。,int fix_mfset(MFSet S, int i ) / 找到元素 i 所在的集合(根) if( i S.n ) return -1; for(

41、 j = i; S.nodej.parent 0; j = S.nodesj.parent); for( k = i; k != j; k = t ) t = S.nodesk.parent; S.nodesk.parent = j; return j; / fix_mfset,6.7 Huffman树与Huffman编码,一. 最优二叉树(Huffman树),结点路径长度：从根到该结点的路径上分支的数目。,树的路径长度：树中每个结点的路径长度之和。,树的带权路径长度：树中所有叶子结点的带权路径长度之和。,结点的带权路径长度：从根到该结点之间的路径长度与结点权的乘积。,在所有含 n 个叶子结点

42、、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。如果 m = 2，称为“最优二叉树”。,例6-12 求下列二叉树的带权路径长度,WPL = 60,WPL = 89, 根据给定的 n 个权值 w1, w2, , wn ，构造 n 棵二叉树的集合 F = T1, T2, , Tn ，Ti 为一个权值为 wi 的结点构成的二叉树；,二. 构造Huffman树,Huffman算法：, 在 F 中选取根的权值最小的两棵二叉树，分别作为左右子树构造一棵新的二叉树，并置这棵新二叉树根的权值为其左右孩子结点的权值之和；, 将新二叉树加入 F，并在 F 中删除其左右子树；,

43、重复 (2) 和 (3) 两步，直至 F 中只含一棵树为止。,例6-13 已知权值 W= 5, 6, 2, 9, 7 ,二叉树集合 F 变化如下：,1）,2）,3）,4）,5）,前缀编码：不等长编码中，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,三. Huffman 编码,利用Huffman 树可以构造一种不等长的二进制编码，并且构造所得的Huffman编码是一种最优前缀编码，即使所传电文的总长度最短。,不等长编码中，出现频率大的字符的编码长度短。,例6-14 假设用于通信的电文由8个字母(AH)组成，字母在电文出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计 Huffman编码。,算法提示：将频率(100) 看作是AH 的权值，根据权值的集合构造最优二叉树。每个权值结点最后得到的编码就是相对应的字符的Huffman 编码。,本章学习要点,