3数据结构篇第7讲树的应用

1、第7讲：树的应用2010/04/24一、基本题目1、树的按层遍历 输入树的结点以及每个结点的孩子（从左向右），然后按层次从根开始输出这棵树的结点信息。树结点的个数不超过300，树的度不超过10。输入：第一行：结点个数n以下n行,每行描述一个结点的信息:结点编号，结点的权值，孩子个数，孩子结点编号。输出：一行：按层遍历的信息（权值）。输入：93 85 3 6 7 91 40 2 5 82 20 3 1 3 44 67 06 95 07 100 05 28 08 80 09 90 0输出：20 40 85 67 28 80 95 100 90const maxn=300; maxm=10;type

2、 tree=record data:integer; num:integer; par:integer; son:array1.maxm of integer; end;bfs head:=0; tail:=1; q1:=root; while headtail do begin inc(head); k:=qhead; write(ak.data, ); for i:=1 to ak.num do begin inc(tail); qtail:=ak.soni; end; end;思考：每层按关键字或编号递增输出？2、多叉树转二叉树 【问题描述：】 一棵有序多叉树都可以转化为唯一的一棵二叉树

3、，转化的方法及规则是：假设有序多叉树中结点t的孩子自左 到右依次为：t1，t2，。ti。转换时：t1变成t的左孩子，t2 成为t1的右孩子，t3变成t2的右孩子，依次类推。因此我们可以得出：多叉树转化后的二叉树的根没有右孩子。如：编程实现：对于给定的有序多叉树，输出相应二叉树的中序遍历序列。 【输入：】第一行：多叉树中的结点个数n（=300,树中结点的编号为1到n）以下n行：结点v，v的孩子数量k，从左到右依次是v的孩子的编号。【输出：】一行，输出多叉树对应二叉树的中序遍历结果，每两个结点之间一个空格。【样例输入：】71 3 2 3 42 2 5 63 04 1 75 06 07 0【样例输出

4、：】5 6 2 3 7 4 1 / left,right:array1.maxn of integer;/ par:array1.maxn of integer;readln(n);for i:=1 to n do begin read(v); read(k); if k0 then begin read(u); paru:=v;leftv:=u; for j:=1 to k-1 do begin read(p); parp:=v; rightu:=p; u:=p; end; end; writeln; end;多叉树是无序的：兄弟间无顺序（常见情况） 【输入：】第一行：多叉树中的结点个数n（

5、=300,树中结点的编号为1到n）以下n行：i和j，i的父亲j。父亲结点为0的结点是树根。【输出：】一行，输出多叉树对应二叉树的中序遍历结果，每两个结点之间一个空格。【样例输入：】72 13 14 15 26 27 41 0【样例输出：】7 4 3 6 5 2 1 方法：新读入的孩子作为他的左孩子，前插。72 13 14 15 26 27 41 0readln(n);for i:=1 to n do begin read(u,v); if v=0 then root:=u else if leftv=0 then leftv:=u else begin rightu:=leftv; leftv

6、:=u; end; end; 正常情况下，我们可以根据二叉树的先序和中序遍历序列唯一确定其后序遍历序列，根据二叉树的后序和中序遍历序列唯一确定其先序遍历序列。但如果知道先序序列和后序序列往往不能唯一确定其中序序列。输入： 两 行：第一行，表示二叉树的先序遍历序列，第二行表示二叉树的后序遍历结果。序列的长度=100.输出： 可能的中序遍历序列的数目（即满足条件的树的数目）。样例：输入：abccba输出：43、二叉树统计方法1：直接判断 ab ba abc cba / abc bca abcd dcba abdcfeg egfcdba dagehibfc hiegbacfd 方法2：归纳：先序：X

7、 Y后序：Y X如果：那么：Y即可以是X的左孩子也可是X得右孩子统计符合上述条件的个数：tot:=0;for i:=1 to length(st1)-1 do begin p:=pos(st1i,st2); if (p1)and(st1i+1=st2p-1)then inc(tot); end;writeln(1 shl tot);补充：N个结点的二叉树的形态数目：二、树型动态规划（树上的搜索问题）1、拾金子 【问题描述】 古老的传说中有一个古老的游戏，游戏的名字叫拾金子。游戏的规则如下：有一树型道路，树中每一结点都有一个标号，同时有一块标有质量的金子，游戏者从最上边根结点出发，遍历若干结点，

