数据结构之树和二叉树的应用.doc

个人收集整理 勿做商业用途第六章 树和二叉树的应用6。1二叉排序树和平衡二叉树在实际应用中,常常需要在一组记录中检索一个记录,向其中插入一个记录或者把找到的记录删除。如果记录无序，查找起来将会很慢。如果记录有序，查找将会很快。但是遇到动态增减变化时，需要移动大量的元素。即使使用链表结构，查找起来也相当麻烦。非常需要一中插入、删除、和检索记录效率都很高的数据组织方法。二叉排序（查找、搜索）树就是这样一种高效的数据结构.5842987090634555836710图6.1 二叉排序树6.1.1二叉排序树的基本概念二叉排序树也称二叉查找树或二叉搜索树。它或者是一棵空树;或者有性质:（1）若其左子树不空，则左子树上所有结点的值均小于根结点的值.(2）若其右子树不空，则右子树上所有结点的值均大于根结点的值。（3）左右子树也为二叉排序树.图5.21就是一棵二叉排序树。二叉排序树通常采用二叉链存储结构。二叉链存储结构的结点类型定义：typedefstructtnodeKeyTypekey;/关键字域ElemTypedata；/其他数据域structtnodelchild，*rchild；/指针BSTNode；中序遍历二叉排序树可以得到有序序列。6.1.2二叉排序树的基本运算二叉排序树的基本运算如下：1.BSTSearch(bt,k）在二叉排序树bt中,查找值为k的结点。2。BSTInsert(bt，k)在二叉排序树bt中，插入值为k的结点。3.CreateBST(bt,str,n)创建二叉排序树4。输出二叉排序树DispBST(bt)5.删除结点BSTDelete(bt，k)1。查找结点BSTSearch（bt,k)方法:将给定值k与查找树的根结点关键码比较.若相等，查找成功，结束查找过程。否则，a当给k小于根结点关键码，查找将在以左子女为根的子树上继续进行；b当给k大于根结点关键码,查找将在以右子女为根的子树上继续进行；c若K等于当前结点的关键字，则返回；如此反复，直至找到或子树为空，查找失败时为止。例如，查找图5.21中关键字等于45的结点。从根结点开始比较。4570，在右子树中查找;7383，在左子树中查找;5。83的左子树为空，查找失败。所以稽核中不含关键字等于73的结点。查找二叉排序树的算法BSTNodeBSTSearch(BSTNode*bt,KeyTypek）BSTNode*p=bt;while（p!=NULLp-key!=k）if(kkey)p=plchild；/沿左子树查找/elsep=p-rchild；/*沿右子树查找/If（p!=NULL)return（p);elseprintf（“找不到”)；2。二叉排序树的插入BSTInsert（bt,k）向二叉排序树中插入一个结点的过程：设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找,若查找成功，按二叉排序树定义，待插入结点已存在，不用插入;查找不成功时,则插入之.因此，新插入结点一定是作为叶子结点添加上去的。例如:记录的关键码序列为：63，90，70，55，67，42，98，83，10，45，58,则构造一棵二叉排序树的过程如图5。22所示：709063556742987090635567427090635567709063557090636390635842987090634555836710429870906345558367107090635567839810427090635567839842图6.2 构造二叉排序树插入算法：intBSTInsert(BSTNode*&bt,KeyTypek)BSTNode*f,p=bt;while（p!=NULL)if（pkey=k)return（0）；f=p;/f指向p结点的双亲结点/if（pkeyk）p=plchild;/k小，在左子树查找*/elsep=prchild;/否则在右子树找/p=（BSTNode*)malloc（sizeof(BSTNode)）；pkey=k;p-lchild=p-rchild=NULL；if（bt=NULL）bt=p;elseif（kfkey）f-lchild=p;elsefrchild=p；return(1)；3.二叉排序树的构造CreateBST(bt，str，n)上例说明，构造一棵二叉排序树则是从空树出发逐个插入结点的过程。创建算法:voidCreateBST(BSTNode*bt,KeyTypestr,intn)bt=NULL；/初始时bt为空树/inti=0;while(ilchild)；if(btrchild!=NULL)printf(”,”)；DispBST（btrchild）；printf（)；5。二叉排序树的删除BSTDelete(bt,k)设p是f的左孩子，p左、右子树为pL、pR,pR中序最右结点为S，S的中序前驱为Q。（1)若*p为叶子结点，则修改*f的对应指针为空。(2)若*p只有1棵子树，则用子树替代p。（3)若p左右子树均不空。可以有两种做法：a。令*p的左子树替代*p，而把p的右子树作为*s的右子树。b.令p的直接前驱（或直接后继）替代p，然后再从二叉排序树中删去他的直接前驱（或直接后继）。当以直接前驱s替代p时，由于s只有左子树,则在删去s之后，只要令SL为s的双亲*q的右子树即可。删除算法:intBSTDelete(BSTNode*&bt，KeyTypek)BSTNodep=bt,*f，*r,f1；f=NULL；/p指向待比较的结点,f指向p的双亲结点*/while(p！=NULL&p-key!=k)/*查找值域为x的结点/f=p；if（p-keyk）p=p-lchild;/*在左子树中查找/elsep=p-rchild;/*在右子树中查找/if（p=NULL)/*未找到key域为k的结点*/图图6.3从二叉排序树中删除元素return（0）；elseif(p-lchild=NULL）/p为被删结点,若它无左子树*/if(f=NULL)/p是根结点，则用右孩子替换它/bt=prchild;elseif(f-lchild=p）/*p是双亲结点的左孩子，则用其右孩子替换它*/flchild=prchild；free（p);elseif（f-rchild=p)/*p是双亲结点的右孩子,则用其右孩子替换它/frchild=p-rchild;free（p）;elseif（p-rchild=NULL）/*p为被删结点，若它无右子树/if(f=NULL)/*p是根结点，则用左孩子替换它/bt=p-lchild；if（f-lchild=p)/p是双亲结点的左孩子，则用其左孩子替换它/flchild=plchild;free（p);elseif（frchild=p)/*p是双亲结点的右孩子，则用其左孩子替换它*/frchild=plchild;free（p）；else/*p为被删结点，若它有左子树和右子树/f1=p;r=p-lchild;/*查找*p的左子树中的最右下结点r/while（rrchild!=NULL)/r一定是无右子树的结点,*f1作为r的双亲*/f1=r;r=rrchild；if（f1-lchild=r）/r是f1的左孩子,删除*r*/f1-lchild=rrchild;elseif(f1rchild=r）/*r是f1的右孩子，删除*r*/f1-rchild=r-lchild；rlchild=p-lchild;/*以下语句是用*r替代*p*/rrchild=p-rchild；if(f=NULL）/*f为根结点*/bt=r；/*被删结点是根结点*/elseif(f-lchild=p)/*p是*f的左孩子*/flchild=r;else/p是*f的右孩子*/f-rchild=r;free（p）;return(1）;从图6.2生成的二叉排序树中删除10，83，70，55的过程如图6.4所示：4258987090634555674258986790634555842987090634555836710删除70，55删除10，83图6。4 从二叉排序树中删除元素示例二叉排序树是一种动态结构，它的运算大都是基于查找运算，查找的次数与树的深度（层数)有关。这样，有n个结点的二叉排序树的平均查找长度就和树的形态有关。如果形态为或接近完全二叉树，则其平均查找次数的数量级为log2n,如果给出的n个关键字的值是有序的，则顺序插入的二叉排序树就蜕变为单支树,深度为n，平均查找长度为。6。1.3平衡二叉排序树(AVL树)二叉排序树在最好情况下的查找时间复杂度只需O(logn)，而在最坏情况下（有序)的查找时间复杂度却需O（n),所以为了提高效率，在生成二叉排序树的过程中，应该进行平衡化处理，使得左右两边尽量均衡。基于这种想法，AdelsonVelskii和Landis发明了AVL树（二者姓氏首字母）,这就是平衡二叉树.1.平衡二叉树的定义平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：（1） 它的左子树和右子树都是平衡二叉树；（2） 左子树和右子树高度之差的绝对值不超过1。若把左子树与右子树高度之差称为结点x的平衡因子（balance factor)，用bf(x)表示。则由平衡二叉树定义知Bf(x)=x的左子树的深度x右子树的深度显然，所有结点的平衡因子只能取1，0,1三个值之一.若二叉排序树中存在平衡因子的绝对值大于1的结点，这棵二叉排序树就不是平衡二叉树.如图6。5所示。91000065504741853060727842-330-202141853060727842-1110010a.非平衡二叉树 b.平衡二叉树图6。5非平衡和平衡二叉树举例2。平衡化调整在平衡二叉树上插入或删除结点后，可能使树失去平衡，因此，需要对失去平衡的树进行平衡化调整.好比用一根扁担挑物，出现一头略重(有时是难免的），可以用手调整.如果相差太多,就得调整支点，前重，支点前移,后重，指点后移。同样,为了恢复二叉排序树的平衡，也需要移动不平衡二叉排序树的结点位置。为此作如下分析：-2Fh-1h-1GEbca需要调整的不平衡而察排序树只能由如下的4种情况:1ahxhBDcEh+11211hDbh-1GcFh-1hEax2-1-2xBhaEcDhh+1-1-1Dhhx(a) LL不平衡 (b) LR不平衡 （c) RL不平衡 d) RR不平衡图6.6 AVL树的不平衡类型4种类型依次表示导致不平衡结点一次位于A的左子树的左子树、左子树的右子树、右子树的左子树、右子树的右子树中。平衡因子不为0的用圆表示，属结点;否则用长条表示，属于树。对于这4种的调整办法，绝大多数教材采用左旋转、先左后右双旋转、先有后座双旋转和右旋转的方法。我们改用一个我们认为更好理解记忆的方法。这方法是:（1） 去掉结点分支；（2） 从左到右排序;（3） 向重端仪结点作为新结点；（4） 重组调整为平衡儿茶排序树。图6。7是这种新调整方法的过程示意。E2ahxhBDch+111-2xBhaEcDhh+1-1E1bh-1GchaFh-1x2-1DhxFh-1h-1GhDhEbca-1-21E c D a B D b F c G a E E a F c G b D B a D c ExahhBDcEh+11xcahBhDh+11ExcbahEFh-1xh-1GDh1DEx-1bh-1GcFh-1hah图6.7 AVL树的不平衡类型的调整过程例如，依次插入关键字序列（13，24，37,90,53）。生成和调整的过程如图6。8所示。删除的过程，与上一节一样,只是注意随时调整即可,就不再赘述了。13131324242437371313243790531324379053(a)空树 (b)插入13 (c)插入24 (d)插入37，不平衡 (e)把中间值24做根(f)相继插入90和53，不平衡 (g)37,90,53的中间值53做根，左37，右90图6.8 二叉平衡术的生成过程-2-21-1-1-1000000000000 6。2堆和堆排序平衡二叉树虽然两边比较均衡，接近完全二叉树，效率比较高。但是毕竟不是完全二叉树，效率还不是最高。由于求最大最小的问题比较常用，事实上解决了最大最小问题也等于解决了排序问题。所以我们引进了一个解决最大最小及排序问题的基于完全二叉树的结构，它就是堆.6.2。1堆的定义堆是每个非终端结点的关键字均不大（小）于它的孩子结点的关键字的完全二叉树。可以描述为：把n个元素的序列k1,k2,，kn，存储到一棵完全二叉树中,且使所有非叶结点的值均不大于(或不小于）其子女的值,根结点的值是最小（或最大）的。显然，堆顶结点具有最大（小）关键字值，非空左、右子树都是一个堆。我们把堆顶点具有最大值的堆叫做大顶堆;把堆顶点具有最小值的堆叫做小顶堆。图6.9就是大顶堆和小顶堆的例子。47852436305391163624854753301291kik2ikik2i+11. Kik2ikik2i+12. i=1，2，n/2图6。9两个堆示例6.2。2堆排序设有n个元素，将其按关键码排序。首先将这n个元素按关键码建成堆,将堆顶元素输出，得到n个元素中关键码最小(或最大)的元素。然后，再对剩下的n1个元素建成堆，输出堆顶元素，得到n个元素中关键码次小（或次大)的元素。如此反复，便得到一个按关键码有序的序列.称这个过程为堆排序。因此，实现堆排序需解决两个问题：（1)如何将n个元素的序列按关键码建成堆；(2）输出堆顶元素后，怎样调整剩余n1个元素,使其按关键码成为一个新堆.更明确地用计算机术语描述，堆排序的基本思想:（1）首先把待排序的顺序表(R1，R2，,Rn)依次填入一棵有n个结点的完全二叉树，并将它转换成一个堆。（2)这时，根结点具有最大(小）值。把根结点与最后一个结点对调，删去最后一个结点，输出；然后将剩下的结点重新调整为一个堆。反复进行（2），直到只剩下一个结点为止。1.把一棵完全二叉树调整为一个堆需要经过多次调整才能把它转换成一个堆,这个堆叫做初始堆.生成初始队的过程叫建堆。当然，首要的任务是把待排序的顺序表(R1，R2，,Rn）依次填入一棵有n个结点的完全二叉树中，然后建堆.建堆方法是：从n/2开始，与其孩子节点比较。若比两个孩子节点之都小(大）,不必调整；否则与较小（大）的一个孩子交换。换下来的结点也要比较，如果不是堆,也要交换。直到以这个结点为根的完全二叉树成为堆。称这个自根结点到叶子结点的调整过程为筛选。之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。例如：把无序序列(53，36，30，91，47，12,24，85）建成小顶堆。如图6.10所示.3630914724125385a.8个结点的初始状态3630914724125385b.从第4个结点开始筛选9185,交换3630854724125391c.对第3个结点开始 筛选3012，交换3612854724305391d.第2个结点为根的 子树已是堆 36128547243053913653854724301291e.对整棵树进行筛选 5312,交换,5324,交换图6。10 建堆示例2.把删除根后的堆调整为新堆由于堆的根结点应具有最小（大)值，且左、右子树是堆，因此，新堆的根结点应是左、右孩子(若存在的话）中的一个结点。因此，删除根结点时只需将其与最后一个结点交换，再删除最后一个然后只对根交换后的结点按上述方法调整即可。调整方法：设有m个元素的堆，输出堆顶元素后，剩下m1个元素。将堆底元素送入堆顶，堆被破坏，其原因仅是根结点不满足堆的性质。将根结点与左、右子女中较小（或小大)的进行交换.这一子堆可能被破坏,且仅这一子堆可能被破坏.继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。如图6。11所示.36248547533012918547533091913685475330243036854724539124a. 输出堆顶12,将 堆低91送入堆顶36d。堆已建成c。右子树不满足堆， 其根与左子女交换b。堆被破坏，根结 点与右子女交换图6.11自堆顶到叶子的调整过程3.堆排序对n个元素的序列进行堆排序，先将其建成堆，以根结点与第n个结点交换；调整前n-1个结点成为堆，再以根结点与第n1个结点交换；重复上述操作，直到整个序列有序。堆排序算法：rsm中的记录关键码除rs外均满足堆的定义,本函数将对第s个结点为根的子树筛选，使其成为大顶堆voidHeapAdjust(S_TBL*h，ints，intm)rc=h-rs；for（j=2*s;j=m；j=j2)/沿关键码较大的子女结点向下筛选*/if（jmh-rj。keyh-rj+1。key）j=j+1；/*为关键码较大的元素下标*/if（rc。keyrj。key）break；/*rc应插入在位置s上*/hrs=hrj;s=j；/*使s结点满足堆定义*/hrs=rc；/*插入/voidHeapSort（S_TBLh）for(i=h-length/2；i0；i-）/将r1.。length建成堆/HeapAdjust（h，i,h-length)；for（i=hlength；i1；i-)h-r1hri；/*堆顶与堆低元素交换*/HeapAdjust（h，1,i1)；/将r1.。i1重新调整为堆*/效率分析：次，交换记录至多k次.所以,在建好堆后，排序过程中的筛选次数不超过下式:2（log2（n-1）+log2（n-2）+log22)2nlog2n而建堆时的比较次数不超过4n次，因此堆排序最坏情况下,时间复杂度也为O（nlog2n)。6.3赫(哈)夫曼树及其应用赫（哈)夫曼(Huffman)树又称最优树,是一种带权路径长度最短的树,在优化程序、缩短编码等方面都有着广泛的应用。6.3。1最优二叉树（赫夫曼)树要完成一个功能，可以有多种方法，各方法的效率是不同的。例如，要编制一个将百分制转换为五级分制的程序。显然，此程序很简单，只要利用条件语句便可完成。如判定过程可以图6.12(a)、（b）所示,如果上述程序需反复使用，而且每次的输入量很大,假定个分数段出现的比例不等（如图6.12（c）所示表的比例数列)，输入数量假定为10000个,则两种方案需要比较判断的总次数如图6.12（c）的表：（a）方案1 （b)房案2 （c）两种方案比较次数表图6。12百分制转化为五级分治的方案及次数计算从上面的图标中不难看出，五级分的结果相当于树的叶子结点,每次运算需要比较的次数恰好等于它的路径长度，假定处于这一分数段的记录数等于这一分数段的比例数与总数的乘积,将它称为权值的话，那么，处理这一分数段的记录需要比较的次数应为路径长度与权值的乘积,从而每一方案的总比较次数应是个分数段的路径长度与权值之积之和。按照这一算法得出:按方案1的判定过程进行操作，则总共需进行31500次比较;而按方案21的判定过程进行操作，则总共仅需进行22000次比较。节省了30.16的工作量。把这一问题引伸，就提出了赫（哈）夫曼殊的概念。1.树的带权路径长度的概念和计算前面我们介绍过路径和结点的路径长度的概念，结点的路径长度定义为：从根结点到该结点的路径上分支的数目。把树的路径长度定义为:树中每个结点的路径长度之和。如果每个叶子结点都有确定的权值，则可引伸出叶子结点的带权路径长度和树的带权路径长度的定义。把叶子结点的带权路径长度定义为：该结点的路径长度与权值的成绩.再把树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和。记带权路径长度为WPL，则2435WPL（T）=式中:wi为第i个叶子结点的权值，Pi为第i个叶子结点的路径长度。图6。13 一个带权二叉树如图6。13所示的二叉树，它的带权路径长度值WPL2242523228.2赫(哈）夫曼树的基本概念赫（哈）夫曼（Haffman）树也称最优二叉树，简单地说是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。用计算机的术语可有一个定量的定义。赫夫曼树定义:在含n个叶子结点、结点i带有权值wi的二叉树，其中带权路径长度WPL取最小值的二叉树树，称为“最优二叉树或“赫夫曼树”。3。构造最优树(赫夫曼算法）：5317(c)在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树.例如，给出4个叶结点，设其权值分别为1，3，5,7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同.图6.14给出了其中5个不同形状的二叉树。7135(b)1357(a)(e)51371753(d)图6.14具有相同叶子结点和不同带权路径长度的二叉树这五棵树的带权路径长度分别为:(a）WPL1232527232（b)WPL1333527129（c）WPL1233537133（d)WPL7353321143（e）WPL7152331329可以计算出其带权路径长度为29，由此可见,对于同一组给定叶结点所构造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的.即(b)（e）均是。这给我们一个启示，可以用穷举的方法构件赫夫曼树，给出所有以给定权值为叶子的所有二叉树，并计算比较WPL，找出最小者，得到赫夫曼树.有时结果可能不惟一.但是，这往往是不现实的，有时甚至是不可能的，同时也是不必要的。根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。赫夫曼根据这一特点，最早给出了一个带有一般性规律的算法,俗称赫夫曼算法，较好地解决了这一问题。现简述如下：（1）据给定的n个权值w1,w2,wn，构造n棵二叉树的集合F=T1，T2，Tn，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树；（2）在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;(3)从F中删去这两棵树，同时加入刚生成的新树;（4）重复（2)和（3)两步,直至F中只含一棵树为止。图6.15 赫夫曼树的建立过程图6.15给出了叶子结点权值集合为W5，6,2,9，7的赫夫曼树的构造过程。并可求得：WPL（6+7+9）2（5+2)3222+2165注意:计算时只算叶子结点，是权值与路径长度之积，而不是权值与层数的乘积。6.3。2赫夫曼编码在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串,我们称之为编码。快速远距传输电文时，为节约时间、减少错误，总要使电文编码尽量短并且不能产生歧义。为使编码简短，可采用不等长编码,且使用频高的字符用较短的码。为了不产生歧义,必须使任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。例如编码方案：A-01，B010，C001，D-10不符合要求。因为字符A的编码01是字符B的编码010的前缀部分,这样对于代码串0101001，既是AAC的代码，也是ABD和BDA的代码.利用赫夫曼树可以构造出一种最优前缀编码使所传电文的总长度最短,这种编码就是赫夫曼编码.赫夫曼编码算法分为两大步：（1）构造赫夫曼树；（2）在赫夫曼树上求叶子结点的编码。方法是：给赫夫曼树的每一个分支标上代码，左分支标0；右分支标1。从根结点到相应叶结点所经过的路径上各分支所组成的0，1序列，即为所求编码。例：已知某系统只用8种字符通信，出现频率为0。05，0。07,0。08,0.14，0.23，0。03，0。11，试设计赫夫曼编码。解：为简便计算,把出现频率的100倍作为权值，即设W=（5,29，7，8,14，23，3,11）则构造出赫夫曼树，并标上分制代码后如图6.16所示。图6.16 赫夫曼编码6.3.3赫夫曼树与赫夫曼编码的算法#include stdio。h#define N 50/叶子结点数*/#define M 2N1/树中结点总数/typedef struct char data；/*结点值*/ int weight； /*权重*/ int parent；/*双亲结点/ int lchild；/*左孩子结点/ int rchild；/*右孩子结点/ HTNode；typedef struct char cdN;/存放哈夫曼码*/ int start； HCode;void CreateHT(HTNode ht，int n） int i，k,lnode，rnode，min1,min2； for (i=0；i2n-1;i+)/*所有结点的相关域置初值-1*/ hti。parent=hti。lchild=hti.rchild=1； for (i=n；i2n-1;i+）/*构造哈夫曼树*/ min1=min2=32767;/*lnode和rnode为最小权重的两个结点位置*/lnode=rnode=-1; for （k=0;k=i1;k+)if (htk.parent=1）/只在尚未构造二叉树的结点中查找/ if (htk.weightmin1） min2=min1;rnode=lnode； min1=htk。weight;lnode=k； else if （htk.weightmin2) min2=htk。weight；rnode=k; hti。weight=htlnode。weight+htrnode.weight； hti。lchild=lnode;hti。rchild=rnode; htlnode.parent=i； htrnode。parent=i； void CreateHCode（HTNode ht，HCode hcd,int n) int i,f,c; HCode hc; for (i=0；in;i+）/根据赫夫曼树求哈夫曼编码/ hc。start=n;c=i；f=hti.parent； while （f!=1）/*循序直到树根结点/ if (htf.lchild=c)/处理左孩子结点*/ hc.cdhc。start-=0; else/处理右孩子结点*/ hc。cdhc.start-=1; c=f；f=htf。parent； hc。start+;/*start指向赫夫曼编码最开始字符/ hcdi=hc； void DispHCode（HTNode ht,HCode hcd，int n） int i，j，k,sum=0,m=0； printf（”输出赫夫曼编码:n）; /*输出赫夫曼编码*/ for (i=0；in;i+) j=0; printf( %c:”，hti.data)； for （k=hcdi.start；k=n;k+) printf(”%c”，hcdi。cdk）； j+； m+=hti.weight;sum+=hti.weightj; printf（n）; printf(”WPL=d Sum=%dn”,sum,m)；v