nbhkdz.com冰点文库

7树的应用


一、基本题目
1、树的按层遍历
输入树的结点以及每个结点的孩子(从左向右),然后按 层次从根开始输出这棵树的结点信息。树结点的个数不超 过300,树的度不超过10。 输入: 第一行:结点个数n 以下n行,每行描述一个结点的信息: 结点编号,结点的权值,孩子个数,孩子结点编号。 输出: 一行:按层遍历的信息(权值)。

? 输入: ? 9

? 3 85 3 6 7 9

? 1 40 2 5 8
? 2 20 3 1 3 4 ? 4 67 0 ? 6 95 0
1/40

2/20

3/85

4/67

? 7 100 0
? 5 28 0 ? 8 80 0 ? 9 90 0 ? 输出: ? 20 40 85 67 28 80 95 100 90
5/28 8/80 6/95 7/100 9/90

? const ? ? type ? ? ? ? ? ?

maxn=300;

maxm=10;

tree=record data:integer; num:integer; par:integer; son:array[1..maxm] of integer; end;

bfs
? ? ? ? ? ? ? ? ? ? ? ?

head:=0; tail:=1; q[1]:=root; while head<tail do begin inc(head); k:=q[head]; write(a[k].data,' '); for i:=1 to a[k].num do begin inc(tail); q[tail]:=a[k].son[i]; end; end;

思考:每层按关键字或编号递增输出?

2、多叉树转二叉树
【问题描述:】 一棵有序多叉树都可以转化为唯一的一棵二叉树,转化的方法及规 则是:假设有序多叉树中结点t的孩子自左 到右依次为:t1,t2,。。。 ti。转换时:t1变成t的左孩子,t2 成为t1的右孩子,t3变成t2的右孩 子,依次类推。因此我们可以得出:多叉树转化后的二叉树的根没有右 孩子。如:

编程实现:对于给定的有序多叉树,输出相应二叉树的中序遍历序列。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

【输入:】 第一行:多叉树中的结点个数n(<=300,树中结点的编号为1到n) 以下n行:结点v,v的孩子数量k,从左到右依次是v的孩子的编号。 【输出:】 一行,输出多叉树对应二叉树的中序遍历结果,每两个结点之间一个空格。 【样例输入:】 7 1 3 2 3 4 2 2 5 6 3 0 4 1 7 5 0 6 0 7 0 【样例输出:】 5 6 2 3 7 4 1

? // left,right:array[1..maxn] of integer; ? // par:array[1..maxn] of integer; ? readln(n); ? for i:=1 to n do ? ?

?
? ? ? ? ? ? ?

begin read(v); read(k); if k<>0 then begin read(u); par[u]:=v;left[v]:=u; for j:=1 to k-1 do begin read(p); par[p]:=v; right[u]:=p; u:=p; end; end; writeln; end;

多叉树是无序的:兄弟间无顺序(常见情况)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

【输入:】 第一行:多叉树中的结点个数n(<=300,树中结点的编号为1到n) 以下n行:i和j,i的父亲j。父亲结点为0的结点是树根。 【输出:】 一行,输出多叉树对应二叉树的中序遍历结果,每两个结点之间一个 空格。 【样例输入:】 7 2 1 3 1 4 1 5 2 6 2 7 4 1 0 【样例输出:】 7 4 3 6 5 2 1

方法:新读入的孩子作为他的左孩子,前插。
7 2 3 4 5 6 7 1
1 1 1 2 2 4 0
1 4 3 7 5 6 7 6 5 2 1

2

3

4

? readln(n); ? for i:=1 to n do ? begin ? read(u,v); ? if v=0 then root:=u ? else ? if left[v]=0 then left[v]:=u ? else begin ? right[u]:=left[v]; ? left[v]:=u; ? end; ? end;

3、二叉树统计
正常情况下,我们可以根据二叉树的先序和中序遍历序列唯一确定其后序 遍历序列,根据二叉树的后序和中序遍历序列唯一确定其先序遍历序列。但 如果知道先序序列和后序序列往往不能唯一确定其中序序列。 输入: 两 行:第一行,表示二叉树的先序遍历序列,第二行表示二叉树的后序遍 历结果。序列的长度<=100.

输出:
可能的中序遍历序列的数目(即满足条件的树的数目)。 样例: 输入: abc cba 输出: 4

