《二叉树及其应用》PPT课件.ppt

《《二叉树及其应用》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《二叉树及其应用》PPT课件.ppt（58页珍藏版）》请在装配图网上搜索。

1、二叉树及其应用,雅礼 朱全民,二叉树,二叉树是一种特殊的树型结构，它的特点是每个节点至多只有两个子节点。 二叉树每个节点的子树有左右之分，其次序不能任意颠倒。 二叉树也有特殊形式，例如满二叉树、完全二叉树等。 例如右图就是一棵二叉树，并且是一棵完全二叉树。,二叉树的存储结构,常用的存储结构 type bitree=node node=record data :datatype; lchild,rchild:bitree; end;,二叉树的遍历,遍历( 先序遍历, 中序遍历, 后序遍历) Proc preorder(bt:bitree); if btNil then visit(bt) pre

2、order(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

3、, ,Tm是森林，则可按如下规则转化为一棵二叉树。 1)若F为空，即m=0,则B为空树 2)若F非空，即m0,则B的根root即为森林中第一棵树的根root(T1),B的左子树为从T1中子树森林F1=T11, T12, ,T1i转换而成的二叉树；其右子树Rb 是从森林F=T2, ,Tm中转换出来的二叉树,树的儿子兄弟表示法,在一棵树中，拥有同一个父结点的结点互称为兄弟。我们不妨假设树中每个结点的子结点是有序的（就像二叉树一样），则我们可以将一棵树这样转化成二叉树： 二叉树中每个结点对应原树的每个结点 对于二叉树中的某个结点 它的左子结点对应原树中该结点的第一个子结点； 它的右子结点对应原树中该

4、结点的下一个兄弟。,转化后的树,树的儿子兄弟表示法,这样我们可以类似于二叉树的链式结构写出树的儿子兄弟表示法的存储结构： TYPE tree = node; node = record data : datatype; parent, child, brother : tree; / 分别记录父亲、第一个儿子、下一个兄弟 end;,树的儿子兄弟表示法,给定m个实数w1, w2, wm,(m=2) ,要求一个具有m个外部节点的扩充二叉树，每个外部ki节点有一个wi与之对应，作为它的权,使得带权外部路径长度 最小，其中li是从根到外部节点的路径长度。,最优二叉树(哈夫曼树),算法,1.构造m个只有

5、1个节点的树 2.找两个最小的权 3.以这两个节点为左右儿子构造一个二叉树，并将该数的根节点权之为左右儿子权值之和 4.继续第二步，直到剩下一棵树为止,讨论,最优k叉树就是指在一个节点最多可以有k个叶子节点的时候，假设有n（n=k）个权值w1,w2,.wn,试构造出一棵有个叶子节点的k叉树。每个叶子节点有一个不同的权值i。其中树的带权路径长度最小的那棵树叫做最优k叉树。 怎么构造?,分析,最优k叉树必须具备的性质： 每个节点如果不是叶子节点，那么一定有k个儿子节点。 权值大的节点不能在比权值小的节点下方。就是权值大的节点到树根的长度要小于等于权值小的节点到树根的长度。,算法,根据给定的n个权值

6、w1，w2，wn构成n棵k叉树的森林F=T1，T2，Tn，其中每棵k叉树Ti中都只有一个权值为wi的根结点，其左右子树均空。 在森林F中选出k棵根结点权值最小的树(当这样的树不止k棵树时，可以从中任选k棵)，将这k棵树合并成一棵新树，为了保证新树仍是k叉树，需要增加一个新结点作为新树的根，并将所选的k棵树的根分别作为新根的左右孩子，将这k个孩子的权值之和作为新树根的权值。 对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是最优k叉树。,反例,假设k=3,当n=5时，这样做是对的。但是当n=4时，用刚才的方法得到的“最优3叉树”，但是，明显右图的那颗树会比左图的那颗树优。,分析原因

7、,错误的原因：主要是左边的这棵树它并没有排满。可以把第3层的一个节点拉到第2层去，而这样做肯定会让WPL更小。 那么肯定要让第一次合并的时候，少合并几个点，后面的操作就和上面所说得算法一样。并且让最后一次合并能合并n棵树。从而让上面排满。 那么第一次要合并多少个点呢？ 首先每次合并会让树的总数减少k-1棵，而最后还有n棵。那么完成了第一次合并后，剩下的树的个数正好模k-1后等于1。那么第一次合并的树的个数就应该是(n-2) mod (k-1) + 2。 而当k=2时，k-1=1，此时第一次合并的个数总是为2。,改进算法,根据给定的n个权值wl，w2，wn构成n棵k叉树的森林F=T1，T2，Tn

