3數(shù)據(jù)結(jié)構(gòu)篇第7講樹的應(yīng)用

1、第7講：樹的應(yīng)用2010/04/24一、基本題目1、樹的按層遍歷 輸入樹的結(jié)點(diǎn)以及每個(gè)結(jié)點(diǎn)的孩子（從左向右），然后按層次從根開始輸出這棵樹的結(jié)點(diǎn)信息。樹結(jié)點(diǎn)的個(gè)數(shù)不超過300，樹的度不超過10。輸入：第一行：結(jié)點(diǎn)個(gè)數(shù)n以下n行,每行描述一個(gè)結(jié)點(diǎn)的信息:結(jié)點(diǎn)編號(hào)，結(jié)點(diǎn)的權(quán)值，孩子個(gè)數(shù)，孩子結(jié)點(diǎn)編號(hào)。輸出：一行：按層遍歷的信息（權(quá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;思考：每層按關(guān)鍵字或編號(hào)遞增輸出？2、多叉樹轉(zhuǎn)二叉樹 【問題描述：】 一棵有序多叉樹都可以轉(zhuǎn)化為唯一的一棵二叉樹

3、，轉(zhuǎn)化的方法及規(guī)則是：假設(shè)有序多叉樹中結(jié)點(diǎn)t的孩子自左 到右依次為：t1，t2，。ti。轉(zhuǎn)換時(shí)：t1變成t的左孩子，t2 成為t1的右孩子，t3變成t2的右孩子，依次類推。因此我們可以得出：多叉樹轉(zhuǎn)化后的二叉樹的根沒有右孩子。如：編程實(shí)現(xiàn)：對(duì)于給定的有序多叉樹，輸出相應(yīng)二叉樹的中序遍歷序列。 【輸入：】第一行：多叉樹中的結(jié)點(diǎn)個(gè)數(shù)n（=300,樹中結(jié)點(diǎn)的編號(hào)為1到n）以下n行：結(jié)點(diǎn)v，v的孩子數(shù)量k，從左到右依次是v的孩子的編號(hào)?！据敵觯骸恳恍?，輸出多叉樹對(duì)應(yīng)二叉樹的中序遍歷結(jié)果，每?jī)蓚€(gè)結(jié)點(diǎn)之間一個(gè)空格?！緲永斎耄骸?1 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;多叉樹是無序的：兄弟間無順序（常見情況） 【輸入：】第一行：多叉樹中的結(jié)點(diǎn)個(gè)數(shù)n（

5、=300,樹中結(jié)點(diǎn)的編號(hào)為1到n）以下n行：i和j，i的父親j。父親結(jié)點(diǎn)為0的結(jié)點(diǎn)是樹根?！据敵觯骸恳恍?，輸出多叉樹對(duì)應(yīng)二叉樹的中序遍歷結(jié)果，每?jī)蓚€(gè)結(jié)點(diǎn)之間一個(gè)空格?！緲永斎耄骸?2 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; 正常情況下，我們可以根據(jù)二叉樹的先序和中序遍歷序列唯一確定其后序遍歷序列，根據(jù)二叉樹的后序和中序遍歷序列唯一確定其先序遍歷序列。但如果知道先序序列和后序序列往往不能唯一確定其中序序列。輸入： 兩 行：第一行，表示二叉樹的先序遍歷序列，第二行表示二叉樹的后序遍歷結(jié)果。序列的長(zhǎng)度=100.輸出： 可能的中序遍歷序列的數(shù)目（即滿足條件的樹的數(shù)目）。樣例：輸入：abccba輸出：43、二叉樹統(tǒng)計(jì)方法1：直接判斷 ab ba abc cba / abc bca abcd dcba abdcfeg egfcdba dagehibfc hiegbacfd 方法2：歸納：先序：X

7、 Y后序：Y X如果：那么：Y即可以是X的左孩子也可是X得右孩子統(tǒng)計(jì)符合上述條件的個(gè)數(shù)：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);補(bǔ)充：N個(gè)結(jié)點(diǎn)的二叉樹的形態(tài)數(shù)目：二、樹型動(dòng)態(tài)規(guī)劃（樹上的搜索問題）1、拾金子 【問題描述】 古老的傳說中有一個(gè)古老的游戲，游戲的名字叫拾金子。游戲的規(guī)則如下：有一樹型道路，樹中每一結(jié)點(diǎn)都有一個(gè)標(biāo)號(hào)，同時(shí)有一塊標(biāo)有質(zhì)量的金子，游戲者從最上邊根結(jié)點(diǎn)出發(fā)，遍歷若干結(jié)點(diǎn)，

