数据结构第六章树的查找和应用

1、第六章:树的查找和树的应用 第一节 查找树v查找树的定义v查找树T是一棵二叉树T，它或是空,或满足下面三个条件：v1.如果树T的根结点的左子树非空，那么左子树中的所有结点的键值都小于T的根结点的键值：v2.如果树T的根结点的右子树非空，那么右子树中的所有结点的键值都大于T的根结点的键值。v3.树T的根结点的左、右子树也都是查找树。v也可以根据中序遍历来定义查找树：v对于一棵给定的二叉树T，如果树T中的结点的中序是排好序的，那么称树T是一棵查找树。v#include vstruct node char date;vstruct node *lchild,*rchild; v;v typedef

2、struct node NODE;v NODE *t , *p, *q;v Char a;v查找树t中找出给定键值a的算法：v(1)若t为空，那么查找失败，算法结束，否则转（）v(2)若t-data等于a，那么查找成功,算法结束,否则转(3)v(3)若t-data小于a, 那么t-lchild=t ;否则t-rchild=t转（）vvoid search(t,a,p_p,p_q)vNODE *t,*p_p,*P_q;vchar a;v *p_p=NULL;v *p_q=t;vwhile(*p_q!=NULL)v if (*p_q)-data=a) return;v*P_P=*p_q;vif (

3、adata)v *p_q=(*p_q)-Ichild;velse *p_q=(*p_q)-rchild;vvv例：变量t指向树的根结点， a是所要查找的键值，q指向被查找的结点，p指向被查找结点的父结点.可用如下的语句调用:search(t,a,&p,&q)vn个结点的查找树中找出结点k（k在树中，每次均是成功查找），所需的比较次数是结点k的树枝长度k加1。vMAX(二叉查找法)=max(1+k) 树T中的kvAVG(二叉查找法)=P(k)是结点k的相对使用频率。v设: p(k)= 则AVG(二叉查找法)= int insert(p_t,a)vNODE *p_t; vchar a;v NODE

