計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)（樹和二叉樹）歷年真題試卷匯編4（總分：74.00，做題時(shí)間：90分鐘）一、綜合題（總題數(shù)：35,分?jǐn)?shù)：74.00）.（1）試找出滿足下列條件的二叉樹：1）先序序列與后序序列相同2）中序序列與后序序列相同3）先序序列與中序序列相同4）中序序列與層次遍歷序列相同⑵已知一棵二叉樹的中序序列和后序序列分別為DBEAFIHCG和DEBHIFGCA，畫出這棵二叉樹?！緰|北大學(xué)1999六（4分）】【東南大學(xué)2000一、4（6分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：（1）先序遍歷二叉樹的順序是“根一左子樹一右子樹”，中序遍歷“左子樹一根一右子樹”，后序遍歷順序是“左子樹一右子樹一根”，根據(jù)以上原則，本題解答如下：1）若先序序列與后序序列相同，則或?yàn)榭諛?，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹。2）若中序序列與后序序列相同，則或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹的二叉樹。3）若先序序列與中序序列相同，則或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹。4）若中序序列與層次遍歷序列相同，則螞為空樹，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹。（2）由中序序列DBEAFIHCG和后序序列DEBHIFGCA。I ）解析：.分別給出滿足下列條件的二叉樹。（1）前序和中序遍歷結(jié)果相同；（2）前序和中序遍歷結(jié)果不相同而是相反；（3）中序和后序遍歷結(jié)果相同；（4）前序和后序遍歷結(jié)果相同?！舅拇ù髮W(xué)2004】【煙臺(tái)大學(xué)2007四、2（8分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：空二叉樹滿足題目要求，若二叉樹非空，則（1）前序和中序遍歷結(jié)果相同的二叉樹是任一結(jié)點(diǎn)無左子女；（2）前序和中序遍歷結(jié)果不相同而是相反的二叉樹是任一結(jié)點(diǎn)無右子女；（3）中序和后序遍歷結(jié)果相同的二叉樹是任一結(jié)點(diǎn)無右子女；（4）前序和后序遍歷結(jié)果相同的二叉樹是只有根結(jié)點(diǎn)。）（分?jǐn)?shù)：2.00）正確答案：（正確答案：森林轉(zhuǎn)為二叉樹的三步：（1）連線（將兄弟結(jié)點(diǎn)相連，各樹的根看作兄弟）；（2）切線（保留最左邊子女為獨(dú)生子女，將其他子女分支切掉）；（3）旋轉(zhuǎn)（以最左邊樹的根為軸，順時(shí)針向下旋轉(zhuǎn)45度）。其實(shí)經(jīng)過（1）和（2），已轉(zhuǎn)為二又樹，執(zhí)行⑶只是為了與平時(shí)的二又樹的畫法一致。）解析：.設(shè)一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列：ABD，CEGH中序遍歷序列：BFDAGEHC（1）畫出這棵二叉樹。（2）畫出這棵二叉樹的后序線索樹。（3）將這棵二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹（或森林）?！灸暇┖娇蘸教齑髮W(xué)1997二（10分）】（分?jǐn)?shù)：2.00）

