《数据结构使用C语言描述第2版第05章树》由会员分享，可在线阅读，更多相关《数据结构使用C语言描述第2版第05章树（119页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构 Data Structures in C+南京邮电大学计算机学院南京邮电大学计算机学院第第5 5章章 树树南京邮电大学计算机学院南京邮电大学计算机学院树的根本概念的根本概念二叉二叉树二叉二叉树的遍的遍历树和森林和森林堆和堆和优先先权队列列哈夫曼哈夫曼树和哈夫曼和哈夫曼编码并并查集和等价关系集和等价关系南京邮电大学计算机学院南京邮电大学计算机学院5.1 5.1 树的根本概念树的根本概念南京邮电大学计算机学院南京邮电大学计算机学院 树形结构是元素之间有着分层关系的结构，树形结构是元素之间有着分层关系的结构，它类似于自然界中的树。这是一类很重要的它类似于自然界中的树。这是一类很重要
2、的非线性数据结构。非线性数据结构。 一方面，计算机应用中，常常出现嵌套的一方面，计算机应用中，常常出现嵌套的数据，树结构提供了对该类数据的自然表示。数据，树结构提供了对该类数据的自然表示。另一方面利用树结构，我们可以有效地解决另一方面利用树结构，我们可以有效地解决一些算法问题。一些算法问题。南京邮电大学计算机学院南京邮电大学计算机学院图图5-1 5-1 西欧语言谱系图西欧语言谱系图原始印欧语原始印欧语古意大利语古意大利语日耳曼语日耳曼语西日耳曼语西日耳曼语拉丁语拉丁语西西班班牙牙语语法法语语意意大大利利语语希腊语希腊语北日耳曼语北日耳曼语冰冰岛岛语语瑞瑞典典语语挪挪威威语语英英语语荷荷兰兰语语
3、德德语语古希腊语古希腊语南京邮电大学计算机学院南京邮电大学计算机学院5.1.1树的定义树的定义树是包括树是包括n个结点的有限非空集合个结点的有限非空集合D，R是是D中元素的序偶的集合，中元素的序偶的集合，R满足以下特性：满足以下特性：1有且仅有一个结点有且仅有一个结点rD，不，不存在任何结点存在任何结点vD，vr，使得，使得R，称，称r为树的根为树的根；2除根除根r以外的所有结点以外的所有结点uD，都有且仅有一个结点，都有且仅有一个结点vD，vu，使得，使得R。这样定义的树也称有根树，简称这样定义的树也称有根树，简称树。树。南京邮电大学计算机学院南京邮电大学计算机学院树是包括树是包括n个结点的
4、有限非空集合个结点的有限非空集合T，其中，其中，一个特定的结点一个特定的结点r称为根，其余结点称为根，其余结点T-r划划分成分成mm0个互不相交的子集个互不相交的子集T1,T2, ,Tm，其中，每个子集都是树，被，其中，每个子集都是树，被称为树根称为树根r的子树。的子树。南京邮电大学计算机学院南京邮电大学计算机学院5.1.2 根本术语根本术语 树树中中元元素素常常称称为为结结点点 。根根和和它它的的子子树树根根如如果果存存在在之之间间形形成成一一条条边边 。如如果果从从某某个个结结点点沿沿着着树树中中的的边边可可到到达达另一个结点，那么称这两个结点间存在一条路径另一个结点，那么称这两个结点间存
5、在一条路径 。南京邮电大学计算机学院南京邮电大学计算机学院 假假设设一一个个结结点点有有子子树树，那那么么该该结结点点称称为为子子树树根根的的双双亲亲，子子树树的的根根是是该该结结点点的的孩孩子子。有有相相同同双双亲亲的的结结点点互互为为兄兄弟弟。一一个个结结点点的的所所有有子子树树上上的的任任何何结结点点都都是是该该结结点点的的后后裔裔。从从根根结结点点到到某某个结点路径上的所有结点都是该结点的祖先个结点路径上的所有结点都是该结点的祖先 。南京邮电大学计算机学院南京邮电大学计算机学院一一个个结结点点拥拥有有的的子子树树数数称称为为该该结结点点的的度度。度度为为零零的的结结点点称称为为叶叶子子
6、，其其余余结结点点称称为为分分支结点支结点。树中结点的最大的度称为树中结点的最大的度称为树的度。树的度。树树是是层层次次结结构构的的，规规定定根根结结点点的的层层次次为为1 1，其其结结点点的的层层次次等等于于其其双双亲亲结结点点的的层层次次加加1 1。树中结点的最大层次称为该。树中结点的最大层次称为该树的高度树的高度。南京邮电大学计算机学院南京邮电大学计算机学院如如果果树树中中结结点点的的各各子子树树之之间间的的次次序序是是不不重重要要的的，可可以以交交换换位位置置，这这样样的的树树称称为为无无序序树树。也也就就是是我我们们通通常常所所说说的的树树。如如果果将将树树中中结结点点的的各各棵棵子
7、子树树看看成成是是从从左左到到右右有有次次序序的的，那那么么称称该该树树为为有有序序树树。从从左左到到右右，可可分分别别称称这这些些子子树树为为第第一一子子树树，第第二二子子树树等等等。等。森森林林是是树树的的集集合合。果果园园或或称称有有序序森森林林是是有有序树的有序集合。序树的有序集合。南京邮电大学计算机学院南京邮电大学计算机学院5.2 二叉树二叉树南京邮电大学计算机学院南京邮电大学计算机学院 5.2.1二叉树的定义二叉树的定义 二叉树二叉树是结点的有是结点的有限集合，该集合或者为限集合，该集合或者为空集，或者是由一个根空集，或者是由一个根和两棵互不相交的，称和两棵互不相交的，称为该根的左
8、子树和右子为该根的左子树和右子树的二叉树组成。树的二叉树组成。南京邮电大学计算机学院南京邮电大学计算机学院 二叉树的五种根本形态二叉树的五种根本形态 二叉树与树的区别二叉树与树的区别 二叉树可以为空二叉树二叉树可以为空二叉树 二叉树结点的子树分为二叉树结点的子树分为左、右子树左、右子树南京邮电大学计算机学院南京邮电大学计算机学院 5.2.2 二叉树的性质二叉树的性质 二二叉叉树树的的第第i(ii(i 1)1)层层上上至至多多有有2 2i-1i-1 个个结结点。点。 证明：当证明：当i=1i=1时，二叉树只有一个结点，结论时，二叉树只有一个结点，结论成立。成立。 设当设当i=ki=k时结论成立，
9、那么当时结论成立，那么当i=k+1i=k+1时，因为每个结点最多只有两个孩子，所以，时，因为每个结点最多只有两个孩子，所以，第第k+1k+1层上至多有层上至多有 2*2k-1 =2k 2*2k-1 =2k 个结点，性质成立。个结点，性质成立。南京邮电大学计算机学院南京邮电大学计算机学院高度为高度为h的二叉树上至多有的二叉树上至多有2h1个结点。个结点。证证明明：当当h=0时时，二二叉叉树树为为空空二二叉叉树树。当当h0时时，利利用用性性质质51，高高度度为为h的的二二叉叉树树中结点的总数最多为：中结点的总数最多为：南京邮电大学计算机学院南京邮电大学计算机学院包包含含n个个元元素素的的二二叉叉树
10、树的的高高度度至至少少为为 log2(n+1) 证证明明：由由性性质质2，高高度度为为h的的二二叉叉树树最最多多有有2h 1个个 结结 点点 ， 因因 而而 n2h 1, 那那 么么 有有hlog2(n+1)。因因h是是整整数数，所所以以hlog2(n+1)。南京邮电大学计算机学院南京邮电大学计算机学院任任意意一一棵棵二二叉叉树树中中，假假设设叶叶结结点点的的个个数数为为n0，度度为为2的的结结点点的的个个数数为为n2，那那么么必必有有n0=n2+1。证明：设二叉树的结点总数为证明：设二叉树的结点总数为n，那么，那么n=n0+n1+n2孩子数为孩子数为n-1=n1+2n2，因此，因此，n0=n
11、2+1南京邮电大学计算机学院南京邮电大学计算机学院高高度度为为h的的二二叉叉树树恰恰好好有有2h1个个结结点点时时称称为为满二叉树满二叉树。一一棵棵二二叉叉树树中中，只只有有最最下下面面两两层层结结点点的的度度可可以以小小于于2，并并且且最最下下一一层层的的叶叶结结点点集集中中在在靠靠左左的的假假设设干干位位置置上上，这这样样的的二二叉叉树树称称为为完完全二叉树全二叉树。扩扩充充二二叉叉树树也也称称2树树，扩扩充充二二叉叉树树中中除除叶叶子结点外，其余结点都必须有两个孩子。子结点外，其余结点都必须有两个孩子。南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学
12、院具具有有n个个结结点点的的完完全全二二叉叉树树的的高高度度为为 log2(n+1) 。证证明明：设设完完全全二二叉叉树树的的高高度度为为h，那那么么除除最最下下层层外外，前前h-1层层形形成成满满二二叉叉树树，总总共共有有2h-1 1个个结结点点；而而最最下下层层，即即第第h层层的的结结点点个个数数最最多多不超过不超过2h-1个。因此有个。因此有2h-1 1n2h 1移项得移项得2h-1n+12h取对数取对数h-1log2(n+1)hlog2(n+1)hlog2(n+1)+1所以，所以，h=log2(n+1)南京邮电大学计算机学院南京邮电大学计算机学院假假定定对对一一棵棵有有n个个结结点点的
13、的完完全全二二叉叉树树中中的的结结点点，按按从从上上到到下下、从从左左到到右右的的顺顺序序，从从0到到n-1编编号号，设设树树中中某某个个结结点点的的序序号号为为i，0i0，那么该结点的双亲的序号为，那么该结点的双亲的序号为(i-1)/2；南京邮电大学计算机学院南京邮电大学计算机学院3假假设设2i+1n，那那么么该该结结点点的的左左孩孩子子的的序序号为号为2i+1，否那么该结点无左孩子；，否那么该结点无左孩子；(4)假假设设2i+2n，那那么么该该结结点点的的右右孩孩子子的的序序号号为为2i+2，否那么该结点无右孩子。，否那么该结点无右孩子。南京邮电大学计算机学院南京邮电大学计算机学院5.2.
14、3 二叉树二叉树ADTADTBTreeADTBTree数据：数据：数据：数据： 二二二二叉叉叉叉树树树树是是是是结结结结点点点点的的的的有有有有限限限限集集集集合合合合，它它它它或或或或者者者者为为为为空空空空集集集集合合合合，或或或或 者者者者由由由由一一一一个个个个根根根根结结结结点点点点和和和和两两两两棵棵棵棵互互互互不不不不相相相相交交交交的的的的左左左左、右右右右子子子子二二二二叉叉叉叉树组成。树组成。树组成。树组成。运算：运算：运算：运算： Create();Create();构造一棵空二叉树。构造一棵空二叉树。构造一棵空二叉树。构造一棵空二叉树。Destroy()Destroy(
15、)：撤消一棵二叉树。：撤消一棵二叉树。：撤消一棵二叉树。：撤消一棵二叉树。 IsEmpty():IsEmpty():假假假假设设设设二二二二叉叉叉叉树树树树为为为为空空空空，那那那那么么么么返返返返回回回回truetrue，否否否否那么返回那么返回那么返回那么返回falsefalse。Clear():Clear():移去所有结点，成为空二叉树。移去所有结点，成为空二叉树。移去所有结点，成为空二叉树。移去所有结点，成为空二叉树。南京邮电大学计算机学院南京邮电大学计算机学院 Root(x): Root(x): 假假设设二二叉叉树树非非空空，那那么么x x有有根根的的值值，并并返回返回truetru
16、e，否那么返回，否那么返回falsefalse。 MakeTree(x, MakeTree(x, left, left, right): right): 构构造造一一棵棵二二叉叉树树：根的值为根的值为x x，以，以leftleft和和rightright为左右子树。为左右子树。 BreakTree(x, BreakTree(x, left, left, right):right):拆拆分分二二叉叉树树为为三三局局部部：x x为为根根的的值值，leftleft和和rightright分分别别为为原原树树的的左左、右右子子树树 南京邮电大学计算机学院南京邮电大学计算机学院 PreOrder(Vis
17、it):使使用用函函数数Visit访访问问结结点点,先序遍历二叉树。先序遍历二叉树。InOrder(Visit):使使用用函函数数Visit访访问问结结点点,中中序遍历二叉树。序遍历二叉树。PostOrder(Visit):使使用用函函数数Visit访访问问结结点点,后序遍历二叉树。后序遍历二叉树。南京邮电大学计算机学院南京邮电大学计算机学院 5.2.4 二叉树的存储表示二叉树的存储表示 完全二叉树的顺序表示完全二叉树的顺序表示 南京邮电大学计算机学院南京邮电大学计算机学院二叉树的链接表示二叉树的链接表示(二叉链表二叉链表)lChildelementrChild共有共有n-1n-1个指针域非空
18、个指针域非空, ,恰有恰有n+1n+1个空指针域。个空指针域。南京邮电大学计算机学院南京邮电大学计算机学院5.2.5 二叉树类二叉树类程序程序5.1 5.1 二叉树结点类二叉树结点类templatestructBTNodeBTNode()lChild=rChild=NULL;BTNode(constT&x)element=x;lChild=rChild=NULL;南京邮电大学计算机学院南京邮电大学计算机学院BTNode(constT&x,BTNode*l,BTNode*r)element=x;lChild=l;rChild=r;南京邮电大学计算机学院南京邮电大学计算机学院Telement;BT
19、Node*lChild,*rChild;lChildelementrChild南京邮电大学计算机学院南京邮电大学计算机学院程序程序5.2二叉树类二叉树类templateclassBinaryTreepublic:BinaryTree()root=NULL;BinaryTree()Clear();boolIsEmpty()const;voidClear();南京邮电大学计算机学院南京邮电大学计算机学院boolRoot(T&x)const;voidMakeTree(constT&e,BinaryTree&left,BinaryTree&right);voidBreakTree(T&e,Binary
20、Tree&left,BinaryTree&right);voidPreOrder(void(*Visit)(T&x);voidInOrder(void(*Visit)(T&x);voidPostOrder(void(*Visit)(T&x);南京邮电大学计算机学院南京邮电大学计算机学院protected:BTNode*root;root;private:voidClear(BTNode*t);voidPreOrder(void(*Visit)(T&x),BTNode*t);voidInOrder(void(*Visit)(T&x),BTNode*t);voidPostOrder(void(*V
21、isit)(T&x),BTNode*t);南京邮电大学计算机学院南京邮电大学计算机学院 5.2.6 5.2.6 实现二叉树根本运算实现二叉树根本运算 程序程序程序程序5.35.3局部二叉树运算局部二叉树运算局部二叉树运算局部二叉树运算templatetemplateboolBinaryTree:Root(T&x)constboolBinaryTree:Root(T&x)const if(root)if(root)x=root-element;x=root-element;returntrue;returntrue;elsereturnfalse;elsereturnfalse; 南京邮电大学计
22、算机学院南京邮电大学计算机学院templatevoidBinaryTree:MakeTree(constT&x,BinaryTree&left,BinaryTree&right)if(root|&left=&right)return;root=newBTNode(x,);left.root=right.root=NULL;南京邮电大学计算机学院南京邮电大学计算机学院templatevoidBinaryTree:BreakTree(T&x,BinaryTree&left,BinaryTree&right)if(!root|&left=&right|)return;x=root-element;l
23、eft.root=root-lChild;right.root=root-rChild;deleteroot;root=NULL;l南京邮电大学计算机学院南京邮电大学计算机学院voidmain(void)BinaryTreea,b,x,y,z;y.MakeTree(E,a,b);z.MakeTree(F,a,b);x.MakeTree(C,y,z);y.MakeTree(D,a,b);z.MakeTree(B,y,x);z.PreOrder(Visit);z.BreakTree(e,y,x);x.PreOrder(Visit);y.PreOrder(Visit);南京邮电大学计算机学院南京邮电
24、大学计算机学院5.3二叉树遍历二叉树遍历南京邮电大学计算机学院南京邮电大学计算机学院5.3.1二叉树遍历算法二叉树遍历算法遍遍历历一一个个有有限限的的结结点点集集合合，意意味味着着对对该该集集合中的每个结点访问且仅访问一次。合中的每个结点访问且仅访问一次。南京邮电大学计算机学院南京邮电大学计算机学院先序遍先序遍历VLR假假设二二叉叉树为空空，那那么么空空操作；操作；否那么否那么a访问根根结点；点；b先序遍先序遍历左子左子树；c先序遍先序遍历右子右子树。先序遍历结点次序：先序遍历结点次序： B,B, D,D,C,C, E,E, F FA,A,A A A AB B B BC C C CD D D
25、DE E E EF F F F南京邮电大学计算机学院南京邮电大学计算机学院中序遍历中序遍历LVR假设二叉树为空，那么空操作；假设二叉树为空，那么空操作；否那么否那么a中序遍历左子树；中序遍历左子树；b访问根结点；访问根结点；c中序遍历右子树中序遍历右子树中序遍历结点次序：中序遍历结点次序： D,D, A,A,E,E, C,C, F FB,B,南京邮电大学计算机学院南京邮电大学计算机学院后序遍历后序遍历LRV假设二叉树为空，那么空操作；假设二叉树为空，那么空操作；否那么否那么a后序遍历左子树；后序遍历左子树；b后序遍历右子树；后序遍历右子树；c访问根结点。访问根结点。后序遍历结点次序：后序遍历结
26、点次序： B,B, E,E,F,F, C,C, A AD,D,南京邮电大学计算机学院南京邮电大学计算机学院先序：先序：先序：先序：中序：中序：中序：中序：后序：后序：后序：后序：A AD D E E H HF FJ J G G B BC CK KH HE E E E F FG GD D A A B BK KC CH HJ J G G F FE ED D K K C CB BA A南京邮电大学计算机学院南京邮电大学计算机学院层次遍历层次遍历 二二叉叉树树还还可可以以按按层层次次遍遍历历。二二叉叉树树的的层层次次遍遍历历为为：首首先先访访问问第第一一层层上上的的结结点点，再再访访问问第第二二层层上
27、上的的结结点点，依依此此类类推推，访访问问二二叉树上全部结点。叉树上全部结点。 二叉树按层次遍历二叉树按层次遍历: : A,D,B,G,C,H,F,K,J,GA,D,B,G,C,H,F,K,J,G 南京邮电大学计算机学院南京邮电大学计算机学院指向函数的指针变量指向函数的指针变量类型名类型名(*指针变量名指针变量名)参数表参数表例如，例如，void(*Visit)(T&x)定义了一个函数指针参数定义了一个函数指针参数Visit。访问元素函数访问元素函数templatevoidVisit(T&x)coutx;5.3.2 二叉树遍历的递归算法二叉树遍历的递归算法南京邮电大学计算机学院南京邮电大学计算
28、机学院先序遍历先序遍历templatevoidBinaryTree:PreOrder(void(*Visit)(T&x)PreOrder(Visit,root);南京邮电大学计算机学院南京邮电大学计算机学院续续templatevoidBinaryTree:PreOrder(void(*Visit)(T&x),BTNode*t)if(t)Visit(t-element);PreOrder(Visit,t-lChild);PreOrder(Visit,t-rChild);南京邮电大学计算机学院南京邮电大学计算机学院5.3.3二叉树遍历的应用实例二叉树遍历的应用实例求二叉树的结点数求二叉树的结点数t
29、emplateintBinaryTree:Size()returnSize(root);南京邮电大学计算机学院南京邮电大学计算机学院续续templateintBinaryTree:Size(BTNode*t)if(!t)return0;elsereturnSize(t-lChild)+Size(t-rChild)+1;南京邮电大学计算机学院南京邮电大学计算机学院二叉树复制二叉树复制templateBTNode*BinaryTree:Copy(BTNode*t)if(!t)returnNULL;BTNode*q=newBTNode(t-element);q-lChild=Copy(t-lChil
30、d);q-rChild=Copy(t-rChild);returnq;南京邮电大学计算机学院南京邮电大学计算机学院5.5 5.5 树和森林树和森林南京邮电大学计算机学院南京邮电大学计算机学院 5.5.1 5.5.1 森林与二叉树的转换森林与二叉树的转换森林转换成二叉树：将森林中各树的根用森林转换成二叉树：将森林中各树的根用线连起来，在树中，但凡兄弟用线连起来；线连起来，在树中，但凡兄弟用线连起来；去掉从双亲到除了第一个孩子以外的孩子去掉从双亲到除了第一个孩子以外的孩子的连线，只保存双亲到第一个孩子的连线；的连线，只保存双亲到第一个孩子的连线；最后，使之稍微倾斜成习惯的二叉树形。最后，使之稍微倾
31、斜成习惯的二叉树形。其实，这里讨论的森林是指有序森林，也其实，这里讨论的森林是指有序森林，也可将一般的森林视为有序森林来对待。可将一般的森林视为有序森林来对待。 南京邮电大学计算机学院南京邮电大学计算机学院A A A AB B B BC C C CF F F FF F F FD D D DE E E EG G G GH H H HJ J J JA A A AB B B BC C C CF F F FF F F FD D D DE E E EG G G GH H H HJ J J JA A A AB B B BC C C CF F F FF F F FD D D DE E E EG G G GH
32、 H H HJ J J J南京邮电大学计算机学院南京邮电大学计算机学院森林转换成二叉树森林转换成二叉树令令F=T1，T2，Tn是是森森林林，那那么么F所所对应的二叉树对应的二叉树B(F)为：为：1假设假设F为空，那么为空，那么B为空二叉树。为空二叉树。2假假设设F非非空空，那那么么B的的根根是是F中中第第一一棵棵子子树树T1的的根根R1，B的的左左子子树树是是R1的的子子树树森森林林T11，T12，T1m所所对对应应的的二二叉叉树树，B的的右右子子树树是是森森林林T2，Tn所所对对应应的的二二叉树。叉树。南京邮电大学计算机学院南京邮电大学计算机学院二叉树转换成森林二叉树转换成森林令令B=R，L
33、B，RB是是二二叉叉树树，R是是根根，LB是是左左子子树树，RB是是右右子子树树，那那么么B所所对对应应的的森林森林F=T1，T2，Tn为：为：1假设假设B为空，那么为空，那么F为空森林。为空森林。2假假设设B非非空空，那那么么F的的第第一一棵棵树树T1的的根根是是二二叉叉树树的的根根R，T1的的根根的的子子树树森森林林是是B的的左左子子树树LB所所对对应应的的森森林林，F中中的的其其余余树树T2，Tn是是B的右子树的右子树RB所对应的森林。所对应的森林。南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院 5.5.2 树和森林的存储表示树和森林的存储表示
34、多重链表表示法多重链表表示法 设设度度为为m m的的树树中中有有n n个个结结点点, ,总总共共有有n*mn*m个个指指针针域域，其其中中，只只有有n-1n-1个个非非空空指指针针域域，其其余余n*m-(n-1)=n(m-1)+1n*m-(n-1)=n(m-1)+1个指针域均为空。个指针域均为空。 elementelementchildchild1 1childchild2 2childchildm m南京邮电大学计算机学院南京邮电大学计算机学院孩子兄弟表示法孩子兄弟表示法 leftChildelementrightSibling南京邮电大学计算机学院南京邮电大学计算机学院双亲表示法双亲表示法
35、 南京邮电大学计算机学院南京邮电大学计算机学院三重链表表示法三重链表表示法leftChildleftChildelementelementrightSiblingrightSiblingparentparent南京邮电大学计算机学院南京邮电大学计算机学院带右链的先序表示法带右链的先序表示法 南京邮电大学计算机学院南京邮电大学计算机学院5.5.3 树和森林的遍历树和森林的遍历按深度方向的遍历按深度方向的遍历 由由森森林林和和二二叉叉树树的的转转换换方方法法可可知知，森森林林中中第第一一棵棵树树的的根根即即二二叉叉树树的的根根，第第一一棵棵树树的的子子树树组组成成的的森森林林对对应应于于二二叉叉树
36、树的的左左子子树树，而而除除第第一一棵棵树树外外其其余余树树组组成成的的森森林林是是二二叉叉树树的的右右子子树树，所所以以，对对森森林林的的先先序序遍遍历历、中中序序遍遍历历和和后后序序遍遍历历的的结结果果应应与与对对应应二二叉叉树树的的先先序序、中中序序和和后后序序遍遍历历的的结结果果完完全全相相同。同。南京邮电大学计算机学院南京邮电大学计算机学院先序遍历先序遍历 假设森林为空，那么遍历结束，假设森林为空，那么遍历结束， 否那么否那么 a) a) 访问第一棵树的根；访问第一棵树的根； b) b) 按按先先序序遍遍历历第第一一棵棵树树的的根根结结点点的的子树组成的森林；子树组成的森林； c)
37、c) 按按先先序序遍遍历历除除第第一一棵棵树树外外其其余余树树组成的森林。组成的森林。A A, ,B,C,K,D,E,H,F,J,GB,C,K,D,E,H,F,J,G 南京邮电大学计算机学院南京邮电大学计算机学院中序遍历中序遍历 假设森林为空，那么遍历结束，假设森林为空，那么遍历结束， 否否那那么么 a) a) 按按中中序序遍遍历历第第一一棵棵树树的的根根结结点的子树组成的森林；点的子树组成的森林； b) b) 访问第一棵树的根；访问第一棵树的根； c) c) 按按中中序序遍遍历历除除第第一一棵棵树树外外其其余树组成的森林。余树组成的森林。B B, ,K,C,A,H,E,J,F,G,DK,C,
38、A,H,E,J,F,G,D 南京邮电大学计算机学院南京邮电大学计算机学院后序遍历后序遍历假设森林为空，那么遍历结束，假设森林为空，那么遍历结束，否否那那么么a)按按后后序序遍遍历历第第一一棵棵树树的的根根结结点点的的子子树树组组成成的森林；的森林；b)按后序遍历除第一棵树外其余树组成的森林按后序遍历除第一棵树外其余树组成的森林；c访问第一棵树的根。访问第一棵树的根。K K, ,C,BC,B, ,H H,J,G,F,J,G,F,E E,D,D,A A 南京邮电大学计算机学院南京邮电大学计算机学院按宽度方向的遍历按宽度方向的遍历 对对森森林林的的层层次次遍遍历历与与对对应应二二叉叉树树的的层层次次
39、遍历之间没有逻辑的对应关系遍历之间没有逻辑的对应关系 南京邮电大学计算机学院南京邮电大学计算机学院5.6 堆和优先权队列堆和优先权队列 南京邮电大学计算机学院南京邮电大学计算机学院5.6.1堆堆 一一个个大大小小为为n n的的堆堆是是一一棵棵包包含含n n个个结结点点的的完完全全二二叉叉树树，该该树树中中每每个个结结点点的的关关键键字字值值大大于于等等于于其其双双亲亲结结点点的的关关键键字字值值。完完全全二二叉叉树树的的根根称称为为堆堆顶顶，它它的的关关键键字字值值是是整整棵棵树树上上最最小小的的。这这样样定定义义的的堆堆称称为为最最小小堆堆 。还有还有最大堆最大堆 。南京邮电大学计算机学院南
40、京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院堆堆是是n n个个元元素素的的序序列列k0,k1,k0,k1, ,kn-1,kn-1，当当且且仅仅当当满满足足kikik2i+1 k2i+1 且且kiki k2i+2,(i=0,1,k2i+2,(i=0,1, , ,(n-2)/2(n-2)/2) )时时称称为为堆堆( (最小堆最小堆) )。 堆顶元素是序列的第一个元素。堆顶元素是序列的第一个元素。南京邮电大学计算机学院南京邮电大学计算机学院向下调整向下调整voidAdjustDown(Theap,intr,intj)设设heapr+1,heapj这这j-r个个位位置置上上的的元元
41、 素素 已已 满满 足足 特特 性性 ： heapiheap2i+1 且且heapi heap2i+2 (i=r+1,2,(j-1)/2)的的条条件件，运运行行此此函函数数将将使使得得增增加加一一个个元元素素heapr，(heapr,heapr+1,heapj)这这j-r+1个元素也满足堆的特性。个元素也满足堆的特性。南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院templatevoidAdjustDown(Theap,intr,intj)/下标从下标从r+1到到j已满足堆的条件已满足堆的条件intchild=2*r+1;/ /左孩子左孩子左孩子左孩子
42、Ttemp=heapr;while(child=j)if(childheapchild+1)child+;if(temp=heapchild)break;heap(child-1)/2=heapchild;child=2*child+1;heap(child-1)/2=temp;南京邮电大学计算机学院南京邮电大学计算机学院templatevoidCreateHeap(Theap,intn)for(inti=(n-2)/2;i-1;i-)AdjustDown(heap,i,n-1)；n/2-1=3,下标范围：下标范围：3，n-1建堆的时间为建堆的时间为O(nlog2n)。更深入分析可知，更深入分
43、析可知，建堆时间复杂度为建堆时间复杂度为O(n)。南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院5.6.2 优先权队列优先权队列ADTADTPrioQueue数据：数据：n0个元素的最小堆。个元素的最小堆。运算：运算：Create()：建立一个空队列。：建立一个空队列。Destroy()：撤消一个队列。：撤消一个队列。IsEmpty()：假假设设队队列列空空，那那么么返返回回true；否否那那么么返回返回false。IsFull()：假假设设队队列列满满，那那么么返返回回true；否否那那么么返返回回false。南京邮电大学计算机学院南京邮电大学计算机
44、学院 Append(x):元素值为元素值为x的新元素入队列。的新元素入队列。Serve(x):Serve(x):在在x中中返返回回具具有有最最高高优优先先权权的的元元素素值值,并并从优先权队列中删除该元素。从优先权队列中删除该元素。南京邮电大学计算机学院南京邮电大学计算机学院5.6.3 优先权队列类优先权队列类templateclassPrioQueuepublic:PrioQueue(intmSize=20);PrioQueue()deleteq;boolIsEmpty()constreturnn=0;boolIsFull()constreturnn=maxSize;voidAppend(c
45、onstT&x);voidServe(T&x);南京邮电大学计算机学院南京邮电大学计算机学院private:private:voidAdjustDown(intr,intj);voidAdjustUp(intj);T*q;T*q;intn,maxSize;intn,maxSize;南京邮电大学计算机学院南京邮电大学计算机学院templatePrioQueue:PrioQueue(intmSize)maxSize=mSize;n=0;q=newTmaxSize;南京邮电大学计算机学院南京邮电大学计算机学院5.6.4 实现优先权队列实现优先权队列voidAdjustUp(intj)voidAdju
46、stUp(intj)设设设设q0,qj-1q0,qj-1这这这这j j位位位位置置置置上上上上的的的的元元元元素素素素已已已已满满满满足足足足特特特特性性性性：qiqiq2i+1q2i+1 且且且且qiqiq2i+2q2i+2 (i=0,1,(i=0,1, , ,(j-2)/2(j-2)/2) )，运运运运 行行行行 此此此此 函函函函 数数数数 将将将将 使使使使 得得得得 增增增增 加加加加 一一一一 个个个个 元元元元 素素素素 qjqj，(q0,q1,qj)(q0,q1,qj)这这这这j+1j+1个个个个元元元元素素素素也也也也满满满满足足足足堆堆堆堆的的的的特特特特性。性。性。性。南
47、京邮电大学计算机学院南京邮电大学计算机学院templatevoidPrioQueue:AdjustUp(intj)inti=j;Ttemp=qi;while(i0&tempq(i-1)/2)qi=q(i-1)/2;i=(i-1)/2;qi=temp;南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院templatevoidPrioQueue:Append(constT&x)if(IsFull()cout“Overflow;return;qn+=x;AdjustUp(n-1);南京邮电大学计算机学院南京邮电大学计算机学院templatevoidPrioQue
48、ue:Serve(T&x)if(IsEmpty()cout“Underflow;return;x=q0;q0=q-n;AdjustDown(0,n-1);南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院5.7 哈夫曼树和哈夫曼编码哈夫曼树和哈夫曼编码 南京邮电大学计算机学院南京邮电大学计算机学院5.7.1树的路径长度树的路径长度定定义义5.7从从根根到到树树中中任任意意结结点点的的路路径径长长度度是是指指从从根根结结点点到到该该结结点点的的路路径径上上所所包包括括的的边边的的数数目目。树树的的内内路路径径长长度度定定义义为为除除叶叶子子结结点点外外，从从
49、根根到到树树中中其其它它所所有有结结点点的的路路径径长长度度之和。之和。树树的的外外路路径径长长度度是是指指从从根根到到树树中中所所有有叶叶子子结结点的路径长度之和。点的路径长度之和。南京邮电大学计算机学院南京邮电大学计算机学院定定理理5.1 5.1 设设I I和和E E分分别别是是一一棵棵扩扩充充二二叉叉树树的的内内路路径径长长度度和和外外路路径径长长度度，n n是是树树中中非非叶叶结结点点的的数目，那么数目，那么 E EI I2n2n。南京邮电大学计算机学院南京邮电大学计算机学院证明证明：对非叶结点个数：对非叶结点个数n作归纳法证明。作归纳法证明。初始情况初始情况，令，令n=1，I0，E=
50、2，有，有E0+22。归纳假设，归纳假设，非叶结点数为非叶结点数为n-1时该等式成立。时该等式成立。归归纳纳步步骤骤，新新二二叉叉树树的的内内路路径径长长度度为为I-k，外外路路径径长长度度为为E-2(k+1)+k。根根据据归归纳纳假假设设，我我们们有有E-k-2=(I-k)+2(n-1)因而有，因而有，EI2n南京邮电大学计算机学院南京邮电大学计算机学院 定定义义5.8 5.8 树树的的加加权权路路径径长长度度为为树树中中所所有有叶叶子结点的加权路径长度之和，记作子结点的加权路径长度之和，记作 其其中中，m m是是叶叶子子结点点的的个个数数，w wk k是是第第k k个个叶叶子子结点点的的权
51、，l lk k是是从从根根到到该叶叶子子结点点的的路路径径长度。度。南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院 5.7.2 哈夫曼树和哈夫曼算法哈夫曼树和哈夫曼算法 哈夫曼算法哈夫曼算法哈哈夫夫曼曼给给出出了了构构造造具具有有最最小小加加权权路路径径长长度度的的扩扩充充二二叉叉树树的的算算法法，称称为为哈哈夫夫曼曼算算法法。用用哈哈夫夫曼曼算算法法构构造造的的扩扩充充二二叉叉树树称称为为哈哈夫夫曼编码树曼编码树或或哈夫曼树哈夫曼树。南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院 哈夫曼算法哈夫曼算法 1 1
52、用用给给定定的的一一组组权权值值w1,w2 w1,w2 ,wn,wn，生生成成一一个个有有n n棵棵树树组组成成的的森森林林F=T1F=T1，T2T2，TnTn，其其中中，每每棵棵二二叉叉树树TiTi只只有有一一个个结结点点，即即权权值值为为wiwi的根结点也是叶子。的根结点也是叶子。2 2从从F F中中选选择择两两棵棵根根结结点点权权值值最最小小的的树树，作作为为新新树树根根的的左左、右右子子树树，新新树树根根的的权权值值是是左左、右右子子树根结点的权值之和。树根结点的权值之和。3 3从从F F中中删删除除这这两两棵棵树树，另另将将新新二二叉叉树树参参加加F F中。中。4 4重重复复2 2和
53、和3 3，直直到到F F中中只只包包含含一一棵棵树树为止。为止。南京邮电大学计算机学院南京邮电大学计算机学院哈夫曼树类哈夫曼树类templateclassHfmTree:publicBinaryTreepublic:operatorT()constreturnweight;TgetW()returnweight;voidputW(constT&x)weight=x;SetNull()root=NULL;private:Tweight;Tweight;南京邮电大学计算机学院南京邮电大学计算机学院构造哈夫曼树构造哈夫曼树HfmTreeCreateHfmTree(Tw,intn)设设数数组组w中中保
54、保存存n个个元元素素类类型型为为T的的权权值值，函函数返回一棵构造成功的哈夫曼树。数返回一棵构造成功的哈夫曼树。南京邮电大学计算机学院南京邮电大学计算机学院函数函数CreateHfmTree的步骤：的步骤：首首先先构构造造n棵棵哈哈夫夫曼曼树树对对象象，每每棵棵树树只只有有一一个个权权值值为为wi的的根根结结点点，且且该该对对象象的的weight为为wi，将它们逐一参加优先权队列。，将它们逐一参加优先权队列。从从优优先先权权队队列列中中取取出出两两棵棵根根结结点点值值最最小小和和次次最最小小的的哈哈夫夫曼曼树树x和和y。以以它它们们根根的的权权值值之之和和为为根根的的权权值值，x和和y为为左左
55、、右右子子树树构构造造一一棵棵新新哈哈夫夫曼曼树树，并并将将新新树树对对象象进进优优先先权权队队列列。重重复复执执行行n-1次次，此此时时，队队列列中中只只剩剩下下合合并并完完成成的的哈哈夫夫曼树。曼树。从从队队列列中中取取出出构构造造完完毕毕的的哈哈夫夫曼曼树树，函函数数返返回该哈夫曼树。回该哈夫曼树。南京邮电大学计算机学院南京邮电大学计算机学院templateHfmTreeCreateHfmTree(Tw,intn)PrioQueueHfmTreepq(n);/空优先权队列空优先权队列HfmTreex,y,z,zero;/空哈夫曼树空哈夫曼树for(inti=0;in;i+)/构造构造n棵
56、一个结点哈树棵一个结点哈树z.MakeTree(wi,x,y);z.putW(wi);pq.Append(z);z.SetNull();南京邮电大学计算机学院南京邮电大学计算机学院for(i=1;i0)个个元元素素的的集集合合V1,V2,Vm，其其中中V1,V2,Vm是是V的的子子集集，V1 V2 , Vm=V且且Vi Vj=，当当i j，i,j=1,m。运算运算:Create():构构造造每每个个子子集集合合只只包包含含一一个个元元素素的的并并查集查集.Find(i):返回包含元素返回包含元素i的子集合标识的子集合标识Union(x,y):合并子集合并子集x和和y。南京邮电大学计算机学院南京
57、邮电大学计算机学院 5.8.2 并查集的存储表示并查集的存储表示 南京邮电大学计算机学院南京邮电大学计算机学院并查集类并查集类classUFSetclassUFSet public:public:UFSet(intmSize);UFSet()deleteparent;intFind(inti)const;voidUnion(intx,inty);private:int*parent;intsize; ;南京邮电大学计算机学院南京邮电大学计算机学院UFSet:UFSet(intmSize)size=mSize;parent=newintsize;for(inti=0;i=0;i=parenti)
58、;returni;voidUFSet:Union(intx,inty)parentx=y;南京邮电大学计算机学院南京邮电大学计算机学院5.8.5 改进的函数改进的函数Union和和FindintUFSet:Find2(inti)intr,t,l;for(r=i;parentr=0;r=parentr);if(i!=r)for(t=i;parentt!=r;t=l)l=parentt;parentt=r;returnr;南京邮电大学计算机学院南京邮电大学计算机学院voidUFSet:Union2(intx,inty)inttemp=parentx+parenty;if(parentxparent
59、y)/y的结点多，的结点多，x链至链至yparentx=y;parenty=temp;elseparenty=x;parentx=temp;对对一一个个有有n个个元元素素的的并并查查集集，可可以以证证明明当当采采用用改改进进的的Union算算 法法 后后 ， 每每 棵棵 树树 的的 高高 度度 将将 不不 超超 过过log2n+1。南京邮电大学计算机学院南京邮电大学计算机学院5.8.6按等价关系分组按等价关系分组设有元素集合设有元素集合S=0,1,2,3,4,5,6，它们用序号，它们用序号惟一标识。惟一标识。S上有等价对上有等价对R=01，23，30，45，65。该等价关系将集合。该等价关系将集合S分成两分成两个等价类：个等价类：0，1，2，3和和4，5，6。 南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院南京邮电大学计算机学院