8、每经过一个结点都必须拿走该结点的金子。现在规定游戏者拿走的金子数目是有限的，问怎样走才能使得到的金子质量最大？(第一个数是标号，第二个是金子重量)具体问题：一棵有n个结点的树（结点标号是1n），从中找m个点，使这些点连通并包含根结点，并使得所有点的权值（金子质量）和最大。（如果包含10号结点，则必须包含9号和1号结点，因为到达10时必须经过9和1结点）。一定含有根的共m个结点的最大连通分支。【输入】第一行： n, m;以下n行；每行是：标号父结点金子质量。父亲结点为0的结点是根。【输出】得到的最大和。【输入样例】 10 52 9 96 9 11 9 13 2 14 2 15 2 17 6 48

9、 6 610 1 209 0 1【样例输出】32数据规模：40% 1=n=10 100% 1=n=100 1=m=n 1=金子重量=10001）、先看简单情况：二叉树【输入样例】 10 52 9 91 9 13 2 14 5 15 2 17 6 48 6 610 1 206 10 19 0 1【样例输出】32分析：Fv,x:以结点v为根，选x个结点的最优值。Fv,x=maxfleftv,i+av+frightv,x-i-1 0=i0 then exit;/记忆化 fv,x:=min;/=0 for i:=0 to x-1 do /枚举左孩子数量 begin dp(leftv,i); dp(ri

10、ghtv,x-i-1); fv,x:=max(fv,x,fleftv,i+av+frightv,x-i-1); end;end;2）本题：多叉树有N件物品和一个容量为V的背包。第i件物品的费用（容量）是vi，价值是wi。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。算法一：背包算法（1）0 1背包问题方程：定义状态：即fi,j表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。则其状态转移方程便是：fi,j=max fi-1,j, fi-1,j-vi+wi, j=vi 目标：fn,v（2）完全背包问题 有N种物品和一个容

11、量为V的背包，每种物品都有无限件可用。第i种物品的费用是vi，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路：每件有取0件、取1件、取2件等很多种 情况。令fi，j表示前i种物品恰放入一个容量为j的背包的最大权值 fi,j=maxfi-1,v-k*vi+ k*wi | 0=k*vi=v 回到本题：在以v为根的树中，选x个结点（包括v的儿子，孙子，）node=record data:longint;/结点权值 son:integer; /儿子数量 ch:array1.maxn of integer;/儿子编号 end;Fv,x:以v为根，选x个结

12、点的最优值。Bi,j:在v的前i个儿子中，选j个结点的最优值。bi,j:=max bi-1,j; /不选第i个儿子 bi-1,j-p+ftv.chi,p; (1=p=j) /从儿子i中选p个结点 / 也可以一起：0=p0 then exit;/必须的，因为多次递归孩子结点 for i:=1 to tv.son do for j:=1 to x-1 do dfs(tv.chi,j);/求每个子孙结点 for i:=1 to tv.son do for j:=1 to x-1 do begin bi,j:=bi-1,j; for p:=1 to j do if bi-1,j-p+ftv.chi,p

13、bi,j then bi,j:=bi-1,j-p+ftv.chi,p; end; fv,x:=tv.data+btv.son,x-1; end;改进：procedure dfs(v,x:longint); /求以v为根，包含1到x个结点的最优值。求了fv,1,fv,2.fv,x var i,j:integer; begin if (v=0)or(x=0) then exit; /if fv,x0 then exit; /每个孩子只递归了一次，不需要 for i:=1 to tv.son do dfs(tv.chi,x-1); for i:=1 to tv.son do for j:=1 to

