連云港市贛榆縣外國語學(xué)校

1、JSOI 函授第一次作業(yè)解題連云港市贛榆縣外國語學(xué)校題一：二叉樹的查找已知一課二叉樹用鄰接表結(jié)構(gòu)結(jié)點。，中序查找二叉樹中值為 x 的結(jié)點，并是第幾個例：如圖二叉樹的數(shù)據(jù)文件的數(shù)據(jù)格式如下70 021 0 0第一行 n 為二叉樹的結(jié)點個樹，n=100；第二行 x 表示要查找的結(jié)點的值；以下第一列數(shù)據(jù)是各結(jié)點的值，第二列數(shù)據(jù)是左兒子結(jié)點輸出一個數(shù) m 即按中序查找的第 m 個結(jié)點。本例的輸出樣例4，第三列數(shù)據(jù)是右兒子結(jié)點。問題分析這道問題的不過是的基本功對鄰接矩陣的二叉樹的遍歷問題，函授講義中也講到，二叉樹的本身的定義就是一個遞歸的定義，因此，用遞歸過程來來解決這道問題是最好不過了。算法分析就以輸

2、入樣例中所提供的二叉樹為例：題目要求用中序來進行查找，中序查找的順序為左中右，非常簡單的遞歸程序，就可以把它搞定。但是，如果不用遞歸的話，這道題目又會怎么樣呢？那會有許許多多的 while 語句，天哪，象我這種初學(xué)的菜鳥，還是老老實實的用遞歸吧，好，言歸正傳。程序的算法流程如下：(1)試探其樹是否為空；(2)若不為空，則繼續(xù)將指針指向樹；進行(1)(3)若為空，則將計數(shù)器加一，判斷是否找到所需要地結(jié)點；進行(5)(4) 試探其右是否為空；(5) 若不為空，則繼續(xù)將指針指向右；進行(1);不難看出，以上過程就是一個遞歸的過程，而且思路很清楚，那么，開始編程吧。數(shù)據(jù)結(jié)構(gòu)無非是三個數(shù)組，沒什么好說的

3、。程序：program tree(input,output); var l,r,d:array1.5000 of i,m,n:eger;f1,f2:text;eger;procedure tree(var i:eger;n,m:eger);真正的好戲開場了beginif ln0 then tree(i,ln,m); if dn=m thenbegininc(i);計數(shù)器加 1write(f2,i);樹是否為空，是進還是退呢exit;有些偷懶，直接用了，呵呵 end elseinc(i);計數(shù)器加 1if rn0 then tree(i,rn,m);樹是否為空，是進還是退呢end; begina

4、ssign(f1,tree.in);assign(f2,tree.out); reset(f1); rewrite(f2); readln(f1,n);readln(f1,m); for i:=1 to n doreadln(f1,di,li,ri);讀入數(shù)據(jù)i:=0;tree(i,1,m); close(f1); close(f2); end.測試數(shù)據(jù)我定義的是據(jù)，無非是只有eger，太大的數(shù)據(jù)過不去，用 fp 就行了，看不出這題能的數(shù)樹，只有右，滿二叉樹，完全二叉樹，不必多談。題二：求后序圖中的一棵二叉樹，其前序遍歷為 ABDRGCFHI，中序遍歷為 DBGEACHFI，后序遍歷為 DGE

5、BHIFCA?？梢宰C明，在已知前序和中序遍歷的情況下，可以唯一確定二叉樹的后序遍歷。你的任務(wù)就是根據(jù)給出的前序和中序遍歷，輸出后序遍歷。輸入格式第一行一個字符串，表示樹的前序遍歷。第二行一個字符串，表示樹的中序遍歷。樹的結(jié)點一律用小寫字母表示。輸出格式輸出樹的后序遍歷。樣例輸入ABDEGCFHI DBGEACHFI樣例輸出DGEBHIFCA問題分析：這題與 noip2001 年復(fù)賽普及組的第三題極為相似，不過是 noip 中是有中序和后序，求前序；而這題是有前序和中序，求后序，無所謂了，反正算法和思路都差不多。下面以輸入樣例中的為例，講一下這題的思路：對于這種經(jīng)典的題目，編程之前必需要在紙上畫

