二叉树及其应用-朱全民

二叉树及其应用雅礼朱全民二叉树二叉树是一种特殊的树型结构，它的特点是每个节点至多只有两个子节点。二叉树每个节点的子树有左右之分，其次序不能任意颠倒。二叉树也有特殊形式，例如满二叉树、完全二叉树等。例如右图就是一棵二叉树，并且是一棵完全二叉树。二叉树的存储结构常用的存储结构typebitree=^nodenode=recorddata:datatype;lchild,rchild:bitree;end;二叉树的遍历遍历(先序遍历,中序遍历,后序遍历)Procpreorder(bt:bitree);ifbtNilthen[visit(bt^)preorder(bt^.lchild);preorder(bt^.rchild);]endP二叉树的性质在二叉树的第i层上最多有2i-1个结点深度为K的二叉树最多有2k-1个结点在二叉树中,叶子结点的总数总比为度数为2的结点多1有n个结点的完全二叉树的结点按层序编号,则对任意一结点i,有(1)如果i=1,则结点i是二查树的根，无双亲；如果i1，则双亲是[i/2](2)如果2in，则结点i无左孩子，否则左孩子为2i(3)如果2i+1n，则结点i无右孩子，否则右孩子为2i+1树、森林转化为二叉树用“孩子兄弟表示法”可以将任意一棵树转化为二叉树的形式森林转化为二叉树如果F={T1,T2,…,Tm}是森林，则可按如下规则转化为一棵二叉树。1)若F为空，即m=0,则B为空树2)若F非空，即m0,则B的根root即为森林中第一棵树的根root(T1),B的左子树为从T1中子树森林F1={T11,T12,…,T1i}转换而成的二叉树；其右子树Rb是从森林F={T2,…,Tm}中转换出来的二叉树树的儿子兄弟表示法在一棵树中，拥有同一个父结点的结点互称为兄弟。我们不妨假设树中每个结点的子结点是有序的（就像二叉树一样），则我们可以将一棵树这样转化成二叉树：二叉树中每个结点对应原树的每个结点对于二叉树中的某个结点它的左子结点对应原树中该结点的第一个子结点；它的右子结点对应原树中该结点的下一个兄弟。原树转化后的树树的儿子兄弟表示法这样我们可以类似于二叉树的链式结构写出树的儿子兄弟表示法的存储结构：TYPEtree=^node;node=recorddata:datatype;parent,child,brother:tree;//分别记录父亲、第一个儿子、下一个兄弟end;树的儿子兄弟表示法给定m个实数w1,w2,…,wm,(m=2),要求一个具有m个外部节点的扩充二叉树，每个外部ki节点有一个wi与之对应，作为它的权,使得带权外部路径长度最小，其中li是从根到外部节点的路径长度。最优二叉树(哈夫曼树)miiilw1算法1.构造m个只有1个节点的树2.找两个最小的权3.以这两个节点为左右儿子构造一个二叉树，并将该数的根节点权之为左右儿子权值之和4.继续第二步，直到剩下一棵树为止讨论最优k叉树就是指在一个节点最多可以有k个叶子节点的时候，假设有n（n=k）个权值{w1,w2,….wn},试构造出一棵有ｎ个叶子节点的k叉树。每个叶子节点有一个不同的权值ｗi。其中树的带权路径长度最小的那棵树叫做最优k叉树。怎么构造??分析最优k叉树必须具备的性质：1.每个节点如果不是叶子节点，那么一定有k个儿子节点。2.权值大的节点不能在比权值小的节点下方。就是权值大的节点到树根的长度要小于等于权值小的节点到树根的长度。算法1.根据给定的n个权值wl，w2，…，wn构成n棵k叉树的森林F={T1，T2，…，Tn}，其中每棵k叉树Ti中都只有一个权值为wi的根结点，其左右子树均空。2.在森林F中选出k棵根结点权值最小的树(当这样的树不止k棵树时，可以从中任选k棵)，将这k棵树合并成一棵新树，为了保证新树仍是k叉树，需要增加一个新结点作为新树的根，并将所选的k棵树的根分别作为新根的左右孩子，将这k个孩子的权值之和作为新树根的权值。3.对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是最优k叉树。反例假设k=3,当n=5时，这样做是对的。但是当n=4时，用刚才的方法得到的“最优3叉树”，但是，明显右图的那颗树会比左图的那颗树优。分析原因•错误的原因：主要是左边的这棵树它并没有排满。可以把第3层的一个节点拉到第2层去，而这样做肯定会让WPL更小。那么肯定要让第一次合并的时候，少合并几个点，后面的操作就和上面所说得算法一样。并且让最后一次合并能合并n棵树。从而让上面排满。那么第一次要合并多少个点呢？首先每次合并会让树的总数减少k-1棵，而最后还有n棵。那么完成了第一次合并后，剩下的树的个数正好模k-1后等于1。那么第一次合并的树的个数就应该是(n-2)mod(k-1)+2。而当k=2时，k-1=1，此时第一次合并的个数总是为2。改进算法1.根据给定的n个权值wl，w2，…，wn构成n棵k叉树的森林F={T1，T2，…，Tn}。其中每棵k叉树Ti中都只有一个权值为wi的根结点，其左右子树均空。进行第一次合并操作选出最小的(n-2)mod(k-1)+2颗根节点权值最小的树进行合并成一棵新树,该树根的权值为选出来的树的权值之和。2.在森林F中选出k棵根结点权值最小的树(当这样的树不止k棵树时，可以从中任选出k棵），将这k棵树合并成一棵新树，为了保证新树仍是k叉树，需要增加一个新结点作为新树的根，并将所选的k棵树的根分别作为新根的孩子，将这k个孩子的权值之和作为新树根的权值。3.对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是最优k叉树。二叉堆定义堆是一棵完全二叉树，对于每一个非叶子结点，它的权值都不大于（或不小于）左右孩子的权值，我们称这样的堆为小根堆（或大根堆）。描述如下:n个元素的序列{k1,k2,…,kn}，当且仅当满足ki=k2i并且ki=k2i+1或者ki=k2i并且ki=k2i+1二叉堆肯定是一颗完全二叉树在堆中插入元素x首先将元素x放到堆中的最后一个位置（即最底层最右边的位置），然后不断地把x往上调整，直到x调不动为止（即大于它现在的父亲，或者x处于根结点）。定义一个堆:Varst:array[1..maxn]oflongint;//存储堆n:longint;//堆中元素个数13545786213557864(1)将新节点插到最后(2)把新节点和父亲进行交换1557864(3)继续交换，直到重新满足堆的性质322插入(实际上是不断向上调整的过程)PROCheapup(k:longint);{把第k个结点上调}beginwhilek1dobegini:=kdiv2;{i是k的父亲}ifst[i]st[k]thenbeginswap(i,k);k:=i;{交换结点i和k}endelseexit;end;end;在堆中删除任意一个元素这里说指的删除任意一个元素，是指在当前堆中位置为w的元素。过程如下：首先把位置w的元素和最后一个位置的元素交换，然后删去最后一个位置，这样w上的元素就被删除了。接着把位置w上的新元素不断下调，直到满足堆的性质。155786431557864315578634(1)当前要删除的节点是根节点的左儿子(2)将根节点的左儿子和最后一个节点交换(3)将新的节点不断下调，直到满足堆的性质22删除(实际上是不断向下调整的过程)PROCheapdown(k:longint);{把第k个结点往下调}beginwhilek+k=ndobegini:=min{2k,2k+1};{如果2k+1不存在直接返回k+k否则返回2个中间的值较小的元素}ifst[i]st[k]thenbeginswap(i,k);k:=i;endelseexitend;end;堆的构造就是不断插入到堆的过程62351分别插入权为6,2,3,5,1的元素6(1)6(2)26(3)236(4)2356(5)2351堆的插入.删除PROCadd(x:longint);{添加一个值为x的元素}begininc(n);st[n]:=x;heapup(n)end;PROCdel(x:longint);{添加一个值为x的元素}beginst[x]:=st[n];dec(n);heapdown(x)end;合并果子在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所消耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。【输入文件】输入文件fruit.in包括两行，第一行是一个整数n(1=n=10000),表示果子的种类数。第二行包含n个整数，用空格分隔，第i个ai(1=ai=20000)是第i个果子的数目。【输出文件】输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。【样例输入】3129【样例输出】15【数据规模】对于30%的数据，保证有n=1000;对于50%的数据，保证有n=5000;对于全部的数据，保证有n=10000。合并果子把合成堆后的每堆的果子仍然看成相对独立的，那么定义timesi等于第i堆果子被合并的次数，ai为第i堆数字权值。则Totalcost=，目标求得是min{Totalcost}。建立一棵二叉树，每堆果子分别为该树的叶节点，一种二叉树形态对应一种合并方案（2堆果子合并则有共同父结点），所以该方案的Totalcost=depthi*vi，i是叶节点。解法是每次取出最小的两个节点，并从节点集合中删除，然后合并这两点后再加入节点集合；重复，直到只剩一个节点；niiivtimes1由于每次要取出最小的两个节点。（一般做法是每更新一次集合，重新排序，时间是O(n2)）。由于n=10000，不得不采用数据结构--堆进行优化。)(2n)log(nn解决方案方法或要点时间复杂度可过数据解决方案1一般做法30%-50%解决方案2堆100%任务有n个任务，每个任务有一个截止完成的时间Ti和完成需要的时间Ci。现在你一个人希望从0时刻开始完成尽量多的任务。问最多能完成多少任务？分析首先不妨将任务按照截止时间排序。这时候我们可以采用贪心方法，尽量选截止时间比较晚，同时需要时间比较少的任务完成是最好的。于是得出一个结论：假设最优方案的组成的任务集合是U。如果存在一个不属于U的任务j，对于某个属于Ｕ的Ｉ满足TjTi而且ＣjCi。那么把Ｉ从Ｕ中删除，而把Ｊ替换过来，肯定仍然满足题目要求，也是一组最优方案。分析考虑排序后前i个任务组成的最优方案集合是Ｕi。下面看第i+1个任务。如果第i+1个任务直接加入后，依然满足题目要求，那么前i+1个任务最后方案集合就是Ui+1=Ui+{i+1}。否则我们找到Ui中需要时间最长的任务K。如果CkCi+1那么根据定理1，将K,i+1替换后肯定更优。于是得到了一个算法的基本流程：1.将任务按照Ti排序。2.从小到大枚举i。维护当前最优方案的集合U。每次将当前的任务I加入U后。如果不满足条件了，那么删去U中耗时最长的任务。3.输出最优方案即可。因此我们需要使用一种数据结构，它能快速删除耗时最长的任务，同时快速的插入一个新元素