方法1:直接判断

方法2:

(1) ab ba

(2) abc
(3) abcd

cba // abc bca
dcba

(4) abdcfeg
(5) dagehibfc

egfcdba
hiegbacfd

归纳:
如果: 先序:…X Y…
后序:…Y X…

那么:Y即可以是X的左孩子也可是X得右孩子

统计符合上述条件的个数:
? tot:=0;
? for i:=1 to length(st1)-1 do ?

?
? ?

?

begin p:=pos(st1[i],st2); if (p<>1)and(st1[i+1]=st2[p-1])then inc(tot); end; writeln(1 shl tot);

补充:N个结点的二叉树的形态数目:

f[n] ? f[0] * f[n ? 1] ? f[1] * f[n ? 2] ? ... ? f[n ? 1] * f[0] ? ? f[i] * f[n ? i ? 1]
i ?0 n ?1

1 n ? C2 n n ?1

二、树型动态规划(树上的搜索问题)

1、拾金子
【问题描述】 古老的传说中有一个古老的游戏,游戏的名字叫拾金子。 游戏的规则如下: 有一树型道路,树中每一结点都有一个标号,同时有一块标有质量的金子, 游戏者从最上边根结点出发,遍历若干结点,每经过一个结点都必须拿走该结点 的金子。现在规定游戏者拿走的金子数目是有限的,问怎样走才能使得到的金子 质量最大? (第一个数是标号,第二个是金子重量) 具体问题: 一棵有n个结点的树(结点标号是1…n),从中找m个点,使这些点连通并包 含根结点,并使得所有点的权值(金子质量)和最大。(如果包含10号结点,则 必须包含9号和1号结点,因为到达10时必须经过9和1结点)。一定含有根的共m 个结点的最大连通分支。 【输入】 第一行: n, m; 以下n行;每行是: 标号 父结点 金子质量。父亲结点为0的结点是根。 【输出】 得到的最大和。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

【输入样例】 10 5 2 9 9 6 9 1 1 9 1 3 2 1 4 2 1 5 2 1 7 6 4 8 6 6 10 1 20 9 0 1 【样例输出】 32 数据规模: 40% 1<=n<=10 100% 1<=n<=100 1<=m<=n

1<=金子重量<=1000

1)、先看简单情况:二叉树
? 【输入样例】 ? 10 5 ? 2 9 9 ? 1 9 1 ? 3 2 1 ? 4 5 1 ? 5 2 1 ? 7 6 4 ? 8 6 6

? 10 1 20
? 6 10 1 ? 9 0 1 ? 【样例输出】 ? 32

分析:
? F[v,x]:以结点v为根,选x个结点的最优值。

F[v,x]=max{f[left[v],i]+a[v]+f[right[v],x-i-1]} 0<=i<=x 0:(V=0 or x=0)

目标:f[root,m]

建立二叉树:
? readln(n,m); ? for i:=1 to n do ? ? ? ? ?

?

begin read(u,v);readln(a[u]); if v=0 then root:=u else if left[v]=0 then left[v]:=u else right[v]:=u; end;

求以v为根,取x个结点的最优值
? ?

?
? ? ? ? ? ? ? ? ? ?

?

procedure dp(v,x:integer); var ans:longint; i:integer; begin if (v=0)or(x=0) then begin f[v,x]:=0; exit; end; if f[v,x]>0 then exit;//记忆化 f[v,x]:=min;//=0 for i:=0 to x-1 do //枚举左孩子数量 begin dp(left[v],i); dp(right[v],x-i-1); f[v,x]:=max(f[v,x],f[left[v],i]+a[v]+f[right[v],x-i-1]); end; end;

2)本题:多叉树
算法一:背包算法
(1)0 1背包问题
? 有N件物品和一个容量为V的背包。第i件物品的费用

(容量)是v[i],价值是w[i]。求解将哪些物品装入背 包可使价值总和最大。 ? 基本思路 ? 这是最基础的背包问题,特点是:每种物品仅有一件, 可以选择放或不放。

方程:
? 定义状态:即f[i,j]表示前i件物品恰放入一个容量为j的
?

?
? ?

背包可以获得的最大价值。 则其状态转移方程便是: f[i,j]=max{ f[i-1,j], f[i-1,j-v[i]]+w[i], j>=v[i] 目标:f[n,v]

}