6、一畫，說不定靈感很快就來了。前序遍歷是什么，很簡單，中、左、右，那么中序呢，很簡單，左、中、右，所以，輸入的前序遍歷的二叉樹，第一個節(jié)點必然是這個二叉樹的頭結(jié)點，這用，別急，所以中序遍歷中 A 的左邊(前邊)必然是這棵大樹的樹，同樣，前序遍歷中 A 的右面（后面）便是這顆大樹的右，繼而，樹的前序遍歷和后序遍歷的結(jié)果便可以從輸入的前序遍歷和中序遍歷中分離出來(好像很簡單嘛)，然后繼續(xù)執(zhí)行上述的方法值得一提的是，題目中是要求輸出后序結(jié)果的，所以對樹和右的處理，要一些。算法分析我個人是不喜歡一邊對輸入的數(shù)據(jù)進行亂七八糟的分離，一邊再去判斷哪個字符應(yīng)該在哪個位置上，那樣對于像我這樣的菜鳥是很難的，所以

7、，我覺得還不如先把這個樹給建立起來，再慢慢的去求他的后序，那樣該多爽！基本思路與例題的一樣， 用 pre1.n和 pin1.n存放二叉樹的先序序列和中序序列，因為先序序列的第一個字符是二叉樹的根，用變量 i1 定位先序序列中的根結(jié)點，i2 定位中序序列中的的第一個字符,具體如下：（1）（2）（3）（4）（5）（6）（7） 數(shù)據(jù)結(jié)構(gòu)賦初值，i1=1,i2=1,k=length(pre);求出根結(jié)點在中序序列中的位置，m=求出 樹的串長，lenl=m-i2;求出右 的串長，lenr=k-lenl-1;(prei1,pin);遞歸建立樹，create(t.left;i1+1,i2,lenl);遞歸建

8、立右，create(t.right,i1+lenl+1,m+1,lenr);直至串長 k=0.一個用鏈表表示的二叉樹，因為用鄰接矩陣的話，在遞歸過程中，那幾乎是不可能實現(xiàn)的。程序program tree(input,output); type daype=char;treetype=node; node=recordleft:treetype; data:daype;right:treetype;end; var t:treetype;prn:string;i1,i2,j,k,l,m,n:eger; f1,f2:text;procedure create(var t:treetype;i1,i

9、2,k:eger);通過前序遍歷和中序遍歷，求它的后序遍歷var m,lenl,lenr:eger; beginif k=0 then t:=nil判斷該樹是否為空else beginnew(t);t.data:=prei1;將這個元素到樹中m:=(prei1,pin);求出根結(jié)點在中序序列中的位置lenl:=m-i2;求樹的長度lenr:=k-lenl-1;求右的長度create(t.left,i1+1,i2,lenl);建立起樹，整個程序的點睛之筆create(t.right,i1+lenl+1,m+1,lenr);遞歸建立右end;end;procedure previsit(t:tre

10、etype);后序遍歷該樹 beginif tnil thenbeginprevisit(t.left); previsit(t.right);write(f2,t.data);三條語句可以調(diào)換，分別表示左，右，中end;end; beginassign(f1,tree.in);assign(f2,tree.out); reset(f1); rewrite(f2); readln(f1,pre); readln(f1,pin); i1:=1;i2:=1;k:=length(pre);賦初值 t:=nil;初始化 create(t,i1,i2,k); previsit(t);close(f1);