8、。其中每棵k叉树Ti中都只有一个权值为wi的根结点，其左右子树均空。进行第一次合并操作选出最小的(n-2)mod(k-1)+2颗根节点权值最小的树进行合并成一棵新树,该树根的权值为选出来的树的权值之和。 在森林F中选出k棵根结点权值最小的树(当这样的树不止k棵树时，可以从中任选出k棵），将这k棵树合并成一棵新树，为了保证新树仍是k叉树，需要增加一个新结点作为新树的根，并将所选的k棵树的根分别作为新根的孩子，将这k个孩子的权值之和作为新树根的权值。 对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是最优k叉树。,二叉堆,定义 堆是一棵完全二叉树，对于每一个非叶子结点，它的权值都不大

9、于（或不小于）左右孩子的权值，我们称这样的堆为小根堆（或大根堆）。 描述如下: n个元素的序列k1,k2,kn，当且仅当满足 ki=k2i 并且 ki = k2i+1 二叉堆肯定是一颗完全二叉树,在堆中插入元素x,首先将元素x放到堆中的最后一个位置（即最底层最右边的位置），然后不断地把x往上调整，直到x调不动为止（即大于它现在的父亲，或者x处于根结点）。,定义一个堆: Var st:array1.maxn of longint; /存储堆 n:longint; /堆中元素个数,插入 (实际上是不断向上调整的过程),PROC heapup (k:longint); 把第k个结点上调 begin

10、while k1 do begin i:=k div 2; i是k的父亲 if stistk then begin swap(i,k); k:=i; 交换结点i和k end else exit; end; end;,在堆中删除任意一个元素,这里说指的删除任意一个元素，是指在当前堆中位置为w的元素。过程如下：首先把位置w的元素和最后一个位置的元素交换，然后删去最后一个位置，这样w上的元素就被删除了。接着把位置w上的新元素不断下调，直到满足堆的性质。,插入 (实际上是不断向上调整的过程),PROC heapdown(k:longint);把第k个结点往下调 begin while k+k=n do

11、 begin i:=min 2k,2k+1; 如果2k+1不存在直接返回k+k否则返回2个中间的值较小的元素 if stistk then begin swap(i,k); k:=i; end else exit end; end;,堆的构造就是不断插入到堆的过程,堆的插入.删除,PROC add(x:longint); 添加一个值为x的元素 begin inc(n); stn:=x; up(n) end; PROC add(x:longint); 添加一个值为x的元素 begin inc(n); stn:=x; up(n) end;,合并果子,在一个果园里，多多已经将所有的果子打了下来，而且

12、按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所消耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又

13、得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。,【输入文件】 输入文件fruit.in包括两行， 第一行是一个整数n(1=n=10000),表示果子的种类数。第二行包含n个整数，用空格分隔，第i个ai(1=ai=20000)是第i个果子的数目。 【输出文件】 输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。 【样例输入】 3 1 2 9 【样例输出】 15 【数据规模】 对于30%的数据，保证有n=1000; 对于50%的数据，保证有n=5000; 对于全部的数据，保

14、证有n=10000。,合并果子,把合成堆后的每堆的果子仍然看成相对独立的，那么定义timesi等于第i堆果子被合并的次数，ai为第i堆数字权值。则 Totalcost= ，目标求得是 minTotalcost。 建立一棵二叉树，每堆果子分别为该树的叶节点，一种二叉树形态对应一种合并方案（2堆果子合并则有共同父结点），所以该方案的Totalcost =depthi*vi ，i是叶节点。解法是每次取出最小的两个节点，并从节点集合中删除，然后合并这两点后再加入节点集合；重复，直到只剩一个节点；,由于每次要取出最小的两个节点。（一般做法是每更新一次集合，重新排序，时间是O(n2)）。由于n=10000

15、，不得不采用数据结构-堆进行优化。,任务,有n个任务，每个任务有一个截止完成的时间Ti和完成需要的时间Ci。现在你一个人希望从0时刻开始完成尽量多的任务。问最多能完成多少任务？,分析,首先不妨将任务按照截止时间排序。这时候我们可以采用贪心方法，尽量选截止时间比较晚，同时需要时间比较少的任务完成是最好的。于是得出一个结论： 假设最优方案的组成的任务集合是U。如果存在一个不属于U的任务j，对于某个属于的满足TjTi而且jCi。那么把从中删除，而把替换过来，肯定仍然满足题目要求，也是一组最优方案。,分析,考虑排序后前i个任务组成的最优方案集合是i。下面看第i+1个任务。如果第i+1个任务直接加入后，

16、依然满足题目要求，那么前i+1个任务最后方案集合就是Ui+1=Ui+i+1。否则我们找到Ui中需要时间最长的任务K。如果CkCi+1那么根据定理1，将K,i+1替换后肯定更优。于是得到了一个算法的基本流程： 1.将任务按照Ti排序。 2.从小到大枚举i。维护当前最优方案的集合U。每次将当前的任务I加入U后。如果不满足条件了，那么删去U中耗时最长的任务。 3.输出最优方案即可。 因此我们需要使用一种数据结构，它能快速删除耗时最长的任务，同时快速的插入一个新元素。显然，使用大根堆即能满足题目要求。,二叉查找树,二叉查找树(Binary Search Tree) 可以被用来表示有序集合、建立索引或优

17、先队列等。 最坏情况下，作用于二叉查找树上的基本操作的时间复杂度，可能达到O(n)。 某些二叉查找树的变形，基本操作在最坏情况下性能依然很好，如红黑树、AVL树等。,BST的特点,（1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。（2） 二叉排序树中，各结点关键字是惟一的。实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质(1)里的小于改为大于等于，或将BST性质(2)里的大于改为小于等于，甚至可同时修改这两个性质。（3） 按中序遍历该树所得到的中序序列是一个递增有序序列。,实例,BST的查找,FUN

18、C bstsrch(t:bitreptr;K:keytype):bitree if (t=nil) or (t.key=K) then return(t) else if t.keyK then return(bstsrch(t.lchild,k) else return(bstsrch(t.rchild,k) endF,BST的插入,在二叉排序树中插入新结点，要保证插入后仍满足BST性质。其插入过程是：(a)若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；(b)若二叉排序树T不为空，则将key和根的关键字比较： (i)二者相等，则说明树中已有此关键字key，无须插入。

19、 (ii)keyTkey，则将它插入根的右子树中。 子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。,BST插入的递归算法,PROC ins_bstree(var bst:bitree;k:keytp); 采用链式存储结构 begin new(s);s.key:=k;s.lchild:=nil;s.rchild:=nil; if bst=nil then bst:=s; else if Kfkey then f.lchild:=s; else f.rchild:=s end;,BST的生成为进行

20、不断插入的过程! 但在生成BST的时候,可能会由于根结点选择不好,使得树很斜,查找的效率降低,可以使用随机产生根结点的方法,使得BST较平衡,下图就是两棵关键字相同的BST树.,删除,分三种情况讨论 1)删除叶子节点不破坏树的结构,修改其双亲结点: f.lchild:=NIL 2)若只有左孩子Pl或者只有右孩子Pr,则只要令Pl或Pr直接为f的左孩子即可:f.lchild:=P.lchild;或者f.lchild:=P.rchild; 3)左右孩子都有,设中序遍历的序列为ClC.QlQSlSPPrF,令P的左孩子为f的右孩子,而P的右孩子为S的右孩子 q:=p;s:=p.lchild; whi

