程序设计技术 第五章 树形结构

1程序设计技术第五章树形结构2第三部分树形结构树的概念和基本术语二叉树树的二叉树表示二叉树遍历树的遍历霍夫曼树3树的概念和基本术语树的定义树是由n(n0)个结点的有限集合。如果n=0，称为空树；如果n0，则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n1，除根以外的其它结点划分为m(m0)个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。4ACGBDEFKLHMIJ例如A只有根结点的树有13个结点的树其中：A是根；其余结点分成三个互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树5树的基本术语1层2层4层3层height=4ACGBDEFKLHMIJ6二叉树(BinaryTree)定义五种形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。LLRR特点每个结点至多只有两棵子树（二叉树中不存在度大于2的结点）7性质1在二叉树的第i层上至多有2i－1个结点。(i1)[证明用归纳法]性质2深度为k的二叉树至多有2k-1个结点(k1)。性质3对任何一棵二叉树T,如果其叶结点数为n0,度为2的结点数为n2,则n0＝n2＋1.性质8定义1满二叉树(FullBinaryTree)一棵深度为k且有2k-1个结点的二叉树称为满二叉树。两种特殊形态的二叉树621754389101113141512满二叉树92154367216543非完全二叉树定义2完全二叉树(CompleteBinaryTree)若设二叉树的高度为h，则共有h层。除第h层外，其它各层(1h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。621754389101112完全二叉树10完全二叉树一般二叉树的顺序表示的顺序表示二叉树的存储结构112345678910912340567800910248910567312365478顺序表示91011链表表示lChilddatarChilddatalChildrChild二叉链表含两个指针域的结点结构lChilddataparentrChild含三个指针域的结点结构parentdatalChildrChild三叉链表12二叉树链表表示的示例AAABBBCCCDDDFFFEEErootrootroot二叉树二叉链表三叉链表13typedefcharTreeData;//结点数据类型typedefstructnode{//结点定义TreeDatadata;structnode*leftChild,*rightchild;}BinTreeNode;typedefBinTreeNode*BinTree;//根指针二叉链表的定义14结点结构datafirstChildnextSiblingABCDEFG空链域n+1个树的左子女-右兄弟表示（二叉链表表示）BCDGFEA树的二叉树表示15树的二叉树表示:ABCDEFGABCEDGF16T1T2T3T1T2T3AFHBCDGIJEKAFBCDEGHIKJABCEDHIKJFG3棵树的森林各棵树的二叉树表示森林的二叉树表示森林与二叉树的转换17二叉树遍历树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作V遍历根的左子树记作L遍历根的右子树记作R则可能的遍历次序有前序VLR中序LVR后序LRVVLR18中序遍历二叉树算法的定义：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果a+b*c-d-e/f中序遍历(InorderTraversal)--/+*abcdef19前序遍历二叉树算法的定义：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。遍历结果-+a*b-cd/ef前序遍历(PreorderTraversal)--/+*abcdef20后序遍历二叉树算法的定义：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果abcd-*+ef/-后序遍历(PostorderTraversal)--/+*abcdef21树的遍历深度优先遍历先根次序遍历后根次序遍历22深度优先遍历当树非空时访问根结点依次先根遍历根的各棵子树树先根遍历ABEFCDG对应二叉树前序遍历ABEFCDG树的先根遍历结果与其对应二叉树表示的前序遍历结果相同树的先根遍历可以借助对应二叉树的前序遍历算法实现ABCEDGF树的先根次序遍历ABCDEFG23树的后根次序遍历:当树非空时依次后根遍历根的各棵子树访问根结点树后根遍历EFBCGDA对应二叉树中序遍历EFBCGDA树的后根遍历结果与其对应二叉树表示的中序遍历结果相同树的后根遍历可以借助对应二叉树的中序遍历算法实现ABCEDGFABCDEFG24霍夫曼树(HuffmanTree)路径长度(PathLength)两个结点之间的路径长度PL是连接两结点的路径上的分支数。树的外部路径长度是各叶结点(外结点)到根结点的路径长度之和EPL。树的内部路径长度是各非叶结点(内结点)到根结点的路径长度之和IPL。树的路径长度PL=EPL+IPL25123456782345678树的外部路径长度EPL=3*1+2*3=9树的外部路径长度EPL=1*1+2*1+3*1+4*1=10126带权路径长度(WeightedPathLength,WPL)二叉树的带权(外部)路径长度是树的各叶结点所带的权值wi与该结点到根的路径长度li的乘积的和。10niiilwWPL27WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=367*3=464*3=3522244455577728霍夫曼树带权路径长度达到最小的二叉树即为霍夫曼树。在霍夫曼树中，权值大的结点离根最近。(1)由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵扩充二叉树的森林F={T0,T1,T2,…,Tn-1}，其中每棵扩充二叉树Ti只有一个带权值wi的根结点,其左、右子树均为空。霍夫曼算法29(2)重复以下步骤,直到F中仅剩下一棵树为止：①在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。30F:{7}{5}{2}{4}F:{7}{5}{6}F:{7}{11}7524初始合并{2}{4}75246F:{18}1175246合并{5}{6}5合并{7}{11}27461118举例霍夫曼树的构造过程315274WeightparentleftChildrightChild7-1-1-15-1-1-12-1-1-14-1-1-1-1-1-1-1-1-1-1-1-10123456上例存储结构初态3252746WeightparentleftChildrightChild7-1-1-15-1-1-12-1-1-14-1-1-16-1-1-1-1-1-1-1-1-10123456p1p24423i过程335274611WeightparentleftChildrightChild7-1-1-15-1-1-124-1-144-1-16-12311-1-1-1-1-1-10123456p1p25514i345274611WeightparentleftChildrightChild7-1-1-155-1-124-1-144-1-1652311-11418-1-1-10123456p1p26605i18终态35霍夫曼编码主要用途是实现数据压缩。设给出一段报文：CASTCASTSATATATASA字符集合是{C,A,S,T}，各个字符出现的频度(次数)是W＝{2,7,4,5}。若给每个字符以等长编码A:00T:10C:01S:11则总编码长度为(2+7+4+5)*2=36.36若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为{2/18,7/18,4/18,5/18},化整为{2,7,4,5}。以它们为各叶结点上的权值,建立霍夫曼树。左分支赋0，右分支赋1，得霍夫曼编码(变长编码)。7254010011ACTS37A:0T:10C:110S:111它的总编码长度：7*1+5*2+(2+4)*3=35。比等长编码的情形要短。总编码长度正好等于霍夫曼树的带权路径长度WPL。霍夫曼编码是一种无前缀编码。解码时不会混淆。霍夫曼编码树0001112457