(4)(4.已知一棵二叉樹的對(duì)稱序和后序序列如下：對(duì)稱序：GLDHBEIACJFK后序：LGHDIEBJKFCA（1）（2分）給出這棵二叉樹；（2）（2分）轉(zhuǎn)換為對(duì)應(yīng)的森林；（3）（4分）畫出該森林的帶右鏈的先根次序表示法;(4)(4分）畫出該森林帶度數(shù)的后根次序表示法；（5）（4分）在帶度數(shù)的后根次序表示法中，不包含指針，但仍能完全反映樹的結(jié)構(gòu)。寫出以結(jié)點(diǎn)x為根的子樹在后根次序序列中的前驅(qū)的求法。（用語言敘述，不用寫算法。）【山東大學(xué)1998八（16分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：（1）1——1（2）1——?⑶森林的帶右鏈的前序表示法。在前序序列中，任何結(jié)點(diǎn)的子樹的所有結(jié)點(diǎn)都直接跟在該結(jié)點(diǎn)之后；每棵子樹的所有結(jié)點(diǎn)都聚集在一起，中間不會(huì)插入其他結(jié)點(diǎn)；任何分支結(jié)點(diǎn)后面跟的是它的第一個(gè)子女。故結(jié)點(diǎn)可采用如下結(jié)構(gòu)（1tag，data，rlink）。其中，ltag為左標(biāo)記，ltag=1表示該結(jié)點(diǎn)無子女或二叉樹無左子女，Itag=0表示其后存儲(chǔ)其第一子女或二叉樹的左子女；data是結(jié)點(diǎn)的數(shù)據(jù)；rlink指向下一兄弟或二叉樹的右子女。用左標(biāo)記代替左指針』用存儲(chǔ)單元少，不會(huì)丟失信息。本題森林的帶右鏈的前序表示法為（注：“下標(biāo)”行不是結(jié)點(diǎn)成分）：?——L）帶度數(shù)的后根次序表示法。在后序序列中，任何一棵子樹的結(jié)點(diǎn)聚在一起，根結(jié)點(diǎn)在最后。結(jié)點(diǎn)按后根次序順序存儲(chǔ)在一片連續(xù)的存儲(chǔ)單元中，結(jié)點(diǎn)結(jié)構(gòu)可描述為：（data，degree）o（5）該森林帶度數(shù)的后根次序表示法如下：后根次序序列中任何一棵子樹的結(jié)點(diǎn)個(gè)數(shù)減邊數(shù)為1。設(shè)某結(jié)點(diǎn)的度degree=m，即該結(jié)點(diǎn)有m個(gè)子女，最右邊的子女就是該結(jié)點(diǎn)的前驅(qū)。在后根次序表示法中最后的第2個(gè)子女是最右子女為根的子樹的前驅(qū)，以結(jié)點(diǎn)x為根的子樹的前驅(qū)求法如下:令q=0，從x開始從后往前走，每經(jīng)過一個(gè)結(jié)點(diǎn)z，作q=q++-degree（z）；到q=1時(shí)，再往前走一個(gè)結(jié)點(diǎn)就是以結(jié)點(diǎn)x為根的子樹在后根序列中的前驅(qū)。?——）解析：.設(shè)某二叉樹的前序遍歷序列為：ABCDEFGHI，中序遍歷序列為：BCAEDGHFI。（1）試畫出該二叉樹。（2）寫出由給定的二叉樹的前序遍歷序列和中序遍歷序列構(gòu)造出該二叉樹的算法。（3）設(shè)具有4個(gè)結(jié)點(diǎn)的二叉樹的前序遍歷序列為abcd；S為長度等于4的由a，b，c，d排列構(gòu)成的字符序列，若任取S作為上述算法的中序遍歷序列，試問是否一定能構(gòu)造出相應(yīng)的二叉樹，為什么？試列出具有4個(gè)結(jié)點(diǎn)二叉樹的全部形態(tài)及相應(yīng)的中序遍歷序列?！菊憬髮W(xué)1997六（15分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案:⑵設(shè)二叉樹的前序遍歷序列為P1正確答案：（正確答案:⑵設(shè)二叉樹的前序遍歷序列為P1，P2,…，Pm，中序遍歷序列為S1，S2,…，Sm。因?yàn)榍靶虮闅v是“根一左一右”，中序遍歷是“左一根一右”，則前序遍歷序列中第一個(gè)結(jié)點(diǎn)P1是根結(jié)點(diǎn)。到中序序列中查詢到Si=P1，根據(jù)中序遍歷時(shí)根結(jié)點(diǎn)將中序序列分成左右兩部分的原則，有：若i=1，即S1=P1，則這時(shí)的二叉樹沒有左子樹；否則，S1，S2,…，Si一1是左子樹的中序遍歷序列，用該序列和前序序列p2,P3,…，Pi去構(gòu)造該二叉樹的左子樹。若i=m，即Sm=P1，則這時(shí)的二叉樹沒有右子樹；否則，Si+1，Si+2,…，Sm是右子樹的中序遍歷序列，用該序列和前序序列中Pi+1，Pi+2,…，Pm，、去構(gòu)造該二叉樹的右子樹。算法描述請(qǐng)參見下面算法設(shè)計(jì)題第49題。（3）若前序序列是abed，并非由這四個(gè)字母的任意組合（41=24）都能構(gòu)造出二叉樹、因?yàn)橐詀bed為輸入序列，通過棧只能得到1/n+1）*2n!/（n!*n!）=14種，即以abcd為前序序列的二叉樹的數(shù)目是14。任取以abed作為中序遍歷序列，并不全能與前序的abed序列構(gòu)成二叉樹。例如：若取中序序列dcab就不能。該14棵二叉樹的形態(tài)及中序序列略。）解析：.假設(shè)一棵二叉樹的前序序列為ABCD，它的中序序列可能是DABC嗎？【石油大學(xué)1998一、1（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：不能。因DABC并不是ABCD的合法出棧序列）解析：.已知一棵二叉樹的后序遍歷序列為EICBGAHDF,同時(shí)知道該二叉樹的中序遍歷序列為CEIFGBADH,試畫出該二叉樹?！局貞c大學(xué)2000二、2】（分?jǐn)?shù)：2.00）正確答案：（正確答案：? ）解析：.已知一棵二叉樹T的諸結(jié)點(diǎn)在先根次序下的排列為:ABCEDFGHI，在中根次序下的排列為：ECBDFAHIG，畫出此樹形狀并給出其后根序列。【吉林大學(xué)2007二、3（3分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：二叉樹略，其后根序列為：ECFDBIHGAo）解析：.在某二叉樹上進(jìn)行前序、中序遍歷后發(fā)現(xiàn)該二叉樹的前序序列的最后一個(gè)結(jié)點(diǎn)和中序序列的最后一個(gè)結(jié)點(diǎn)是同一個(gè)結(jié)點(diǎn)。請(qǐng)問該結(jié)點(diǎn)具有何種性質(zhì)？為什么？【上海交通大學(xué)2003五（10分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：該結(jié)點(diǎn)應(yīng)是二叉樹最右邊的葉子結(jié)點(diǎn)。因?yàn)榍靶虮闅v是“根一左一右”，中序遍歷是“左一根一右”，只有在最右邊的葉子處，前序和中序遍歷才能是同一個(gè)結(jié)點(diǎn)。）解析：.在二叉樹上進(jìn)行前序遍歷時(shí)，結(jié)點(diǎn)A在結(jié)點(diǎn)B之前，而在進(jìn)行后序遍歷時(shí)，結(jié)點(diǎn)A在結(jié)點(diǎn)B之后，那么結(jié)點(diǎn)A是結(jié)點(diǎn)B的祖先，對(duì)嗎?為什么？【上海交通大學(xué)2003六（10分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：正確。前序遍歷是“根一左一右”，后序遍歷是“左一右一根”。前序遍歷結(jié)點(diǎn)A在結(jié)點(diǎn)B之前，說明結(jié)點(diǎn)A到B有路徑，或A在B的左面。后序遍歷結(jié)點(diǎn)A在結(jié)點(diǎn)B之后，說明結(jié)點(diǎn)A到B有路徑，或A在右面，B在左面。綜合以上情況，說明結(jié)點(diǎn)A是B的祖先。）解析：.某二叉樹的后序遍歷序列為：，①，①，A，①，①，E，①，①，CD，B，其中①表示空格符，代表空二叉樹。能否以此序列作為輸入創(chuàng)建二叉樹?如不能，請(qǐng)說明理由；如能夠，試畫出對(duì)應(yīng)二叉樹。【華中科技大學(xué)2007三、23（8分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：二叉樹后序遍歷序列是“左一右一根”，序列的最后一個(gè)結(jié)點(diǎn)是根，根結(jié)點(diǎn)的左面是右子樹的根，若無右子樹，則該位置應(yīng)為T，9的左面應(yīng)是左子樹的根結(jié)點(diǎn)，若無左子女，則該位置也為①。照此規(guī)則，就能建立二叉樹。I ）解析：.輸入帶空二叉樹信息（O）的前序遍歷序列：A，G，①，①，B，①，C，D，E，①，E①，①，①，E①，中建立一棵二又樹，其中①表示空格符，代表空二叉樹，試畫出該二叉樹?！救A中科技大學(xué)2006三、1（6分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：二叉樹前序遍歷序列的第一個(gè)結(jié)點(diǎn)是根（如是空樹，則用中表示），接著應(yīng)是左子樹的根，如無左子樹■，則用①表示，9的后邊是右子樹的根，如無右子樹，則用中表示。如此分析，得二叉樹如下。? ）解析：