8、每經(jīng)過一個(gè)結(jié)點(diǎn)都必須拿走該結(jié)點(diǎn)的金子?，F(xiàn)在規(guī)定游戲者拿走的金子數(shù)目是有限的，問怎樣走才能使得到的金子質(zhì)量最大？(第一個(gè)數(shù)是標(biāo)號(hào)，第二個(gè)是金子重量)具體問題：一棵有n個(gè)結(jié)點(diǎn)的樹（結(jié)點(diǎn)標(biāo)號(hào)是1n），從中找m個(gè)點(diǎn)，使這些點(diǎn)連通并包含根結(jié)點(diǎn)，并使得所有點(diǎn)的權(quán)值（金子質(zhì)量）和最大。（如果包含10號(hào)結(jié)點(diǎn)，則必須包含9號(hào)和1號(hào)結(jié)點(diǎn)，因?yàn)榈竭_(dá)10時(shí)必須經(jīng)過9和1結(jié)點(diǎn)）。一定含有根的共m個(gè)結(jié)點(diǎn)的最大連通分支?！据斎搿康谝恍校?n, m;以下n行；每行是：標(biāo)號(hào)父結(jié)點(diǎn)金子質(zhì)量。父親結(jié)點(diǎn)為0的結(jié)點(diǎn)是根?！据敵觥康玫降淖畲蠛??！据斎霕永?10 52 9 96 9 11 9 13 2 14 2 15 2 17 6 48

9、 6 610 1 209 0 1【樣例輸出】32數(shù)據(jù)規(guī)模：40% 1=n=10 100% 1=n=100 1=m=n 1=金子重量=10001）、先看簡(jiǎn)單情況：二叉樹【輸入樣例】 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:以結(jié)點(diǎn)v為根，選x個(gè)結(jié)點(diǎn)的最優(yōu)值。Fv,x=maxfleftv,i+av+frightv,x-i-1 0=i0 then exit;/記憶化 fv,x:=min;/=0 for i:=0 to x-1 do /枚舉左孩子數(shù)量 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件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用（容量）是vi，價(jià)值是wi。求解將哪些物品裝入背包可使價(jià)值總和最大?；舅悸愤@是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。算法一：背包算法（1）0 1背包問題方程：定義狀態(tài)：即fi,j表示前i件物品恰放入一個(gè)容量為j的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：fi,j=max fi-1,j, fi-1,j-vi+wi, j=vi 目標(biāo)：fn,v（2）完全背包問題 有N種物品和一個(gè)容

11、量為V的背包，每種物品都有無限件可用。第i種物品的費(fèi)用是vi，價(jià)值是wi。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。基本思路：每件有取0件、取1件、取2件等很多種 情況。令fi，j表示前i種物品恰放入一個(gè)容量為j的背包的最大權(quán)值 fi,j=maxfi-1,v-k*vi+ k*wi | 0=k*vi=v 回到本題：在以v為根的樹中，選x個(gè)結(jié)點(diǎn)（包括v的兒子，孫子，）node=record data:longint;/結(jié)點(diǎn)權(quán)值 son:integer; /兒子數(shù)量 ch:array1.maxn of integer;/兒子編號(hào) end;Fv,x:以v為根，選x個(gè)結(jié)

12、點(diǎn)的最優(yōu)值。Bi,j:在v的前i個(gè)兒子中，選j個(gè)結(jié)點(diǎn)的最優(yōu)值。bi,j:=max bi-1,j; /不選第i個(gè)兒子 bi-1,j-p+ftv.chi,p; (1=p=j) /從兒子i中選p個(gè)結(jié)點(diǎn) / 也可以一起：0=p0 then exit;/必須的，因?yàn)槎啻芜f歸孩子結(jié)點(diǎn) for i:=1 to tv.son do for j:=1 to x-1 do dfs(tv.chi,j);/求每個(gè)子孫結(jié)點(diǎn) 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;改進(jìn)：procedure dfs(v,x:longint); /求以v為根，包含1到x個(gè)結(jié)點(diǎn)的最優(yōu)值。求了fv,1,fv,2.fv,x var i,j:integer; begin if (v=0)or(x=0) then exit; /if fv,x0 then exit; /每個(gè)孩子只遞歸了一次，不需要 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：多叉樹轉(zhuǎn)化為二叉樹轉(zhuǎn)化后的父子關(guān)系發(fā)生了變化轉(zhuǎn)化為二叉樹后f v,x:以v為根的子樹，包含x個(gè)結(jié)點(diǎn)的最優(yōu)值，不一定必須有結(jié)點(diǎn)v：fv,x=max frightv,x： 如果不包含結(jié)點(diǎn)v（顯然也不含有左孩子），則把x全分給v的右孩子（對(duì)于于原樹結(jié)構(gòu)中的5和6） fleftv,i

