树和二叉树PPT演示课件

第六章,树和二叉树,1,6.6赫夫曼树及其应用,6.1树的定义和基本术语,6.2二叉树,6.3遍历二叉树和线索二叉树,6.4树和森林,2,6.4树和森林,6.4.1树的存储结构,6.4.2森林与二叉树的转换,6.4.3树和森林的遍历,3,6.4.1树的存储结构,一、双亲表示法,二、孩子链表表示法,三、孩子兄弟存储表示法,4,r=0n=7,dataparent,一、双亲表示法:,5,typedefstructPTNodeElemTypedata;intparent;/双亲位置域PTNode;,#defineMAX_TREE_SIZE100,结点结构:,C语言的类型描述:,6,typedefstructPTNodenodesMAX_TREE_SIZE;intr,n;/根结点的位置和结点个数PTree;,树结构:,7,第一种解决方案,二、孩子(链表)表示法:,其中d是结点的度;由于每个结点的子女个数是不限制的,则如按照度最大的结点的度分配子女指针的个数,则在实际应用中,会有很多空指针域,造成空间的浪费。,8,r=0n=7,datafirstchild,第二种解决方案,9,typedefstructCTNodeintchild;structCTNode*next;*ChildPtr;,孩子结点结构:,C语言的类型描述:,10,typedefstructElemTypedata;ChildPtrfirstchild;/孩子链的头指针CTBox;,双亲结点结构,11,typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根结点的位置CTree;,树结构:,12,root,三、树的孩子-兄弟(二叉链表)表示法,13,14,typedefstructCSNodeElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,C语言的类型描述:,结点结构:,15,6.4.2森林与二叉树的转换,设森林F=(T1,T2,Tn);T1=(root，t11,t12,t1m);,二叉树B=(LBT,Node(root),RBT);,16,由森林转换成二叉树的转换规则为:,若F=，则B=;,由ROOT(T1)对应得到Node(root);,否则，,由(t11,t12,t1m)对应得到LBT;,由(T2,T3,Tn)对应得到RBT。,17,T1,T2,Tn,18,顺时针旋转45度。以根结点为轴；左孩子不再旋转。,树(森林)转化成二叉树的简单方法,在亲兄弟之间加连线；,保留结点与第一个孩子之间的连线，去掉与其余孩子之间连线；,19,T1T2T3,各棵树的二叉树表示,20,由二叉树转换为森林的转换规则为:,由LBT对应得到(t11,t12,，t1m);,若B=,则F=;,否则，,由Node(root)对应得到ROOT(T1);,由RBT对应得到(T2,T3,Tn)。,21,二叉树转化成树(森林)的简单方法,若某结点是其双亲的左孩子，则将该结点的双亲同该结点的右孩子、右孩子的右孩子、右孩子的右孩子的右孩子加连线；,去掉所有双亲与右孩子之间的连线。,22,T1T2T3,23,由此，树和森林的各种操作均可与二叉树的各种操作相对应。,应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟,24,6.4.3树和森林的遍历,25,一、树的遍历,二、森林的遍历,26,树的遍历:,先根(次序)遍历:,后根(次序)遍历:,若树不空，则先访问根结点，然后依次按先根遍历各棵子树。,若树不空，则先依次按后根遍历各棵子树，然后访问根结点。,27,先根遍历时结点的访问次序：,ABEFCDGHIJK,后根遍历时结点的访问次序：,EFBCIJKHGDA,28,1.森林中第一棵树的根结点；,2.森林中第一棵树的子树森林；,3.森林中其它树构成的森林。,可以分解成三部分：,森林,29,若森林不空，则访问森林中第一棵树的根结点;先序遍历森林中第一棵树的子树森林;先序遍历森林中(除第一棵树之外)其余树构成的森林。,先序遍历,森林的遍历,即：依次从左至右对森林中的每一棵树进行先根遍历。,30,中序遍历,若森林不空，则中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;中序遍历森林中(除第一棵树之外)其余树构成的森林。,即：依次从左至右对森林中的每一棵树进行后根遍历。,31,树的遍历和二叉树遍历的对应关系？,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,32,设树的存储结构为孩子兄弟链表,typedefstructCSNodeElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,一、求树的深度,二、输出树中所有从根到叶子的路径,三、建树的存储结构,33,IntDepth(CSTreeT)If(T=NULL)return0;ElseD1=Depth(T-firstchild);D2=Depth(T-nextsibling);ReturnMaxd1+1,d2,34,intTreeDepth(CTreeT)/T是树的孩子链表存储结构，/返回该树的深度if(T.n=0)return0;elsereturnDepth(T,T.r);/TreeDepth,一、求树的深度的算法：,35,intDepth(CTreeT,introot)max=0;p=T.nodesroot.firstchild;while(p)h=Depth(T,p-child);if(hmax)max=h;p=p-nextchild;/whilereturnmax+1;,36,二、输出树中所有从根到叶子的路径的算法:,例如：对左图所示的树，其输出结果应为：,ABEABFACADGHIADGHJADGHK,37,voidAllPath(BiTreeT,Stack/if(T)/AllPath,/输出二叉树上从根到所有叶子结点的路径,38,voidOutPath(BitreeT,Stack/while/OutPath,/输出森林中所有从根到叶的路径,39,40,三、建树的存储结构的算法:,和二叉树类似，不同的定义相应有不同的算法。,假设以二元组(F,C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。,41,A,B,C,D,E,F,G,例如:,对下列所示树的输入序列应为:,(#,A)(A,B)(A,C)(A,D)(C,E)(C,F)(E,G),A,B,C,D,(#,A),(A,B),(A,C),(A,D),(C,E),可见，算法中需要一个队列保存已建好的结点的指针,42,voidCreatTree(CSTree/所建为根结点else/非根结点的情况/for/CreateTree,43,GetHead(Q,s);/取队列头元素(指针值)while(s-data!=fa)/查询双亲结点DeQueue(Q,s);GetHead(Q,s);if(!(s-firstchild)s-firstchild=p;r=p;/链接第一个孩子结点elser-nextsibling=p;r=p;/链接其它孩子结点,44,6.6赫夫曼树及其应用,6.6.2赫夫曼编码,6.6.1最优二叉树(赫夫曼树),45,6.6.1最优二叉树（赫夫曼树）,树的路径长度定义为：从树根到每个结点的路径长度之和。,路径长度定义为：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目叫做路径长度。,46,树的带权路径长度定义为：树的带权路径长度是树的各叶子结点所带的权值与该结点到根的路径长度的乘积的和。WPL(T)=wklk(对所有叶子结点),在所有含n个叶子结点、并带相同权值的二叉树中，必存在一棵其带权路径长度取最小值的二叉树，称为最优二叉树或赫夫曼树。,例如：,47,2,79,7,5,4,9,2,WPL(T)=72+52+23+43+92=60,WPL(T)=74+94+53+42+21=89,5,4,48,具有不同带权路径长度的扩充二叉树,WPL=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=35带权路径长度达到最小,2,2,2,4,4,4,5,5,5,7,7,7,在赫夫曼树中，权值大的结点离根最近。,49,根据给定的n个权值w1,w2,wn，构造n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;,如何构造赫夫曼树,(1),50,在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;,(2),51,从F中删去这两棵树，同时加入刚生成的新树;,重复(2)和(3)两步，直至F中只含一棵树为止。,(3),(4),这棵树便是赫夫曼树,52,9,例如:已知权值W=5,6,2,9,7,5,6,2,7,5,2,7,6,9,7,6,7,13,9,(1),(2),(3),53,9,9,16,(4),(3),54,9,16,29,(5),55,F:7524,F:756,7,5,2,4,初始,合并24,F:711,7,5,2,4,7,5,2,4,6,6,11,合并56,F:18,5,合并56,2,7,4,6,11,18,56,6.6.2赫夫曼编码,在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。,57,1.等长编码这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。,58,2.不等长编码在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。,59,前缀编码:任何一个字符的编码都不是另一个字符的编码的前缀。,利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。,60,主要用途是实现数据压缩。设给出一段报文：CASTCASTSATATATASA字符集合是C,A,S,T，各个字符出现的频度(次数)是W2,7,4,5。若给每个字符以等长编码A:00T:10C:01S:11则总编码长度为(2+7+4+5)*2=36.若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。因各字符出现的概率为2/18,7/18,4/18,5/18。,61,化整为2,7,4,5，以它们为各叶子结点上的权值，建立赫夫曼树。左分支赋0，右分支赋1，得赫夫曼编码(变长编码)。A:0T:10C:110S:111它的总编码长度：7*1+5*2+(2+4)*3=35。比等长编码的情形要短。总编码长度正好等于赫夫曼树的带权路径长度WPL。赫夫曼编码是一种无前缀的编码。解码时不会混淆。,赫夫曼编码树,62,9,16,29,0,0,0,0,1,1,1,1,00,01,11,100,101,63,typedefstructunsignedintweight;unsignedintparent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedefchar*HuffmanCode;/动态分配数组存储赫夫曼编码表/串数组类型,赫夫曼树和赫夫曼编码的存储表示,64,voidHuffmanCoding(HuffmanTree/0号单元未用,求赫夫曼编码的算法算法6.12P147,65,for(p=HT,i=1;i=n;+i,+p,+w)*p=*w,0,0,0;for(;i=m;+i,+p)*p=0,0,0,0;for(i=n+1;i=m;+i)/建赫夫曼树/在HT1.i-1选择parent为0且weight最小的两个结点,/其序号分别为s1和s2。Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;,66,/从叶子到根逆向求赫夫曼编码HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char