程序設計：加分二叉樹

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

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

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題目還要求輸出最大加分樹的前序遍歷序列，因此必須在計算過程中記下從節(jié)點i到節(jié)點j所組成的最大加分二叉樹的根節(jié)點，用數組rooti,j表示VI,j表：（樣例數據）J=12345I=151213251452781585313224212510填表順序：左上至右下斜對角線依次填寫，V1，5即為所求。Ro

4、otI,j表：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)

5、; end; end;begin assign(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;計算單個節(jié)點構成的二叉樹的加分 rooti,i:=i;記錄單個節(jié)點構成的二叉樹的根節(jié)點 end; for i:=1 to n-1 do begin vi,i+1:=ai+ai+1;計算相鄰兩個節(jié)點構成的二叉樹的最大加分 rooti,i+1:=i;記錄相鄰兩個節(jié)點構成的二叉樹的根節(jié)點；需

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