其他數(shù)據(jù)結構樹的遍歷

1、加分二叉樹 文件名：tree（.pas.c） 輸入文件tree.in 輸出文件tree.out問題描述：設一個 n 個節(jié)點的二叉樹 tree 的中序遍歷為（1,2,3,n），其中數(shù)字 1,2,3,n 為節(jié)點。每個節(jié)點都有一個分數(shù)（均為正整數(shù)），即第 j 個節(jié)點的分數(shù)為 dj，tree 及它的每個都有一個加分，任意棵subtree（也包含 tree 本身）的加分計算方法如下：subtree 的樹的加分*subtree 的右的加分+subtree 的根的分數(shù)若某個為空，規(guī)定其加分為 1，葉子的加分就是葉節(jié)點本身的分數(shù)，不考慮它的空。試求一棵符合中序遍歷為（1,2,3,n）且加分最高的二叉樹tree

2、。要求輸出：1）tree 的最高加分2）tree 的前序遍歷輸入格式：第 1 行：一個整數(shù) n（n30），為節(jié)點個數(shù)。第 2 行：n 個用空格隔開的整數(shù)，為每個節(jié)點的分數(shù)（分數(shù)100）。輸出格式：第 1 行：一個整數(shù)，為最高加分（結果不會超過 4,000,000,000）。第 2 行：n 個用空格隔開的整數(shù)，為該樹的前序遍歷。輸入樣例55 7 1 2 10輸出樣例1453 1 2 4 5一、題意分析1、在中序遍歷為（1,2,3,n）的各種二叉樹中，選出加分最高的一棵二叉樹，輸出最高加分和對此二叉樹的前序遍歷。加分規(guī)則：任意棵subtree（也包含 tree 本身）的加分計算方法如下：subtr

3、ee 的樹的加分*subtree 的右的加分+subtree 的根的分數(shù)為空，規(guī)定其加分為 1，葉子的加分就是葉節(jié)點本身若某個的分數(shù)，不考慮它的空。2、輸入：節(jié)點數(shù)和每個節(jié)點的分值。（n30、分值100）3 、輸出：最高加分，和此樹的前序遍歷。（結果不會超過4,000,000,000）保險可利用 double 類型。二、算法分析1、因為給出中序遍歷（1,2,3,n），所以可以以每個節(jié)點作根。當根為 i 時，則將序列分為三部分 1 至（i-1）為樹，i 為根，（i+1）至 n 為右。根據(jù)上面分析可斷定此題可利用動態(tài)規(guī)劃解決。2、根據(jù)加分規(guī)則：轉移方程如下：f(i,j)表示為 i 到為 j 的中序

4、遍歷的二叉樹的最高加分。f(1,n)即為所求最高加分。最高加分結果的劃分就是前序遍歷的結果。可以利用備忘錄形式或遞推形式完成。三、程序?qū)崿F(xiàn)Const MM=30;Type arr1=Array1.MM Ofeger;VarA:arr1;N:eger;F:Array1.MM,0.MM Of Double;S:Array1.MM Of 1.MM;輸入： Procedure Init; Var f1:text;BeginAssign(f1,);Reset(f1);Readln(f1,n);For i:=1 to N Do Read(f1,Ai);Close(f1); End;計算 F1,n的最高加分

5、Procedure Tree1;Var Max:Double;i,j,k,l:Begineger;For i:=1 to N+1 Do Fi,i-1:=1;For i:=1 to N Do Fi,i:=Ai;For j:=2 to N DoFor k:=1 to N-j+1 Do BeginMax:=0;For l:=k to k+j-1 DoIf MaxFk,l-1*Fl+1,k+j-1+Al Thenbegax:= Fk,l-1*Fl+1,k+j-1+Al;Sk,k+j-1:=l; end;Fk,k+j-1:=Max;End;End;輸出劃分方法即為前序遍歷Procedure Pr(i,j:eger);Begin If ijThen BeginWrite(si,j:2);PrPr End