4、 *p, *q, *r;v search(*p_t,a,&p,&q);vif (q!=NULL) return(l);vr=(NODE *)malloc(sizeof(NODE);vr-data=a;vr-Ichild=NULL;vr-rchild=NULL;vif (p=NULL) *p_t=r;velse if (p-dataa)vp-Ichild=r;velse p-rchild=r;vreturn(0);vv结点的删除v删除的算法(1)首先调用serach(),从而确定被删除结点在树中的位置。(2)若被删结点不在树中，则算法结束。(3)若被删结点在树中，则进行下面的删除。v(I)若被删

5、结点是根结点v(a)若被删结点无左子结点，则用被删结点的右子树作为删除后的树v(b) 若被删结点有左子结点，则用左子结点作为根，右子树作为被删结点的左子树在中序最后一个结点的右子树v(II)被删结点不是根结点v(a)若被删结点无左子结点，则v若被删结点是它的父结点的左子结点，那么被删结点的右子树作为被删结点的父结点的左子树。v如果被删结点是它的父结点的右子结点，那么被删结点的右子树作为被删结点的右子树。v(b)若被结点有左子结点，则把被删结点的右子树作为被删结点左子树按中序最后一个结点的右子树，同时进行。v如果被删结点是它的父结点的左子结点，那么把被删结点的左子树作为被删结点的父结点的左子树。

6、v如果被删结点是它的父结点的右子结点，那么被删结点的左子树作为被删结点父结点的右子树。v(III)回收被删结点的存贮单元vint delete(p_t,a)vNODE *p_t;vchar a;v NODE *p, *q, *r;vsearch(*p_t,a,&p,&q);vif (q=NULL) return(1);vif (p=NULL)vif (q-lchild=NULL)v *p_t=q-rchild;velse (r=q-lchild;vwhile (r-rchild!=NULL)vr=r-rchild;vr-rchild=q-rchild;v*p_t=q-Ichild;vvelse

7、 if (q-Ichild=NULL)vif (q=p-lchild)vp-Ichild=q-rchild;velse p-rchild=q-rchild;velse r=q-Ichild;vwhile (r-rchild!=NULL)v r=r-rchild;vr-rchild=q-rchild;vif (q=p-Ichild)vp-Ichild=q-Ichild;velse p-rchild=q-Ichild;vvfree(q);vreturn(0);vv依次删除a,e,d,c,b各结点第二节满树，拟满树，丰满树 v设二叉树T有n个结点，令I=log 2(n+1)v若2I-1个结点放满0至

8、（I-1）层，并且(1)若r=0,则称树T是一棵满二叉树，简称满树。 (2)若r 0,且剩下的 r个结点尽量靠左地排列在第I层上，则称树T是一棵拟满二叉树，简称拟满树。 (3)若r 0,且剩下的 r个结点随意地分布在第I层上，则称树T是一棵丰满二叉树，简称丰满树。v若T是满树，拟满树，丰满树，同时也是查找树，则称T是满查找树，拟满查找树，丰满查找树。v对于n个结点的任意序列，我们可用平分法构造出该结点序列的丰满树(1)若结点序列为空，那么得到一棵空的二叉树(2)如果序列中有n=1个结点，k0,k1,kn-1，那么令 m=(n-1)/2所求的树是由根结点km以及它的左子树TL和右子树Tr组成，其

9、中TLTr分别是用平分法由k0,k1,km-1和 km+1,km+2,kn-1得到的丰满树。v10,20, . 150 共15个数v所有结点的使用频率相同时，概率=1/nvAVG( 二叉查找法)log2nv当查找树退化为线性链表时vAVG( 二叉查找法)= = =n110)1(nik21nn110)1(niiv由于具有n个结点的丰满查找树具有log2n +1层，所以vMAX（二叉查找法）log2nv然而当查找树退化成线性链表时，vMAX（二叉查找法）=nv查找树与顺序存贮的线性表相比，它的突出优点是向查找树中插入和删除结点比较容易。第三节 堆和排序v设二叉树T是一棵拟满树，如果树T的任一结点不

10、小于它的左子结点的值，且不小于它的右子结点的值，那就称树T是一个堆（heap）vn个结点放在数组an中，v若n个结点的拟满树是一个堆，那么按层次次序存放树T的数组an就是一个堆，具有如下性质：v(1)若 2*I+1=a2*I+1v且(2)若2*I+2=a2*I+2vvoid siftdown(a,i,n)vint a ;vint i, n;v int j;vInt t;vt=aj;vwhile (j= 2 * i+ 1)n)v if(jn-1 & ajaj+l) j+;vif (t=0; i-)vsiftdown(a,i,n);vfor(i=n-1;i0; i-)v t=a0;va0=ai;v

11、ai=t;vsiftdown(a,0,i);vv第四节 平衡树v对于二叉查找树来说，丰满查找树最为有利，然而对丰满树进行插入和删除后，丰满查找树很容量变成不是丰满查找树，将其改造成丰满查找树非常困难。v平衡树的结构，它与丰满树较接近，但在进行结点的插入和删除工作后较易使该树仍保持一棵平衡查找树。v二叉树的高度定义：h(T)表示二叉树T的高度v若T=NULL，则h(t)=-1v若T为非空，TL和TR表示T的左右子树，v结点的平衡度：v设K是二叉树T中的结点，TKL和TKR分别是点K的左子树和右子树，称TKL和TKR高度之差为结点K的平衡度，记为v(k): (k)=h(TKR)-h(TKL)v平衡

12、树：若二叉树T中每个结点K都有|(k)|=1 ，则称树T为平衡树。v可以证明n个结点的平衡树的树枝的最大长度小于3/2log2nv因而查找效率与丰满查找树相近。vAdelson方法：vT是一棵平衡查找树，新结点K插入到T中，插入后的树T仍然是平衡查找树。vAdelson方法分为三个步骤：插入、平衡、改组v插入：不考虑结点的平衡度，使用在查找树中插入新结点的方法，把K插入树中，同时置新结点的平衡度(k)=0v平衡：k0,k1,km (km就是k)是从树根k0引向插入结点k的树枝v改组：1.如果kI是树根，且kI=0，那么v若K插在kI的左子树中，则置kI=-1；v若K插在kI的右子树中，则置kI

13、=+1；2.若kI0；那么v若kI=-1，且K插在kI的右子树中，则置kI=0；v若kI=-1，且K插在kI的左子树中，则必须对以kI为根的子树进行“左改组 ”；v若kI=+1，且K插在kI的左子树中，则置kI=0；v若kI=-1，且K插在kI的右子树中，则必须对以kI为根的子树进行“右改组 ”；v左改组为例：v改造后满足下面二个条件：1.改组后的新子树的高度和插入前以kI为根的子树的高度相同。2.新子树是一棵平衡树第五节 最佳查找树v在树中每个空指针上都挂上一个附加结点：外部结点。v原来树中的结点称为内部结点v在一棵树中共有（n+1）个外部结点v查找那些不在查找树中的结点总是终止于一个外部结

14、点上，并且是不成功的查找，故外部结点也称为失败结点。v由根结点到所有的外部结点的路径长度的总和称为外部路径长度v由根结点到所有内部结点的路径长度的总和称为内部路径长度 内部路径长度 外部路径长度可以证明第六节 Huffman算法vHuffman算法：寻找一个具有紧小加权外部路径长度的二叉树的方法。v给定n个结点的序列F=k0,k1,kn-1，它们的权w(k0),w(k1)w(kn-1)构造一棵以k0,k1,kn-1作为叶结点的二叉树T。v使得 v 达到最小，v算法：vm个结点序列A（初始时，A=F，m=n）v对t=1，2，n-1执行如下的构造步骤。vA=a0,a1,am-1, A中的结点都是已

15、形成的子树的根，如果ai,aj分别是A中权最小和次最小的结点，那么用权w(bt) =w(ai) +w(aj) 的新结点 bt和ai,aj形成新子树。然后从A中除去ai,aj并把bt作为A的最后一个结点，m减去1，最后只有一个树根：这棵也称为Hmffman树。 v例如：5个结点vHmffman编码：v为信息M0M1Mn-1求得一组最佳编码，每个编码都是二进制位串，通迅的发送方应用二进制位串传送一定的信息，而接收方使用译码树，把所接收到的二进制 位翻译成相应的信息。v 译码树是一棵二叉树，二叉树的外部结点表示翻译的信息结点，从根到外部结点的路径上的树枝表示使用的二进制位串，把M0M1Mn-1的使用

16、频率看作是对应的权。则可构造一棵Hmffman树。v例：5个字母 a,b,c,d,e使用频率是10，5，20，10，18a:011 b:010 c:11 d:00 e:10 0100110010 代表 bade得不到相应的译码第七节 B_树vB_树是一种平衡的多叉树，B_树的操作简单，改进后的B+树成为索引文件的常用结构vm阶B_树的性质v每个结点的子结点个数m；v除根和叶子外，每个结点的子结点树m/2 v根结占至少有两个子结点，除非它同时又是叶子，此时它没有子结点。v所有叶子都出现在同一层上，而且不带有信息。v具有k个子结点的非叶子结点含有k-1个键值 v叶子结点是终端结点，不带有任何信息，

17、实际上可看作不在树中的外部结点。vB_树的m阶是人们事先指定的，一旦指定后，就固定不变了。vm阶B_树中，每个结点具有如下的结构：v其中；vj=m-1vki(1=I=j)是键值，且所有键值是唯一的vPi(0=I=j)是指向该结点的子结点的指针。v结点中的键值是排好序的。v若是升序： k1k2kj,vp0指向k1 和k2的子树的根结点vPi(0I=3的情况。M阶B_树上进行查找，插入和删除的算法v查找：v查找给定的键值kv查找的节点从外存调入内存，在该结点的键值k1,k2,kj中查找k。v当m较小时，可有顺序查找法，当m较大时，可用二分查找法。v若k=ki(1=I=j)则查找成功。v若kk1，则

18、v (a)若p0为空，那么查找失败v (b)若P0非空，那么取得P0所指向的结点，再继续进行查找。v若kikki+1(1=Ikj则v(a)若pj为空,那么查找失败v(b)若pj非空,那么取pj所指向的结点,再继续进行查找,v在实际应用中,B_树结点不仅含有键值,而且还包含与该键值对应的记录的地址,当查找成功时,就可找到相应的记录。v对于给定的一棵B_树,在最坏情况下，查找一个键值最多要向外存取多少个结点？v取决于B_树的层数，假设树中有N个键值，那么t层上有N+1个叶子，各层上最少的结点个数：例如：当N=1999998和M=199时，t最多是4非曲直，也只要存取4个结点，就能找到所要的键值。v

19、插入：v一般地：当一个新键值插到一棵m阶B_树中，如果所有的叶子都在第t层上，那么我们就把新键值插入到第（t-1）层的相应结点中，如果被插入的结点在插入之前，键值的个数少于（m-1）个，那么把新键值直接插入在这个结点的适当位置即可；如果这个结点在插入前，键值的个数为m-1连同插入的新键值共有m个，那么我们就把这m 个键值分裂成两个结点vk1,k2,km分裂成 k1,k2km/2-1和km/2+1,km，再把km/2 插入到父结点中，原来父结点中指向被插入结点的指针P改成P, km/2-1,p左面结点右面结点vP, km/2-1,pv若km/2-1 插入父结点时，变成具有m个键值的结点，我们还用

20、相同的方法进行分裂。如果一直分裂到根结点，我们把原来的根结点分裂成两个结点，而把中间的键值 km/2-1 往上推，作为一个新的根结点，此时B_树长高了一层。v下面是5阶B_树中插入键值P, km/2-1,p左面结点右面结点v删除v真正的删除总是从叶子层的上面一层开始。在执行真正的删除后，我们还要检查被删除结点中键值个数是否小于m/2 -1？若大于等于m/2-1,则删除过程结束；若小于m/2-1,则要从相邻的键值个数大于m/2-1的兄弟结点中借一个键值。（注意：我们所借到的键值是它们的父结点中介于这两个结点之间的键值，然后把左邻（或右邻）兄弟结点的最右（或最左）的键值替代父结点中被取走的键值）若

21、借键成功，则删除过程结束。v删除后的B_树:v从5阶B_树中删除200和040v如果从相邻的兄弟结点的键值个数都是m/2 -1，那么就借不到键值，这时就要进行与分裂相反的处理过程联结，即把两个结点中的键值连同介于其中间的父结点的键值组成一个新结点，此时父结点就少了一个键值。如果进行联结后父结点的键值个数仍然大于等于m/2 -1个，那么删除过程结束。v若进行的联结使得位于上一层的父结点的键值个数少于 m/2 ，那么还得要在上一层中再次进行借用键值或联结处理。v为了便于B_树的查找、插入和删除的实现，我们可以在结点上附加一个信息，用它指明结点当前有多少个键值。v在索引文件中，经常使用B_树的一些变

22、形，其中B+树是一种应用广泛的变形：vm阶B+树的定义如下：v每个结点最多可以有 m个子结点v除根结点和叶子结点外，每个结点至少有(m+1)/2 个子结点v根结点至少有个子结点，最多有m个子结点v有k个子结点的结点必有k个键值v所有叶子结点包含全部键值及指向相应记录的指针，而且叶子结点按照键值从小到大顺序链接v所有非叶子结点仅包含其子树中最大的键值vB+树是可以在其叶子结点上存贮信息的树，所有叶子结点包含了树中所有键值且包含了指向记录的相应指针；同时，叶子结点按照键值从小到大顺序链接起来。这样，使B+树即可以进行随机查找，也可以进行顺序查找。第八节 Trie结构v当键值为变长时，有一种索引结构

23、特别有效，那就是Trie 结构。v Trie 是 Retrieve（检索）的中间个字母组成的vTrie树是一棵m(m=2)次树，其中每层上的分支不是由整个键值所确定，而是由键值的一部分所确定。v下面是由键值所构成的一棵 Trie 树 v( 一)查找v在介绍 rie树的插入和删除操作时，为直观和叙述方便，我们用p-link/0,p-linka,p-linkb,p-z 分别表示分支结点中序号为，26的指针。v(二)插入 v（三）删除v删除上图中的“computer”经过查找，得到信息结点q4，q4-key值为computer，因为q4挂在P8-linke的分支上，置P8-linke为空，删除q4但

24、以P8为根的子树只含一个信息结点q3，所以P8无存在必要，删除P8，基于同样的道理删除P7，P6，此时以P4为根的子树有3个信息结点，P4不能删除。第四节 解答树v经常遇到这样的一类问题，只需系统地检查有限多个可能性，就可以得到关于它的一切答案，通常把这些可能性看成是树的结点，这种树称为解答树，于是，系统地鉴定一切可能性的问题就变成普查解答树的问题了。v通过具体例子介绍用回溯法查找解答树v假设：给定的“位置”集合为S，“规则”集合为R，对于每个位置sS，由R定义它的有限个后继位置集合S0，S1，S2 St-1,记作R（S）=S0，S1，S2 St-1,假设S中，指定一个位置为初始位置A，指定若

25、干个终止位置为终止位置集合E。如果用P表示从A出发应用规则R所能到达的位置的集合，那么对给定问题的解答常常可以归结为从P的终止位置中找出符合某些指定条件的特殊的“解答位置”。v若P是有限集合，那么集合P很自然地对应于一棵解答树，它相对应于初始位置A，如果结点K对应于位置S，那么K有t=0个子结点K0，K1，Kt-1对应于后继位置 R（S）=S0，S1，S2 St-1v为了找出解答位置，我们可以分二步走：v构造解答树v系统地检查解答树的结点，看它们是否对应于解答位置v回溯法v背包问题v设的n种物品，记作d1,d2,dn，对应于每个di(1in)都有一个整数重量Wi0和一个整数价值Vi0。如果从这

26、n件物品中挑选其中几件物品装进背包，使总重量不超过给定的重量tot，同时，使背包中物品的价值量尽可能高。v背包的装填可以这样进行，依次考虑物品d1,d2,dn，或者把它装进背包，或者不装进背包，背包的装填情况可用三元组表示（重量，价值，m），其中重量是当前背包的重量，价值是当前背包的价值，m是已经考虑过的d1,d2,dm。v为简单起见，以下假定相对价值按递减次序排列，即并假定不出现退化情况：v算法一v#define MAXN 100vstruct wv_node int w;vint v;v ;vtypedef struct wv_node WV_NODE;vstruct stack node

27、 int w;v int v;v int m;v;vtypedef struct stack_node S_NODE;vWV_NODE wvMAXN;vS_NODE SMAXN + 1;vint top,n;vint f(t,m)v int t, m;v if (m=n | t=0) return(0);v else if (t=wvm+l.w)v return(f(t-wvm+1.w,m+1) +wvm+1.v);v else return(t* wvm+1.v/wvm+1.w );vvmain() vint tot,y,i,aux;v printf(nnlnput n=);v scanf(

28、%d,&n);v if (nl) printf(* * * n1 * * * * n);vexit(l);vv printf(input wv:n);v for (i=1; i=n;i+ )v printf(%3d;,i);v scanf(%d, %d,&wvi.w,&wvi.v);v vprintf(input tot=);vscanf(%d,&tot);vy=0;vs0.w=0;vs0.v=0; vs0.m=1;vtop=0;vif (wv1.w=0)v if (stop.m=n)v if (stop.vy) y=stop.v;v top-;v v elsev if (stop.v +f(

29、tot-stop.w,stop.m)y)v stop.m=stop.m+1;v if (stop.w+wvstop.m.w=wvm+1.w)v return(f(t-wvm+1.w,m+1) +wvm+1.v);v else return(t*wvm+1.v/wvm+1.w);vvmain()v int tot, y,i, aux;vprintf(nnlnput n=);vscanf(%d, &n);vif (n1) printf(* * * * * n1 * * * *n);v exit (1);v vprintf(Input wv:n);vfor (i=1;i=n; i+)v printf(%3d:,i);v scanf(%d, %d, &wvi.w,&wvi.v);v vprintf(input tot=);vscanf(%d, &tot);vy=0;vs0.w=0;vso.v=0;vs0.m=1;vtop=0;vif (wv1.w=0)v if (stop.m=n)v if (stop.vy)v y=stop.v;v stop.m=-stop.m;v printf(The bast filling );v printf(so far is:n);v for (i=0; i=top;i+)v if (si