[學(xué)科競(jìng)賽]樹型動(dòng)態(tài)規(guī)劃

《[學(xué)科競(jìng)賽]樹型動(dòng)態(tài)規(guī)劃》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、樹型動(dòng)態(tài)規(guī)劃補(bǔ)充二叉樹的遍歷的相關(guān)知識(shí)：在二叉樹的應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對(duì)全部結(jié)點(diǎn)逐一進(jìn)行某種處理。這就是二叉樹的遍歷問(wèn)題。所謂二叉樹的遍歷是指按一定的規(guī)律和次序訪問(wèn)樹中的各個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次?！霸L問(wèn)”的含義很廣，可以是對(duì)結(jié)點(diǎn)作各種處理，如輸出結(jié)點(diǎn)的信息等。遍歷一般按照從左到右的順序，共有3種遍歷方法，先（根）序遍歷，中（根）序遍歷，后（根）序遍歷。先序遍歷的操作定義如下：若二叉樹為空，則空操作，否則①訪問(wèn)根結(jié)點(diǎn)②先序遍歷左子樹③先序遍歷右子樹先序遍歷右圖結(jié)果為：124753689中序遍歷的操作定義如下：若二叉

2、樹為空，則空操作，否則①中序遍歷左子樹②訪問(wèn)根結(jié)點(diǎn)③中序遍歷右子樹中序遍歷右圖結(jié)果為：742513869后序遍歷的操作定義如下：若二叉樹為空，則空操作，否則①后序遍歷左子樹②后序遍歷右子樹③訪問(wèn)根結(jié)點(diǎn)后序遍歷右圖結(jié)果為：745289631滿二叉樹：一棵深度為h且有2^h-1個(gè)結(jié)點(diǎn)的二叉樹。滿二叉樹一定為完全二叉樹，但是完全二叉樹不一定為滿二叉樹。若設(shè)二叉樹的深度為h，除第h層外，其它各層(1～h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。滿二叉樹有如下性質(zhì)：如果一顆樹深度為h，最大層數(shù)為k，且深度與最大層數(shù)相同，

3、即k=h;1、它的葉子數(shù)是：2^(h-1)2、第k層的結(jié)點(diǎn)數(shù)是：2^(k-1)3、總結(jié)點(diǎn)數(shù)是：2^k-1(2的k次方減一)4、總節(jié)點(diǎn)數(shù)一定是奇數(shù)。完全二叉樹：若設(shè)二叉樹的深度為h，除第h層外，其它各層(1～h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。1、求pascal中二叉樹的前序遍歷給你一棵二叉樹Input輸入第一行為該樹中結(jié)點(diǎn)的個(gè)數(shù)n，第二行到第n＋1行分別為這n個(gè)結(jié)點(diǎn)的值（也代表序號(hào)），左子樹和右子樹，Output輸出二叉樹的中序遍歷SampleInput5123245300400500SampleOut

4、put42513參考程序：constmax=100;vara:array[1..max,1..3]oflongint;i,j,n:longint;s:setof1..max;proceduretree(k:longint);beginifa[k,2]<>0thentree(a[k,2]);writeln(a[k,1]);ifa[k,3]<>0thentree(a[k,3]);end;beginreadln(n);s:=[1..n];fori:=1tondobeginreadln(a[i,1],a[i,2],a[i,3]);s:=s-[a[i,2],a[

5、i,3]];end;fori:=1tondoifiinsthenbreak;tree(i);end.2、愚蠢的礦工(RQNOJ30)題目：背景Stupid家族得知在HYC家的后花園里的中央花壇處,向北走3步,向西走3步,再向北走3步,向東走3步,再向北走6步,向東走3步,向南走12步,再向西走2步(--

6、

7、)就能找到寶藏的入口,而且寶藏都是藏在山里的,必須挖出來(lái),于是Stupid家族派狗狗帶領(lǐng)礦工隊(duì)去挖寶藏.(HYC家的寶藏被狗狗挖走后有什么感想?)描述這個(gè)寶藏的制造者為了掩蓋世人耳目,他做的寶藏是沒(méi)有出口,只有入口,不少建造寶藏的人都死在里面.現(xiàn)在知

8、道寶藏總共有N個(gè)分岔口,在分岔口處是有財(cái)寶的,每個(gè)寶藏點(diǎn)都有一個(gè)財(cái)富值.狗狗只帶了M個(gè)人來(lái),而且為了安全起見(jiàn),在每個(gè)分岔口,必須至少留一個(gè)人下來(lái),這個(gè)留下來(lái)的人可以挖寶藏(每個(gè)人只能挖一個(gè)地方的寶藏),這樣才能保證不會(huì)迷路,而且這個(gè)迷宮有個(gè)特點(diǎn),任意兩點(diǎn)間有且只有一條路可通（這一句是關(guān)鍵，由此我們可以判斷用二叉樹來(lái)做）.狗狗為了讓他的00開(kāi)心,決定要盡可能地多挖些寶藏回去.現(xiàn)在狗狗的圈叉電腦不在身旁,只能求救于你了,你要知道,狗狗的終身幸福就在你手上了..（狗狗ps：00，你不能就這樣拋棄偶……）輸入/輸出格式：輸入——第1行：兩個(gè)正整數(shù)N,M.N表示

9、寶藏點(diǎn)的個(gè)數(shù),M表示狗狗帶去的人數(shù)(那是一條懶狗,他自己可不做事)。(n<=1000,m<=100)第2行：N個(gè)整數(shù),第i個(gè)整數(shù)表示第i個(gè)寶藏的財(cái)富值.(保證

10、wi

11、

12、。對(duì)于多叉樹，我們一般采用多叉樹轉(zhuǎn)化為二叉樹來(lái)簡(jiǎn)化問(wèn)題即左兒子右兄弟，這也是dfs過(guò)程中為什么