15、+vi+frightv,x-i-1: i:=0.x-1：包含結(jié)點(diǎn)v的情況。解析：4的父親2，兄弟5和6：如果不從4中選x個(gè)，則只能分給兄弟5和6中選。4，5，6是3個(gè)背包問題。父親結(jié)點(diǎn)2可以不分給4結(jié)點(diǎn)，但可以給5或6多叉樹對(duì)應(yīng)二叉樹上的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保存樹的先根遍歷序編號(hào)（vi）;并保存每個(gè)子樹中節(jié)點(diǎn)數(shù)量（avi)。fi,j表示先根遍歷序中第i個(gè)編號(hào)到n個(gè)編號(hào)所有的點(diǎn)，選j個(gè)最大獲利考慮第vi這個(gè)點(diǎn)選或不選選：fi,j=fi+1,j-1+valuevi就是從i+1。n這些點(diǎn)中選j-1個(gè)，不選：fi,j=fi+avi,j。那么i這個(gè)點(diǎn)的子樹都不能選，因?yàn)橄雀闅v序，所以vi節(jié)點(diǎn)為根子樹緊跟著i，直接跳過avi個(gè)。邊界fn+

17、1,k=0(k=0.m)目標(biāo)f1,m遞歸生成先序編號(hào)序列vi和結(jié)點(diǎn)k的子樹數(shù)量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);總結(jié)：1、需要

18、掌握的算符是算法1：轉(zhuǎn)化為背包問題算法2：多叉樹轉(zhuǎn)二叉樹2、算法3特殊，具有局限性。適于于本題。3、算法1和算法2的一個(gè)小優(yōu)化：統(tǒng)計(jì)出每個(gè)個(gè)結(jié)點(diǎn)的子樹數(shù)量（兒子，孫子，）4、非常重要的一類樹型dp問題。?多叉樹轉(zhuǎn)成二叉樹=左孩子右兄弟表示法sonibrotheri2、二叉蘋果樹3、聚會(huì)的快樂有個(gè)公司要舉行一場(chǎng)晚會(huì)。為了讓到會(huì)的每個(gè)人不受他的直接上司約束而能玩得開心，公司領(lǐng)導(dǎo)決定：如果邀請(qǐng)了某個(gè)人，那么一定不會(huì)再邀請(qǐng)他的直接的上司，但該人的上司的上司，上司的上司的上司都可以邀請(qǐng)。已知每個(gè)人最多有唯一的一個(gè)上司。已知公司的每個(gè)人參加晚會(huì)都能為晚會(huì)增添一些氣氛，求一個(gè)邀請(qǐng)方案，使氣氛值的和最大。輸入

19、：第1行一個(gè)整數(shù)N（1=N=6000）表示公司的人數(shù)。接下來N行每行一個(gè)整數(shù)。第i行的數(shù)表示第i個(gè)人的氣氛值x(-128=x=127)。接下來每行兩個(gè)整數(shù)L，K。表示第K個(gè)人是第L個(gè)人的上司。輸入以0 0結(jié)束。輸出：一個(gè)數(shù)，最大的氣氛值和。樣例輸入112 3 1 1 1 4 1 5 -2 5 21 32 33 56 49 610 77 48 411 84 50 0樣例輸出20從葉子向上求本題： 所選結(jié)點(diǎn)無個(gè)數(shù)的限制。不用轉(zhuǎn)二叉樹分析設(shè)fi,0 表示根結(jié)點(diǎn)為i的子樹中,根結(jié)點(diǎn)i不參加聚會(huì)所得到的最大高興值。(整棵子樹)fi,1表示根結(jié)點(diǎn)為i參加聚會(huì)所得到的最大高興值。(整棵子樹)假設(shè)i有k個(gè)孩子

20、,分別為j1,j2,jk方程：1、當(dāng)根結(jié)點(diǎn)i不參加時(shí),任意一個(gè)孩子jm可以參加也可不參加,選最大值max(fjm,0,fjm,1).所以子樹的最大高興值=所有孩子最大高興值之和:2、當(dāng)根結(jié)點(diǎn)i參加時(shí)，他的孩子不能參加。初始化：i是葉子結(jié)點(diǎn)： Fi,0=0; Fi,1=ai;目標(biāo)： 假設(shè)t是整個(gè)樹的根： 最優(yōu)值：max(ft,0,ft,1)注意：只有i的孩子都全部求得，才能求i。所以先從葉子結(jié)點(diǎn)開始，逐級(jí)向上求，直到把根節(jié)點(diǎn)t求完為止。記錄孩子：type node=record data:integer; num:integer; son:array1.maxn of integer; end;procedure treedp(v:inte