【正文】 _________________的結(jié)點互稱為兄弟結(jié)點，簡稱為兄弟。 13．從根結(jié)點開始定義，根為________層，根的孩子為__________層，依次往下類推，若某結(jié)點在第k層，則其子樹的根就在______________層。 14．其雙親在同一層次上的結(jié)點互稱為___________________。 15．樹中結(jié)點的___________稱為樹的深度，又稱為樹的高度。 16．如果樹中各結(jié)點的各子樹從左至右是有序排列，不可互換的，則稱該樹為______。 17．如果樹中各結(jié)點的各子樹無排列順序，即可以互換位置，則稱為該樹為_________。 18．n(n≥0)棵互不相交的樹的集合稱為______________________。 19．二又樹（Binary Tree）是結(jié)點的有限集合，這個集合或者是空，或者是由一個根結(jié)點和__________的稱為______________和____________的二叉樹構(gòu)成。 20．二叉樹第i層上最多有____________個結(jié)點。 21．深度為k的二又樹最多有____________個結(jié)點(k≥l)。 22．在任意二叉樹中，葉子結(jié)點的數(shù)目(即度為0的結(jié)點數(shù))等于度為2的結(jié)點數(shù)____________。 23．一棵深度為k且具有2k1個結(jié)點的二叉樹稱為__________。這類二叉樹的特點是，二叉樹中每一層結(jié)點的個數(shù)都是______________的個數(shù)。 24．_________是那種在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者所缺少的結(jié)點都在右邊。 25．具有n個結(jié)點的完全二叉樹的深度是_______________。 26．對于一棵有n個結(jié)點的完全二叉樹的結(jié)點進行編號（自上而下，自左至右），則對任一結(jié)點 i（l≤i≤n），如果結(jié)點i=l，則結(jié)點i是二叉樹的____________，無雙親；如果結(jié)點il，則其雙親Parent(i)的序號是結(jié)點_______________；如果2i≤n，則結(jié)點i的左孩子Lchild(BT,，i）是_________，否則結(jié)點i無左孩子(結(jié)點i必為葉子結(jié)點)；如果2i＋l≤n，則結(jié)點i的右孩子 RChild（BT，i）的序號是____________；否則該結(jié)點無右孩子。 27．二叉樹的順序存儲結(jié)構(gòu)是用_________________存儲二叉樹的數(shù)據(jù)元素。 28．____________是指按照某條搜索路徑訪問樹中的某個結(jié)點，使得樹中每個結(jié)點均被訪問一次，而且僅被訪問一次。 29．先序遍歷二叉樹的操作定義為：若二叉樹為空，則為空操作；否則進行如下操作：訪問二叉樹____________；先序遍歷二叉樹____________；先序遍歷二叉樹_________。 30．中序遍歷二叉樹的操作定義為：若二叉樹為空，則為空操作；否則進行如下操作：中序遍歷二叉樹__________；訪問二又樹__________；中序遍歷二又樹____________。 31．后序遍歷二叉樹的操作定義為：若二叉樹為空，則為空操作；否則進行如下操作：后序遍歷二叉樹___________；后序遍歷二叉樹_________；訪問二叉樹_____________。 32．線索二叉樹（Threaded Binary Tree）是充分利用二義鏈表的 n+1個空的指針域作為線索來標志每一個結(jié)點的________和__________信息。當某個結(jié)點有左孩子的時候，使其___________指向其左孩子，無左孩子的時候，使其左指針域指向該結(jié)點的___________；當某個結(jié)點有有孩子的時候，使其右指針域指向該結(jié)點的__________，無右孩子的時候，使其有指針域指向該結(jié)點的_____________。 33．線索二叉樹的線索鏈表中，指向結(jié)點前驅(qū)和后繼的指針稱為___________；加上線索的二叉樹稱為_____________；對二叉樹以某種次序進行遍歷使其成為線索二叉樹的過程稱為_______________________。 34．樹的存儲結(jié)構(gòu)常見的有____________、____________和________________。 35．樹的先序遍歷過程如下：若樹為空，則進行空操作；若樹非空，則：訪問樹的__________；依次先序遍歷樹的__________。 36．樹的后序遍歷過程為：若樹為空，則進行空操作；若樹非空，則：依次后序遍歷__________；訪問_________________。 37．森林的先序遍歷過程為：若森林非空，則： （1）訪問森林中第一棵樹的___________。 （2）先序遍歷第一棵樹中_____________。 （3）先序遍歷_______________________。 38．森林的后序遍歷過程為：若森林非空，則： （l）后序遍歷森林中第一棵樹的_______________。 （2）訪問第一棵樹的_________________________。 （3）后序遍歷_______________________________。 39．從樹中一個結(jié)點到另一個結(jié)點之間的_________稱為這兩個結(jié)點的路徑。 40．路徑上的分支數(shù)目稱為______________。 41．樹的路徑長度是指從樹根到每一結(jié)點的__________________。 42．將樹中的結(jié)點賦上一個有著某種意義的實數(shù)，稱此實數(shù)為該結(jié)點的____________。 43．樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的____________。 44．哈夫曼樹（Huffman Tree）又稱___________。它是n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑長度WPL__________________。 45，所謂前綴編碼是指在所有對字符的編碼中，任何一個字符都不是____________。46．已知完全二叉樹的第八層有8個結(jié)點，則其葉子結(jié)點數(shù)是__________________。47．在有n個葉子結(jié)點的哈夫曼樹中，總結(jié)點數(shù)是___________。48．已知完全二又樹的第7層有10個葉子結(jié)點，則整個二又樹的結(jié)點數(shù)最多是__________。49．已知二叉樹中葉子數(shù)為50，僅有一個孩子的結(jié)點數(shù)為30，則總結(jié)點數(shù)為__________。50．一棵樹T采用二叉鏈表BT存儲，如果樹T中某結(jié)點為葉子結(jié)點，則在二叉鏈表BT中所對應的結(jié)點一定滿足___________________。51．在二叉鏈表中，判斷某指針P所指結(jié)點為葉子結(jié)點的條件是__________。52．若以{4，5，6，7，8}作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是___________。53．已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是______________。54．3個結(jié)點可構(gòu)成___________________棵不同形態(tài)的樹。55．已知完全二叉樹的第七層有8個結(jié)點，則其葉子結(jié)點數(shù)是______________.56．將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié) 點進行編號，根結(jié)點的編號為1，則編號為49的結(jié)點的左孩子編號為____________。57．若要對某二叉排序樹進行遍歷，保證輸出的所有結(jié)點序列按鍵值遞增次序排列， 應對該二叉樹采用_______________遍歷法。1. 有限2. 根、根、根、子樹3. 結(jié)點、記錄4. 子樹數(shù)目5. 最大值6. 分支結(jié)點、非終端結(jié)點7. 度為零的結(jié)點8. 后繼結(jié)點、子樹的根9. 雙親結(jié)點10. 子孫結(jié)點11. 祖先結(jié)點12. 同一雙親13. 第一、第二、第k+114. 堂兄弟15. 最大層次16. 有序樹17. 無序樹18. 森林19. 兩棵互不相交、左子樹、右子樹20. 2i121. 2k122. 加123. 滿二叉樹、最大結(jié)點24. 完全二叉樹25. 26. 根、2i、2i+127. 一組連續(xù)的存儲單元28. 遍歷二叉樹29. 根結(jié)點、左子樹、右子樹30. 左子樹、根結(jié)點、右子樹31. 左子樹、右子樹、根結(jié)點32. 前驅(qū)、后繼、左指針域、直接前驅(qū)結(jié)點、右孩子、直接后繼結(jié)點33. 線索、線索二叉樹、線索化34. 雙親表示法、孩子表示法、孩子兄弟表示法35. 根結(jié)點、各子樹36. 根的各子樹、根結(jié)點37. 根結(jié)點、根結(jié)點的子樹、除第一棵樹之外剩余的樹構(gòu)成的森林38. 根結(jié)點的子樹、根結(jié)點、除第一棵樹之外剩余的樹構(gòu)成的森林39. 分支40. 路徑長度41. 路徑長度之和42. 權(quán)43. 帶權(quán)路徑長度之和44. 最優(yōu)二叉樹、最小的二叉樹45. 另一個字符的前綴46. 6847. 2n148. 7449. 12950. 左子樹為空51. (plchild==nil)amp。amp。(prchild==nil)52. 6953. 9954. 255. 3656. 9857. 中序三、判斷題1．完全二叉樹的某個結(jié)點若無左孩子，則它必然是葉結(jié)點。（ ）2．存在這樣一種二叉樹，對它采用任何次序的遍歷結(jié)果相同。（ ）3．度為二的樹稱為二叉樹。（ ）4．二叉樹中不存在度大于2的結(jié)點。（ ）5．當二叉樹中某個結(jié)點只有一棵子樹的時候，無左右子樹之分。（ ）6．任何一棵二叉樹都可以不用棧實現(xiàn)前序線索樹的前序遍歷。（ ）7．哈夫曼編碼是一種前綴編碼，不允許出現(xiàn)兩個字符編碼相同的情況。（ ）8．完全二叉樹某結(jié)點有右子樹，則必然有左子樹。（ ）9．前序遍歷一棵二叉樹的結(jié)點就可以得到排好序的結(jié)點序列。（ ）10．將一棵擁有子樹的樹轉(zhuǎn)換為二叉樹后，根結(jié)點可能沒有左子樹。（ ）11．根據(jù)二叉樹的前序遍歷和中序遍歷可以得到二又樹的后序遍歷。（ ）12．哈夫曼樹是帶權(quán)路徑長度最短的二叉樹。（ ）13．哈夫曼樹上權(quán)值較大的結(jié)點離根較遠。（ ）14．中序遍歷森林與后序遍歷與森林相對應的二叉樹結(jié)果相同。（ ）15．在二叉樹中，具有一個孩子的結(jié)點，在中序遍歷序列中，沒有后繼子女結(jié)點。 （ ）16．先序遍歷森林與先序遍歷相對應的二叉樹結(jié)果不同。（ ）17．若一棵二叉樹的任一非葉子結(jié)點的度為2，則該二叉樹為滿二叉樹。（ ）18．二叉樹只能采用二叉鏈表來存儲。（ ）19．給定結(jié)點數(shù)的平衡二叉樹的高度是惟一的。（ ）1. 正確：根據(jù)完全二叉樹定義可以知道，若完全二叉樹無左孩子，則它必然無右孩子。2. 正確：二叉樹只有一個結(jié)點的時候。3. 錯誤：二叉樹子樹還有左右次序之分。4. 正確。5. 錯誤。6. 正確。7. 正確。8. 正確：根據(jù)完全二叉樹定義可以知道，9. 錯誤：中序遍歷一棵二叉樹的結(jié)點就可以得到排好序的結(jié)點序列。10. 錯誤：將一棵擁有子樹的樹轉(zhuǎn)換為二叉樹后，根結(jié)點必然有左子樹。11. 正確。12. 正確。13. 錯誤：哈夫曼樹的路徑上權(quán)值較大的結(jié)點離根較近。14. 錯誤：后序遍歷森林與中序遍歷與森林相對應的二叉樹結(jié)果相同。15. 錯誤：在二叉樹中，具有一個左孩子的結(jié)點，在中序遍歷序列中，沒有后繼子女結(jié)點。16. 錯誤：前序遍歷森林與前序遍歷與森林相對應的二叉樹結(jié)果相同。17. 錯誤：任一非葉子結(jié)點的度為2也不能保證滿足滿足滿二叉樹的定義。18. 錯誤：也可以采用順序存儲和三叉鏈表等形式進行表示。19. 錯誤：給定結(jié)點數(shù)的平衡二叉樹的高度不一定是惟一的。四、綜合題1．一棵樹表達成如下形式：D＝{A，B，C，D，E，F(xiàn)，G， H，I，J，K，L，M，N，O}R=＜A，B＞，＜A，C＞，＜A，D＞，＜B，E＞，＜B，F(xiàn)＞，＜C，G＞，＜D，H＞，＜D，I＞，＜D，J＞，＜K，F(xiàn)＞，＜K，L＞，＜F，M＞，＜I，N＞，＜I，O＞｝其中D為結(jié)點集合，R為邊的集合。請根據(jù)以上內(nèi)容回答以下問題：(1) 畫出這棵樹。(2) 該樹的根結(jié)點是哪一個？(3) 哪些是葉子結(jié)點？(4) F結(jié)點的雙親是誰？(5) F結(jié)點的祖先是哪些？(6) F結(jié)點的孩子是哪些？(7) F結(jié)點的兄弟是哪些？(8) F結(jié)點的堂兄弟是哪些？(9) F結(jié)點的度是多少？(10)F結(jié)點的層次是多少？(11)D結(jié)點的子孫有哪些？(12) 以結(jié)點D為根的子樹度是多少？(13) 以結(jié)點D為根的子樹層是多少？(14) 該樹的層是多少？(15) 該樹的度是多少？2．畫出圖61中樹的二叉樹表示形式。 （a） （b） （c） 圖6l3．已知某二叉樹的先序遍歷的結(jié)果是：A，B，D，QC，E，H，L，I，K，M，F(xiàn)和J，它的中序遍歷的結(jié)果是：QD，B，A，L，H，E，K，LM，C，F(xiàn)和J，請畫出這棵二叉樹，并且寫出該二叉樹后序通歷的結(jié)果。4．寫一個將一棵二叉樹復制給另一棵二又樹的算法