21、le srchildnil do q:=s;s:=s.rchild p.data:=s.data; if qp then q.rchild :=s.lchild else q.lchild :=s.lchild dispose(s),Splay 树,Splay树是二叉查找树的改进。 对Splay树的操作的均摊复杂度是O(log2n)。 Splay树与二叉查找树一样，也具有有序性。 即Splay树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。 Splay树的核心思想就是通过Splay操作进行自我调整，从而获得平摊较低的时间复杂度。,Splay操作,

22、Splay操作是在保持Splay树有序性的前提下，通过一系列旋转操作将树中的元素x调整至树的根部的操作(Zig:右旋,Zag:左旋)。 在旋转的过程中，要分三种情况分别处理： 1)Zig 或 Zag 2)Zig-Zig 或 Zag-Zag 3)Zig-Zag 或 Zag-Zig,Splay操作 情况1,Zig或Zag操作： 节点x的父节点y是根节点。,Splay操作 情况2,Zig-Zig或Zag-Zag操作： 节点x的父节点y不是根节点，且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。,Spaly操作 情况3,Zig-Zag或Zag-Zig操作： 节点x的父节点y不是根节点，x

23、与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。,Splay操作举例,Splay(1,S),Spaly树基本操作,查找：与二叉排序树查找类似，只是查找结束后要将找到的元素通过Splay操作旋转到根。 插入：用查找过程找到要插入的位置，进行插入。然后将新元素旋转到根。 删除：首先在树中找到要删除的元素，将他转到根节点并删去，这样原来的树就分裂成了两棵树，然后将左子树中拥有最大关键字的那一个元素转到根，由于它是左子树中的最大元素，所以他不存在有儿子，这样只要把原来的右子树作为他的右子树，就重新合并成了一棵树。 可见在Splay树的基本操作中，处处要用到Splay旋转操作！,例一 Pet（湖