14、x-1 do begin bi,j:=bi-1,j; for p:=1 to j do if bi-1,j-p+ftv.chi,pbi,j then bi,j:=bi-1,j-p+ftv.chi,p; end; for j:=1 to x do /记录 fv,j:=btv.son,j-1+tv.data; end;算法2：多叉树转化为二叉树转化后的父子关系发生了变化转化为二叉树后f v,x:以v为根的子树，包含x个结点的最优值，不一定必须有结点v：fv,x=max frightv,x： 如果不包含结点v（显然也不含有左孩子），则把x全分给v的右孩子（对于于原树结构中的5和6） fleftv,i

15、+vi+frightv,x-i-1: i:=0.x-1：包含结点v的情况。解析：4的父亲2，兄弟5和6：如果不从4中选x个，则只能分给兄弟5和6中选。4，5，6是3个背包问题。父亲结点2可以不分给4结点，但可以给5或6多叉树对应二叉树上的dpprocedure dp(v,x:integer); var i:integer; begin if (v=0)or(x=0) then exit; if fv,x0 then exit; dp(rightv,x); fv,x:=frightv,x; for i:=0 to x-1 do begin dp(leftv,i); dp(rightv,x-i-1

16、); fv,x:=max(fv,x,fleftv,i+av+frightv,x-i-1); end; end;算法3：在先序遍历的序列上直接dpi12345678910vi92345678110avi10411131121保存树的先根遍历序编号（vi）;并保存每个子树中节点数量（avi)。fi,j表示先根遍历序中第i个编号到n个编号所有的点，选j个最大获利考虑第vi这个点选或不选选：fi,j=fi+1,j-1+valuevi就是从i+1。n这些点中选j-1个，不选：fi,j=fi+avi,j。那么i这个点的子树都不能选，因为先根遍历序，所以vi节点为根子树紧跟着i，直接跳过avi个。边界fn+

17、1,k=0(k=0.m)目标f1,m递归生成先序编号序列vi和结点k的子树数量ak procedure dfs(k:integer);/深搜先序遍历生成a和v var i:integer; begin if k0 then begin inc(p); vp:=k; ak:=1; for i:=1 to tk.son do begin dfs(tk.chi); ak:=ak+atk.chi; end; end; end;Dp求解：for i:=n downto 1 do for j:=1 to m do fi,j:=max(fi+1,j-1+tvi.data, fi+avi,j);总结：1、需要

18、掌握的算符是算法1：转化为背包问题算法2：多叉树转二叉树2、算法3特殊，具有局限性。适于于本题。3、算法1和算法2的一个小优化：统计出每个个结点的子树数量（儿子，孙子，）4、非常重要的一类树型dp问题。?多叉树转成二叉树=左孩子右兄弟表示法sonibrotheri2、二叉苹果树3、聚会的快乐有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司都可以邀请。已知每个人最多有唯一的一个上司。已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。输入

19、：第1行一个整数N（1=N=6000）表示公司的人数。接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128=x=127)。接下来每行两个整数L，K。表示第K个人是第L个人的上司。输入以0 0结束。输出：一个数，最大的气氛值和。样例输入112 3 1 1 1 4 1 5 -2 5 21 32 33 56 49 610 77 48 411 84 50 0样例输出20从叶子向上求本题： 所选结点无个数的限制。不用转二叉树分析设fi,0 表示根结点为i的子树中,根结点i不参加聚会所得到的最大高兴值。(整棵子树)fi,1表示根结点为i参加聚会所得到的最大高兴值。(整棵子树)假设i有k个孩子

20、,分别为j1,j2,jk方程：1、当根结点i不参加时,任意一个孩子jm可以参加也可不参加,选最大值max(fjm,0,fjm,1).所以子树的最大高兴值=所有孩子最大高兴值之和:2、当根结点i参加时，他的孩子不能参加。初始化：i是叶子结点： Fi,0=0; Fi,1=ai;目标： 假设t是整个树的根： 最优值：max(ft,0,ft,1)注意：只有i的孩子都全部求得，才能求i。所以先从叶子结点开始，逐级向上求，直到把根节点t求完为止。记录孩子：type node=record data:integer; num:integer; son:array1.maxn of integer; end;procedure treedp(v:inte