(2)完全背包问题
? 有N种物品和一个容量为V的背包,每种物品都有无限

件可用。第i种物品的费用是v[i],价值是w[i]。 ? 求解将哪些物品装入背包可使这些物品的费用总和不 超过背包容量,且价值总和最大。

? 基本思路: ? 每件有取0件、取1件、取2件……等很多种 情况。 ? 令f[i,j]表示前i种物品恰放入一个容量为j的背包的最

大权值 ? f[i,j]=max{f[i-1,v-k*v[i]]+ k*w[i] | 0<=k*v[i]<=v}

回到本题:
v / x

ch[1]

ch[2]

ch[3]

ch[m]

?

?

?

?

在以v为根的树中,选x个结点(包括v的儿子,孙子,…)

? node=record

?
? ?

?

data:longint;//结点权值 son:integer; //儿子数量 ch:array[1..maxn] of integer;//儿子编号 end;

? F[v,x]:以v为根,选x个结点的最优值。 ? B[i,j]:在v的前i个儿子中,选j个结点的最优值。

b[i,j]:=max{ b[i-1,j]; //不选第i个儿子 b[i-1,j-p]+f[t[v].ch[i],p]; (1<=p<=j) //从儿子i中选p个结点 } // 也可以一起:0<=p<=j 范围: i=1..t[v].son // t[v].son 是v的儿子数量 J=1..x-1

f[v,x]:=b[t[v].son,x-1] + t[v].data;

? procedure dfs(v,x:longint); ? //求以v为根,包含x个结点的最优值。只记录了f[v,x],多次递归孩子 ? var i,j:integer; ? begin ? if (v=0)or(x=0) then exit; ? if f[v,x]>0 then exit;//必须的,因为多次递归孩子结点 ? for i:=1 to t[v].son do ? for j:=1 to x-1 do dfs(t[v].ch[i],j);//求每个子孙结点 ? for i:=1 to t[v].son do ? for j:=1 to x-1 do ? begin ? b[i,j]:=b[i-1,j]; ? for p:=1 to j do ? if b[i-1,j-p]+f[t[v].ch[i],p]>b[i,j] then ? b[i,j]:=b[i-1,j-p]+f[t[v].ch[i],p]; ? end; ? f[v,x]:=t[v].data+b[t[v].son,x-1]; ? end;

改进:
? procedure dfs(v,x:longint); ? //求以v为根,包含1到x个结点的最优值。求了f[v,1],f[v,2]...f[v,x] ? var i,j:integer; ? begin ? if (v=0)or(x=0) then exit; ? //if f[v,x]>0 then exit; //每个孩子只递归了一次,不需要 ? for i:=1 to t[v].son do dfs(t[v].ch[i],x-1); ? for i:=1 to t[v].son do ? for j:=1 to x-1 do ? begin ? b[i,j]:=b[i-1,j]; ? for p:=1 to j do ? if b[i-1,j-p]+f[t[v].ch[i],p]>b[i,j] then ? b[i,j]:=b[i-1,j-p]+f[t[v].ch[i],p]; ? end; ? for j:=1 to x do //记录 ? f[v,j]:=b[t[v].son,j-1]+t[v].data; ? end;

算法2:多叉树转化为二叉树
1 1 3

2

2 3

4

5

6

4 5 7 6 8 10 9

7

8

9

10

转化后的父子关系发生了变化

? 转化为二叉树后f [v,x]:以v为根的子树,包含x个结点的

最优值,不一定必须有结点v: ? f[v,x]=max{ f[right[v,x]: ? 如果不包含结点v(显然也不含有左孩子), 则把x全分给v的右孩子(对于于原树结构中的5和6) ? f[left[v],i]+v[i]+f[right[v],x-i-1]: i:=0..x-1:包含结点v的情况。}
? 解析: ? 4的父亲2,兄弟5和6:如果不从4中选x个,则只能分给兄

弟5和6中选。4,5,6是3个背包问题。 ? 父亲结点2可以不分给4结点,但可以给5或6

多叉树对应二叉树上的dp
? procedure dp(v,x:integer); ? ? ? ?

?
? ? ?

?
? ?

var i:integer; begin if (v=0)or(x=0) then exit; if f[v,x]>0 then exit; dp(right[v],x); f[v,x]:=f[right[v],x]; for i:=0 to x-1 do begin dp(left[v],i); dp(right[v],x-i-1); f[v,x]:=max(f[v,x],f[left[v],i]+a[v]+f[right[v],x-i-1]); end; end;

算法3:在先序遍历的序列上直接dp

保存树的先根遍历序编号(v[i]);并保存每个子树中节点数量(a[v[i]])。 i v[i] 1 9 2 2 4 3 3 1 4 4 1 5 5 1 6 6 3 7 7 1 8 8 1 9 1 2 10 10 1

a[v[i]] 10

? f[i,j]表示先根遍历序中第i个编号到n个编号所有的点, ? ? ?

?

?

选j个最大获利 考虑第v[i]这个点选或不选 选:f[i,j]=f[i+1,j-1]+value[v[i]]就是从i+1。。n这 些点中选j-1个, 不选:f[i,j]=f[i+a[v[i]],j]。那么i这个点的子树都不 能选,因为先根遍历序,所以v[i]节点为根子树紧跟着i, 直接跳过a[v[i]]个。 边界f[n+1,k]=0(k=0..m) 目标f[1,m]

递归生成先序编号序列v[i]和结点k的子树数量a[k]
? ? ? ? ? ? ? ? ? ? ? ? ? ?

procedure dfs(k:integer);//深搜先序遍历生成a和v var i:integer; begin if k<>0 then begin inc(p); v[p]:=k; a[k]:=1; for i:=1 to t[k].son do begin dfs(t[k].ch[i]); a[k]:=a[k]+a[t[k].ch[i]]; end; end; end;

Dp求解:
? for i:=n downto 1 do
? ?

?

for j:=1 to m do f[i,j]:=max(f[i+1,j-1]+t[v[i]].data, f[i+a[v[i]],j]);

总结:
1、需要掌握的算符是 ? 算法1:转化为背包问题 ? 算法2:多叉树转二叉树 2、算法3特殊,具有局限性。适于于本题。 3、算法1和算法2的一个小优化:统计出每个 个结点的子树数量(儿子,孙子,…) 4、非常重要的一类树型dp问题。

多叉树转成二叉树=左孩子右兄弟表示法

father

?
i
right[i]

son[i]

left[i]

……

brother[i]

……

2、二叉苹果树

3、聚会的快乐
? 有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约

? ? ? ?

?
? ? ? ?

束而能玩得开心,公司领导决定:如果邀请了某个人,那么一定不会 再邀请他的直接的上司,但该人的上司的上司,上司的上司的上 司……都可以邀请。已知每个人最多有唯一的一个上司。 已知公司的每个人参加晚会都能为晚会增添一些气氛,求一个邀请方 案,使气氛值的和最大。 输入: 第1行一个整数N(1<=N<=6000)表示公司的人数。 接下来N行每行一个整数。第i行的数表示第i个人的气氛值 x(-128<=x<=127)。 接下来每行两个整数L,K。表示第K个人是第L个人的上司。 输入以0 0结束。 输出: 一个数,最大的气氛值和。

? 样例输入

? ? ? ? ? ? ? ? ? ? ? ? ?

11 2 3 1 1 1 4 1 5 -2 5 2 5(1) 1 3 2 3 3(1) 4(1) 3 5 6 4 1(2) 2(3) 6(4) 7(1) 9 6 10 7 10(5) 7 4 9(-2) 8 4 11 8 从叶子向上求 4 5 0 0

8(5)

11(2)

? 样例输出 ? 20

分析
? 本题:

所选结点无个数的限制。不用转二叉树

设f[i,0] 表示根结点为i的子树中,根结点i不参加聚会所得到的最大 高兴值。(整棵子树) f[i,1]表示根结点为i参加聚会所得到的最大高兴值。(整棵子树) 假设i有k个孩子,分别为j1,j2,…,jk 方程: 1、当根结点i不参加时,任意一个孩子jm可以参加也可不参 加,选最大值max(f[jm,0],f[jm,1]).所以子树的最大高兴值 =所有孩子最大高兴值之和:

f[i,0] ? ? max(f[j m,0], f[j m,1])
m ?1

k

2、当根结点i参加时,他的孩子不能参加。

f[i,1] ? ? f[jm,0] ? a[i]
m ?1

k

注意:只有i的孩子都全部求得,才能求i。所以先从叶子结 点开始,逐级向上求,直到把根节点t求完为止。
初始化:i是叶子结点: F[i,0]=0; F[i,1]=a[i]; 目标: 假设t是整个树的根: 最优值:max(f[t,0],f[t,1])

记录孩子:
? type
? ?

?
? ?

node=record data:integer; num:integer; son:array[1..maxn] of integer; end;

? procedure treedp(v:integer); ? var i,k:integer; ? begin ? {if t[v].num=0 then ? begin ? f[0,v]:=0; f[1,v]:=t[v].data; ? exit; ? end;} //可以不写 ? f[0,v]:=0; f[1,v]:=t[v].data; ? for i:=1 to t[v].num do ? begin ? k:=t[v].son[i]; ? treedp(k); ? f[0,v]:=f[0,v]+max(f[0,k],f[1,k]); ? f[1,v]:=f[1,v]+f[0,k]; ? end; ? end;

记录父亲:节省空间
? ?

?

a:array[1..maxn] of integer;//权值 par:array[1..maxn] of integer; son:array[1..maxn] of boolean; //有无儿子

每个结点只记录他的父亲结点。 找结点i的孩子时,通过如下方式判断j时否为i的孩子。 For j:=1 to if n do treedp(j)

father[j]=i then

主程序: writeln(max(f[root,0],f[root,1]));

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

procedure treedp(k:integer); var i:integer; begin { if not son[k] then begin f[0,k]:=0; f[1,k]:=a[k]; exit; end;} f[0,k]:=0; f[1,k]:=a[k]; for i:=1 to n do if par[i]=k then begin treedp(i); f[0,k]:=f[0,k]+max(f[0,i],f[1,i]); f[1,k]:=f[1,k]+f[0,i]; end; end;

4、皇宫看守


决策树及应用

决策树及应用_计算机软件及应用_IT/计算机_专业资料。第 5 章 决策树及应用 ...(4,5,11,12,21,22,23)共 7 条记录, 这 7 条记录都是属于 P 类的,...

实验七 二叉树的其他典型算法及其应用(1)

实验七 二叉树的其他典型算法及其应用 一、实验目的 1、深入了解二叉树递归遍历算法的执行过程,熟练掌握二叉树先序非递归遍历算法、 中序非递归算法及其应用。 2、...

实验七 哈夫曼树的建立与应用

浙江大学城市学院实验报告课程名称 实验项目名称 实验成绩 实验七 数据结构与算法 哈夫曼树的建立与应用 日期 指导老师(签名 ) 一. 实验目的和要求 1、 掌握哈...

7-1实验七报告(二叉树的相关操作)

实验器材(软件) :Computer,Windows OS,VC++ 实验过程记录: 1、二叉树的遍历及其应用 (1) 请实现二叉树的创建 (2) 并对创建好的二叉树分别进行先序、中序、...

4角规测树原理及应用

4角规测树原理及应用_信息与通信_工程科技_专业资料。角规测树基本原理(重点:同心圆原理)及应用 [提要]在介绍角规测定林分每公顷胸高断面积原理的基础上,还介...

设备树使用手册

设备树使用手册_计算机软件及应用_IT/计算机_专业资料。设备树使用手册本文将介绍...{ compatible = "maxim,ds1338"; reg = <58>; interrupts = < 7 3 >;...

树木学实习木本植物系统名录7

树木学实习木本植物系统名录7_实习总结_总结/汇报_应用文书。二十二.桑科 Moraceae (一)桑属 Morus Linn 1、蒙桑 Morus mongolica Schneid. 采集地:花溪水库 海...

10章 树补充习题

10章 树补充习题_计算机软件及应用_IT/计算机_专业资料。1.一棵无向树 T 有...最优树的权为:W(T)=(3+4)×4+7×3+(5+6)×3+(8+9)×2=116。 ...

树结构实验报告

树结构实验报告_计算机软件及应用_IT/计算机_专业资料。树结构实验报告附件...D-7,E-2,F-8,G-13,H-4,I-1 路径 2 权值=5 + 4 + 11 + 2 = ...

数据结构练习 第六章 树

数据结构练习 第六章 树_计算机软件及应用_IT/计算机_专业资料。数据结构练习 ...具有 4 个结点的二叉树可有( ) A.4 种形态 B.7 种形态 C.10 种形态 ...