24、南省省队选拔赛）,宠物收养场提供两种服务：收养被离弃的宠物与让新的主人领养宠物。每个宠物有不相同的特点值。领养人所希望的特点值也不相同。如果领养人/遗弃宠物过多，则当前来的宠物/领养人选择离其特点值最近的（如果有两个特点值与其同样接近，则选择较小的）领养人/宠物，被领养/领养。并且纪录两个特点值的差值。 输入N条请求(X,Y)，X=0表示宠物;X=1表示领养人，Y为特征值。 任务是计算所有差值的和。 （N=80000，等待的宠物/领养者数M=10000）,例一 Pet,我们先用最普通的数组记录过多的宠物/领养人。 查找：需要检索整个数组，复杂度为O(M) 删除：删除指定元素之后，需要成批移动主

25、轴元素，时间复杂度也为O(M) 这样最坏情况下时间复杂度为O(NM)， 是不可取的。,例一 Pet,对宠物/领养人过多的情况下，我们建立一颗排序二叉树，并记录其属性Sign（宠物/领养人）。 对于命令(X,Y)，如果树为空或者X=Sign，则将其插入，并令Sign=x； 否则在树中查找符合要求的结点，记录特征值之差，并将其删除。（注意无论树的属性是0或1,相对进行的操作是相同的） 普通的排序二叉树在最坏情况下时间复杂度也是O(NM) 。我们可以应用较高效的排序二叉树，例如AVL树（平衡二叉树）或者Splay树。,例一 Pet,AVL树引入平衡因子的概念，使得整棵排序二叉树严格平衡，时间复杂度严

26、格为O(nlogm)。但是其编程复杂度很高。 Splay树通过Splay旋转操作，使得分摊时间复杂度为O(nlogm)，虽然常系数较AVL树相比大。但是操作简便，编程复杂度较低。 在考场上我们要综合考虑各方面的因素，合理的选择数据结构。,例二 郁闷的出纳员(NOI2004),你是一个公司出纳员，需要处理n条下面的命令： 此外，如果某个员工的工资低于最低工资下界Min，他就会立刻离开公司。 现在请你写一个程序完成这个工资统计的工作。,例二 郁闷的出纳员,这个题目简单来说就是请你设计一种数据结构满足如下4种操作： 向集合中插入一个数； 将集合中所有的数都加上一个值； 将集合中所有的数都减去一个值，

27、并将所有低于min的数从集合中删除掉（min是事先给定的一个固定的数）； 查找集合中第k大的数。 我们考虑应用Splay树维护这个工资系统。,例二 郁闷的出纳员,Splay树的插入、删除、查找第K大元素都可以在均摊时间复杂度O(logn)内完成。 但是还有一种操作就是将集合内的所有元素都加上或减去一个值，如果单纯的按照题目要求对数据进行改动，则每一步这样的操作所需的时间复杂度为O(NlogN)（因为需要重建二叉树）,例二 郁闷的出纳员,注意到，这个增值操作不会改变已经在树中的元素的大小关系，只会改变已经在集合内的元素与以后将要加进来的元素间的关系。这样我们就可以只改变以后要加进来的元素而不改变当前已有的元素。 具体做法为设立一个表示改变量的变量delta，遇到改值操作，只需令delta = delta + a，同时将Splay树中所有小于min-delta的元素删掉。 当新增一个值为x的元素时，只需先修改为x-delta在插入树中即可。这样改值的复杂度就为O(1)了,例二 郁闷的出纳员,通过Splay树维护工资系统，我们得到了时间复杂度为O(nlogn)的算法。 至此，问题得到解决。,