.已知某二叉樹的每個(gè)結(jié)點(diǎn)，要么其左、右子樹皆為空，要么其左、右子樹皆不空。又知該二叉樹的前序序列為（即先根次序）：J、F、D、B、A、C、E、H、X、I、K；后序序列為（即后根次序）：A、C、B、E、D、X、，、H、F、K、，。請(qǐng)給出該二叉樹的中序序列（即中根次序）。【上海交通大學(xué)2001二（8分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：二叉樹中序序列ABCDEFXHIJK。）解析：.假設(shè)一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列DBGEHJACIF。請(qǐng)畫出這棵二叉樹?！疚錆h大學(xué)2000三、1】【東南大學(xué)2000一、1（6分）】【大連理工大學(xué)2005二、3（20/4分）】【中國海洋大學(xué)2007一、5（8分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：按層次遍歷，第一個(gè)結(jié)點(diǎn)（若樹不空）為根，該結(jié)點(diǎn)在中序序列中把序列分成左右兩部分一一左子樹和右子樹。若左子樹不空，層次序列中第二個(gè)結(jié)點(diǎn)是左子樹的根；若左子樹為空，則層次序列中第二個(gè)結(jié)點(diǎn)是右子樹的根。對(duì)左、右子樹也作類似的分析。層次序列的特點(diǎn)是：從左到右每個(gè)結(jié)點(diǎn)或是當(dāng)前情況下子樹的根或是葉子。該題型的算法參見下面算法設(shè)計(jì)題第52題。解析：.已知一個(gè)森林的先序序列和后序序列如下，請(qǐng)構(gòu)造出該森林。先序序列：ABCDEFGHIJKLMNO后序序列:CDEBFHIJGAMLONK【合肥工業(yè)大學(xué)2000四、1（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：森林的先序序列和后序序列對(duì)應(yīng)其轉(zhuǎn)換的二叉樹的先序序列和中序序列，應(yīng)先據(jù)此構(gòu)造二叉樹，再構(gòu)造出森林。解析：構(gòu)造二叉樹，再構(gòu)造出森林。解析：.畫出同時(shí)滿足下列兩條件的兩棵不同的二叉樹。（1）按先根序遍歷二叉樹順序?yàn)锳BCDE。（2）高度為5其對(duì)應(yīng)的樹（森林）的高度最大為4?！緰|北大學(xué)1997一、3（5分）】.用一維數(shù)組存放的一棵完全二叉樹；ABCDEFGHIJKL。請(qǐng)寫出后序遍歷該二叉樹的訪問結(jié)點(diǎn)序列?！疚靼搽娮涌萍即髮W(xué)1999計(jì)算機(jī)應(yīng)用一、6（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：HIDJKEBLFGCA。完全二叉樹的結(jié)點(diǎn)按從上到下、從左到右的順序，在數(shù)組中存儲(chǔ)。結(jié)點(diǎn)t和其雙親、子女的編號(hào)間有確定的關(guān)系。）解析：.一棵二叉樹的先序、中序和后序序列如下，其中有部分未標(biāo)出，試構(gòu)造出該二叉樹。先序序列為：-一CDE—GHI-K中序序列為：CB——FA—JKIG后序序列為：-EFDB—JIH—A【電子科技大學(xué)2001三、1（5分）】【廈門大學(xué)2002七、l（6分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：本題解答原理及方法如下：首先掌握先序遍歷是“根一左一右”中序遍歷是“左一根一右”，后序遍歷是“左一右一根"。從給定條件的后序序列中，最后元素A是根。到中序序列中找到A,A將序列分成左右兩部分：左邊5個(gè)元素形成二叉樹的左子樹，右邊5個(gè)元素形成二叉樹的右子樹。這樣，先序序列從第2個(gè)元素開始的5個(gè)元素是二叉樹左子樹的先序序列，后面的5個(gè)元素形成二叉樹右子樹的先序序列。同理，后序序列也可以確定左右子樹各有5個(gè)元素。先畫左子樹還是右子樹都一樣，按習(xí)慣，我們先畫出左子樹。從后序序列知，B是左子樹的根，到左子樹的中序序列中找到B，B的左面有一個(gè)元素C，這是B的左子女。B的右面有3個(gè)元素，即B的右子樹有3個(gè)結(jié)點(diǎn)。從左子樹的先序（或后序）序列中都能發(fā)現(xiàn)D是B的右子樹的根。但是這時(shí)中序序列并未給出D，而是空格。這時(shí)B的右子樹先序序列是“DE___"，中序序列是"___F”，后序序列是“EFD”，可以判定E是D的左子女，F(xiàn)是D的右子女。至此，整棵二叉樹的左子樹分析完畢。同樣，也可以畫出右子樹。）解析：.M叉樹的前序和后序遍歷分別與由它轉(zhuǎn)換成的二叉樹的哪種遍歷相對(duì)應(yīng)？【中國人民大學(xué)2000一、2（4分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：M叉樹的前序和后序遍歷分別與它轉(zhuǎn)換成的二叉樹的先序和中序遍歷對(duì)應(yīng)。）解析：.設(shè)樹形T在后根次序下的結(jié)點(diǎn)排列和各結(jié)點(diǎn)相應(yīng)的次數(shù)如下：后根次序：BDEFCGJKILHA次數(shù)：000030002024請(qǐng)畫出T的樹形結(jié)構(gòu)圖。【吉林大學(xué)2001一、2（4分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：樹的遍歷序列中，各子樹的結(jié)點(diǎn)在一起，不會(huì)漏掉一個(gè)結(jié)點(diǎn)，也不會(huì)有其他子樹的結(jié)點(diǎn)插到里面。后根遍歷序列中最后一個(gè)是根結(jié)點(diǎn)，根結(jié)點(diǎn)的左邊是其最右子樹的根，該子樹的結(jié)點(diǎn)連在一起。據(jù)此分析本題。A是根結(jié)點(diǎn)，其次數(shù)是4,即有4棵子樹。H在A的左邊，是A的最右子樹的根，它有兩棵子樹，L是右子樹的根，它次數(shù)是O,說明L是葉子。I是H的左子樹的根，它有兩棵子樹，K是它右子樹的根，次數(shù)0說明它是葉子，J是I的左子樹的根，它也是葉子。這就完成了對(duì)根A的最右子樹的分析。同樣也可以從右到左地分析根A的其他3棵子樹。最后得到結(jié)果樹如下。?——）解析：.已知二叉樹采用二叉鏈表方式存放，要求返回二叉樹T的后序序列中的第一個(gè)結(jié)點(diǎn)的指針，是否可不用遞歸且不用棧來完成?請(qǐng)簡(jiǎn)述原因?！疚鞅贝髮W(xué)2001三、6】（分?jǐn)?shù)：2.00）正確答案：（正確答案：后序遍歷的順序是“左一右一根”。因此，二叉樹最左（或右）下的葉子結(jié)點(diǎn)是后序遍歷的第一個(gè)結(jié)點(diǎn)。下面的語句段說明了這一過程（設(shè)p是二叉樹根結(jié)點(diǎn)的指針）。if（p!=null）{while（p一>lchild!=nullI}p一〉rchild!=null）//只要不是葉子（while（p->lchild!=null）p=p—>1child；//首先沿左子樹向下if（p一>rchildl=null）p=p—>rchild； //無左子樹而有右子樹時(shí)沿右子樹向下}}ret一urn（p）； //返回后序序列第一個(gè)結(jié)點(diǎn)的指針）解析：.對(duì)于二叉樹T的兩個(gè)結(jié)點(diǎn)N1和N2,我們應(yīng)該選擇樹T結(jié)點(diǎn)的前序、中序和后序中哪兩個(gè)序列來判斷結(jié)點(diǎn)n1必定是結(jié)點(diǎn)n2的祖先，并給出判斷的方法。不需證明判斷方法的正確性。【復(fù)旦大學(xué)1999五（10分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：采用前序和后序兩個(gè)序列來判斷二叉樹上結(jié)點(diǎn)n1必定是結(jié)點(diǎn)n2的祖先。在前序序列中某結(jié)點(diǎn)的祖先都排在其前。若結(jié)點(diǎn)n1是n2的祖先，則n1必在n2之前。而在后序序列中，某結(jié)點(diǎn)的祖先排在其后，即若結(jié)點(diǎn)n1是n2的祖先，則n1必在n2之后。根據(jù)這條規(guī)則來判斷若結(jié)點(diǎn)n1在前序序列中在n2之前，在后序序列中又在n2之后，則它必是結(jié)點(diǎn)n2的祖先。對(duì)本題的解答還可以參見上面第59題。）解析：.在二又樹的前序遍歷和中序遍歷的遞歸算法中，最后一個(gè)遞歸調(diào)用語句在調(diào)用時(shí)所保留的參數(shù)有什么作用？如何清除最后這個(gè)遞歸語句？【北京郵電大學(xué)1994三（8分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：最后一個(gè)遞歸調(diào)用語句所保留的參數(shù)沒有意義。這類遞歸因其在算法最后，通常被稱為“尾遞歸”，可不用棧且將其（遞歸）消除。如中序遍歷遞歸算法中，最后的遞歸語句inorder（bt一〉rchild）可改為下列語句段：bt=bt一〉rchild；while（bt一〉rchild!=null）（inorder（bt—>1child）；conlt<data<rchild；｝）解析：.在二叉樹的Llink-一Rlink存儲(chǔ)表示中，引入“線索”的好處是什么？【山東大學(xué)1999六、1（2分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：在二叉鏈表表示的二叉樹中，查找結(jié)點(diǎn)的左右子女非常方便，但查找后繼就不太方便。引入線索的目的主要是便于查找結(jié)點(diǎn)的前驅(qū)和后繼。因?yàn)槿糁栏鹘Y(jié)點(diǎn)的后繼，二叉樹的遍歷就變得非常簡(jiǎn)單。為此將二叉樹加上線索。利用結(jié)點(diǎn)的空鏈域，左鏈為空時(shí)用作前驅(qū)指針，右鏈為空時(shí)作為后繼指針。再引入左右標(biāo)記ltag和rtag，約定ltag=0時(shí)，lchild指向左子女，ltag=1時(shí)，lchild指向前驅(qū)；rtag=0時(shí)，rchild指向右子女，rtag=1時(shí)，rchild指向后繼。這樣，在線索二叉樹（特別是中序線索二叉樹）上遍歷就消除了遞歸，也不使用棧（后序線索二叉樹查后繼仍需要棧。））解析：.按下面要求解下圖中二叉樹的有關(guān)問題：（1）對(duì)此二叉樹進(jìn)行后序后繼線索化;（2）將此二叉樹變換為森林；（3）用后根序遍歷該森林，寫出遍歷后的結(jié)點(diǎn)序列。I 【北京郵電大學(xué)1996五（10分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：給二叉樹加上線索有如下要點(diǎn)：首先要明確是什么序的線索化，即前序、中序還是后序線索化；二是前驅(qū)、后繼還是全線索化；三是只有空指針處才能加線索。本題是后序后繼線索畫，畫上前驅(qū)線索或在非空處加線索就是畫蛇添足，說明概念不明確。（1）? 1（2）? ⑶后根遍歷森林，結(jié)點(diǎn)序列為：BDCAIFJGHELOPMNK）解析：.一棵h層、度為k（k〉1）的樹，最多有多少個(gè)結(jié)點(diǎn)？【北京科技大學(xué)2006】（分?jǐn)?shù)：2.00）正確答案：（正確答案：1+k1+k2+k3+…+kh-1=（kh-1）/（k-1））解析：設(shè)二叉樹BT的存儲(chǔ)結(jié)構(gòu)如下：?——其中BT為樹根結(jié)點(diǎn)的指針，其值為6,Lchild,Rchild分別為結(jié)點(diǎn)的左、右孩子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域。試完成下列各題：（分?jǐn)?shù)：6.00）（1）.畫出二叉樹BT的邏輯結(jié)構(gòu)；（分?jǐn)?shù)：2.00）（2）.寫出按前序、中序、后序遍歷該二叉樹所得到的結(jié)點(diǎn)序列；（分?jǐn)?shù)：2.00）正確答案：（正確答案：前序序列：ABCEDFHGIJ中序序列：ECBHFDJIGA后序序列：ECHFJIGDBA）解析：解析：.請(qǐng)說明是否存在這樣的二叉樹，即它可以實(shí)現(xiàn)后序線索樹進(jìn)行后序遍歷時(shí)不使用棧；而對(duì)前序線索樹進(jìn)行前序遍歷時(shí)，又有什么樣的二叉樹可不使用棧。【西安電子科技大學(xué)1996二、1（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：后序線索樹中結(jié)點(diǎn)的后繼，要么是其右線索（當(dāng)結(jié)點(diǎn)的rtag=1時(shí)），要么是其雙親結(jié)點(diǎn)右子樹中最左下的葉子結(jié)點(diǎn)。所以，只有當(dāng)二叉樹只有根或樹中任一結(jié)點(diǎn)均無右子樹時(shí)，進(jìn)行遍歷才不用棧，其遍歷程序段如下：whi1e（p—>1tag==0）p：=p->1chi1d； //找最左下葉子結(jié)點(diǎn)whi1e（p一〉rchi1d!=nu11）{visit（p一〉data）； //訪問結(jié)點(diǎn)p=p一>rchild； //沿線索向上}對(duì)前序線索二叉樹，當(dāng)二叉樹非空時(shí)，若其結(jié)點(diǎn)有左子女（1tag=0）,左子女是后繼；否則，若結(jié)點(diǎn)有右子女（rtag=0）,則右子女是后繼；若無右子女（rmg=1）,右鏈?zhǔn)蔷€索，也指向后繼。所以，對(duì)任何前序線索二叉樹進(jìn)行前序遍歷均不需使用棧。）解析：.一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數(shù)為多少？【西安電子科技大學(xué)2000計(jì)算機(jī)應(yīng)用一、2（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：左右子樹均不空的二叉樹先序線索化后，空指針域?yàn)?個(gè)（最后訪問結(jié)點(diǎn)的右鏈為空）。）解析：.在前序線索樹上，要找出結(jié)點(diǎn)p的直接后繼結(jié)點(diǎn)，請(qǐng)寫出相關(guān)語句。結(jié)點(diǎn)結(jié)構(gòu)為（1tag,lc,data,nag,rc）?！疚鞅贝髮W(xué)2000二、6（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：if（p一>1tag==0）return（p—>1chi1d）； //左子女不空，左子女為直接后繼結(jié)點(diǎn)elsereturn（p一〉rchild）；//