程序設(shè)計(jì)：加分二叉樹

1、加分二叉樹描述 Description 設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為（l,2,3,n），其中數(shù)字1,2,3,n為節(jié)點(diǎn)編號(hào)。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第j個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di，tree及它的每個(gè)子樹都有一個(gè)加分，任一棵子樹subtree（也包含tree本身）的加分計(jì)算方法如下：subtree的左子樹的加分 subtree的右子樹的加分subtree的根的分?jǐn)?shù)若某個(gè)子樹為主，規(guī)定其加分為1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹。試求一棵符合中序遍歷為（1,2,3,n）且加分最高的二叉樹tree。要求輸出；（1）tree的最高加分（2）tree的前序遍歷輸入格式

2、Input Format第1行：一個(gè)整數(shù)n（n30），為節(jié)點(diǎn)個(gè)數(shù)。第2行：n個(gè)用空格隔開的整數(shù)，為每個(gè)節(jié)點(diǎn)的分?jǐn)?shù)（分?jǐn)?shù)100）。輸出格式 Output Format第1行：一個(gè)整數(shù)，為最高加分（結(jié)果不會(huì)超過4,000,000,000）。第2行：n個(gè)用空格隔開的整數(shù)，為該樹的前序遍歷。樣例輸入 Sample Input55 7 1 2 10樣例輸出 Sample Output1453 1 2 4 5分析：因?yàn)橹行虮闅v節(jié)點(diǎn)編號(hào)是1,2,3,n，如果編號(hào)為i的節(jié)點(diǎn)是根節(jié)點(diǎn)，則節(jié)點(diǎn)1.i-1一定在左子樹中，而節(jié)點(diǎn)i+1,n一定在右子樹中。用數(shù)組vi,j表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j所組成的二叉樹的最大加分，則動(dòng)

3、態(tài)方程可以表示如下：vi,j=maxvi,i+vi+1,j,vi+1,i+1+vi,i*vi+2,j,vi+2,i+2+vi,i+1*vi+3,j,vj-1,j-1+vi,j-2*vj,j, vj,j+vi,j-1邊界值：VI,i=ai i=1n VI,i+1=ai+ai+1 i=1n-1題目還要求輸出最大加分樹的前序遍歷序列，因此必須在計(jì)算過程中記下從節(jié)點(diǎn)i到節(jié)點(diǎn)j所組成的最大加分二叉樹的根節(jié)點(diǎn)，用數(shù)組rooti,j表示VI,j表：（樣例數(shù)據(jù)）J=12345I=151213251452781585313224212510填表順序：左上至右下斜對(duì)角線依次填寫，V1，5即為所求。RootI,j表

4、：J=12345I=11113322233333444455參考程序：var i,j,n,d:byte; a:array1.30of byte; v:array1.30,1.30of comp; root:array1.30,1.30of byte; s,temp:comp;procedure preorder(p1,p2:byte);按前序遍歷輸出最大加分二叉樹 begin if p2=p1 then begin write(rootp1,p2, ); preorder(p1,rootp1,p2-1); preorder(rootp1,p2+1,p2); end; end;begin ass

5、ign(input,in.txt);reset(input); readln(n); for i:=1 to n do read(ai); fillchar(v,sizeof(v),0); for i:=1 to n do begin vi,i:=ai;計(jì)算單個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的加分 rooti,i:=i;記錄單個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的根節(jié)點(diǎn) end; for i:=1 to n-1 do begin vi,i+1:=ai+ai+1;計(jì)算相鄰兩個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的最大加分 rooti,i+1:=i;記錄相鄰兩個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的根節(jié)點(diǎn)；需要說明的是，兩個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹，其根節(jié)點(diǎn)可以是其中的任何一

6、個(gè)；這里選編號(hào)小的為根節(jié)點(diǎn)，則編號(hào)大的為其右子樹；若選編號(hào)大的為根節(jié)點(diǎn)，則編號(hào)小的為其左子樹；因此，最后輸出的前序遍歷結(jié)果會(huì)有部分不同，但同樣是正確的。如果最大加分二叉樹的所有節(jié)點(diǎn)的度數(shù)都是0或2，則最后輸出的前序遍歷結(jié)果是唯一的。 end; for d:=2 to n-1 do 依次計(jì)算間距為d的兩個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的最大加分 begin for i:=1 to n-d do begin s:=vi,i+vi+1,i+d;計(jì)算以i為根節(jié)點(diǎn)，以i+1至i+d間所有節(jié)點(diǎn)為右子樹的二叉樹的最大加分 rooti,i+d:=i; 記錄根節(jié)點(diǎn)i for j:=1 to d do begin temp:=vi+j,i+j+vi,i+j-1*vi+j+1,i+d;計(jì)算以i+j為根節(jié)點(diǎn)，以i至i+j-1間所有節(jié)點(diǎn)為左子樹，以i+j+1至i+d間所有節(jié)點(diǎn)為右子樹的二叉樹的最大加分 if temps then 如果此值為最大 begin s:=temp;rooti,i+d:=i+j;記下新的最大值和新的根節(jié)點(diǎn) end; end; temp:=vi,i+d-1+vi+d,i+d;計(jì)算以i+d為根節(jié)點(diǎn)，以i至i+d-1間所有節(jié)點(diǎn)為左子樹的二叉樹的最大加分 if temps then begin s:=t