11、close(f2); end.測試數(shù)據(jù)應(yīng)該不會有太太大的數(shù)據(jù)，否則的數(shù)據(jù)，有 noip2001 年的測試數(shù)據(jù)為例嘛。再說，這道題目除非有程序肯定沒問題。題三：廣義表轉(zhuǎn)換成二叉樹的二叉樹可以用廣義表表示，其廣義表的表示為：A(B(C),D(E(F,G),H(,I)為結(jié)束字符。文件中給出這樣一個廣義表表示的二叉樹，請你編一個程序，輸出該二叉樹的后序遍歷序列。輸入文件（tree.in）：A(B(C),D(E(F,G),H(,I)輸出文件(tree.out)：CBFGEIHDA問題分析這道題考查的是大家的基本功，也就是二叉樹的建立。如果說這道題目改一下，改成廣義表表示的不一定是二叉樹時，恐怕難度就提高

12、了不少。好，言歸正傳。首先，要搞清楚的廣義表（這種基礎(chǔ)概念，不必多談），十分美妙的是，廣義表也可以看成一種遞歸方式，而且和樹沒有太大的區(qū)別，所以說，程序用遞歸來做便成了首選。遇到左括號便建立一棵，遇到字母便，遇到逗號便再建立當(dāng)前所指向的結(jié)點的同一個根結(jié)點的兄弟結(jié)點（像一支繞口令似的）。算法分析我這樣的菜鳥暫時是不適合用非遞歸的方式來解決明顯要遞歸的題目的。所以說這道題目用一個遞歸的過程搞定比較好一點，讀入一個廣義表，然后用一個指針，依次指向該字符串的各個元素（當(dāng)然，邊讀入邊處理也可以，只是這個緩沖區(qū)要用上了），用一個數(shù)組分別表示每一個結(jié)點的子結(jié)點的情況，沒有的 jI0，否則等于一，以便于遇到（

13、時判斷是建立樹還是右，然后依次判斷，具體流程如下：(1.) 將指針指向下一個元素；(2.) 判斷該元素，如果它是正常的字符的話，那么 t.data 賦值為該字符；(3.) 如果該元素是左括號的話，判斷 pI是 1 還是 0，是 0 的話，則 create(t.left)，即建立樹，否則create(t.right)建立右；(4.) 如果該元素是右括號的話，那么該層遞歸結(jié)束，回到上一層中；(5.) 如果該元素是，的話則將一型變量賦值為false，然后返回上一層，接著 create(t.right)，即建立右；(6.) 如果該元素是的話，那么exit；不妨用輸入樣例來作例子：A(B(C),D(E(

14、F,G),H(,I)遇到 A，賦值給根結(jié)點，遇到左括號，jI0，則建立樹，遇到B，則再賦值給所指向節(jié)點，遇到左括號，且 jI0，則建立樹遇到 C，則給所指向節(jié)點賦值，遇到右括號，則返回上一層，遇到，則返回上一層，再建立右，遇到 D，將所指向結(jié)點賦值為D，遇到左括號，建立樹，遇到E，將所指向結(jié)點賦值為 E，遇道，則另一種思路：還可以用空間來降低程序的復(fù)雜性，就是將廣義表變成例題第二題中所提到的那種二叉樹的方法，時間關(guān)系，就不展開講了。數(shù)據(jù)結(jié)構(gòu)一個二叉鏈表，用于存放二叉樹，一個數(shù)組，用于記載某節(jié)點的字節(jié)點的狀況，若使用上文提到的另一種思路，則是使用一個數(shù)組。程序program tree(input

15、,output); type daype=char;typetree=node; node=recordleft:typetree; data:daype; right:typetree;end;flag=array 1.5000 of 0.1;記載某結(jié)點的子結(jié)點的情況 var f1,f2:text;s:string; t:typetree;i,w:eger;f:j:flag;procedure create(var t:typetree;var i,w:eger;var j:flag;var f:);beginif f then判斷剛才遇到的是不是逗號 beginf:=false;f 平常都

16、賦值為 false create(t.right,i,w,j,f);建立右end;if si thenif si not in (,), then beginnew(t);t.data:=si;將該結(jié)點賦值 inc(i);end;if si=( thenbegininc(w);表示是第幾個結(jié)點 if jw=0 then還沒有子結(jié)點begin jw:=1;inc(i); create(t.left,i,w,j,f);end;if jw=1 then有了 begininc(i);樹create(t.right,i,w,j,f); end;end; if si=, thenf:=true用于回到上一層時判斷遇到過，;end;procedure lastvisit(t:typetree);后序遍歷 beginif tnil then beginlastvisit(