數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案第六章-文庫吧資料
2025-06-28 21:25本頁面
【正文】 ile (pamp。 p=T。 { InitStack (S)。 【解答】中序遍歷的非遞歸算法如下：1．編寫對(duì)二叉樹進(jìn)行中序遍歷的非遞歸算法，并對(duì)算法執(zhí)行原教材題圖66所示的二叉樹的情況進(jìn)行跟蹤（即給出各階段棧的變化及輸出的結(jié)點(diǎn)序列）。 }return S。 s=slchild。 （sltag） if(srtag) S=Xrchild。 x) BiTree 。 100 A110 BO C10 DII1 非空樹如下： 7．將原教材題圖65轉(zhuǎn)換為孩子兄弟所表示的二叉樹及該二叉樹的后序線索二叉樹如下：^ 6．若前序遍歷某樹的結(jié)點(diǎn)次序：SACEFBDGHIJK。若該結(jié)點(diǎn)不存在，則取0值。畫出該二叉樹的鏈接表示形式。 【解答】轉(zhuǎn)化成如下二叉樹： 4．將算術(shù)表達(dá)式((a+b)+c*(d+e)+f*(g+h)轉(zhuǎn)化為二叉樹。 (10)以結(jié)點(diǎn)C為根的子樹的深度是：3。 (9)樹的深度是：5。 (8)結(jié)點(diǎn)B和N的層次號(hào)分別是：2，5。結(jié)點(diǎn)F的兄弟是：G，H?！窘獯稹扛鶕?jù)邊集畫出的樹如下所示： 單分支：3 高度：5最后得到由中序和后序序列決定的二叉樹為：再由后序遍歷序列可知右子樹{d，e}的根結(jié)點(diǎn)為d，再由中序遍歷序列可知d的左子樹為空，右子樹為{e}。由后序序列可知該樹的根結(jié)點(diǎn)為a，由中序遍歷序列可知該樹的左子樹為{c，b，d，e}，右子樹為{g，i，h，j，f）。 后序序列：c，e，d，b，i，j，h，g，f，a 后序：c，b，e，D，d，a 【解答】前序：a，b，c，d，e，D 1．假設(shè)一棵二叉樹廣義表表示為a(b(c)，d(e，D)，分別寫出對(duì)它進(jìn)行前序、中序、后序遍歷的結(jié)果。 10. √ 7. √ 4. 3. 2. 1. ，雙親鏈表表示法，孩子鏈表表示法，孩子兄弟鏈表表示法 20．n+l。 17. HIDJKEBLFGCA0 ：EACBDGF，森林包括1棵樹。 ，F(xiàn)。 ，空樹。 。 10. 160 。 2/n , (3) nlk+n+1,(4)i≠nk+l(n=0,l,2，…),n+1. 二、填空題（參考答案） 19．D 17．A15．B 14．A13．B (7)C (5)C (3)C 10. (1)C8．B7．A 6．C 4．A，C 一、選擇題（參考答案）8．假設(shè)二叉樹采用鏈接方法存儲(chǔ)，編寫一個(gè)函數(shù)按凹入表表示法打印出該二叉樹。6．給出中序線索樹的結(jié)點(diǎn)結(jié)構(gòu)，設(shè)計(jì)算法在不使用棧和遞歸的情況下前序遍歷一棵中序線索樹，并分析它的時(shí)間復(fù)雜度。 (2)程序?yàn)榉沁f歸形式。 (l)額外空間的使用只能為O(1)。3．一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)對(duì)該完全二叉樹進(jìn)行前序遍歷的算法。2．假設(shè)在表示一棵二叉樹的二叉鏈表上增加兩個(gè)域：雙親域用于指示其雙親結(jié)點(diǎn)，標(biāo)志域flag（可取0...2）的值，用以區(qū)分在遍歷過程中到達(dá)該結(jié)點(diǎn)時(shí)繼續(xù)向右或向左或訪問該結(jié)點(diǎn)。 )五、算法設(shè)計(jì)題1．編寫對(duì)二叉樹進(jìn)行中序遍歷的非遞歸算法，并對(duì)算法執(zhí)行題圖66所示的二叉樹的情況進(jìn)行跟蹤（即給出各階段棧的變化及輸出的結(jié)點(diǎn)序列）。 （sltag） if（srtag） s=Xrchild。 { INSUCC (BiTree下面的算法返回x所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的位置。9．已知信息為“ABCD BCD CB DB ACB”，請(qǐng)按此信息構(gòu)造哈夫曼樹，求出每一字符的最優(yōu)編碼。8．試找出分別滿足下列條件的所有二叉樹：7．已知一棵樹如題圖65所示，將其轉(zhuǎn)換為其孩子兄弟表示的二叉樹。 數(shù)組BT的存放形式是相對(duì)于滿二叉樹中編號(hào)為數(shù)組下標(biāo)值的結(jié)點(diǎn)值。5. 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組BT中，如題表61所示。 (9)樹的深度是多少？ (7)哪些是結(jié)點(diǎn)E的兄弟？哪些是結(jié)點(diǎn)F的兄弟？ (5)哪些是結(jié)點(diǎn)G的孩子？ (3)哪個(gè)是結(jié)點(diǎn)G的雙親？ (1)哪個(gè)是根結(jié)點(diǎn)？ 葉子： 雙支： 后根序列：c，e，d，b，i，j，h，g，fa 中序：( ( )9．二叉樹的前序和后序遍歷序列能惟一確定這棵二叉樹。((((((( ，樹的存儲(chǔ)結(jié)構(gòu)分為____。，9，6，2，5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為____。 則后序遍歷該二叉樹時(shí)結(jié)點(diǎn)訪問的順序?yàn)開___。，后序序列為BDCAFGE，則該二叉樹結(jié)點(diǎn)的前序序列為____，該二叉樹對(duì)應(yīng)的森林包括____棵樹。，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是____ ，結(jié)點(diǎn)最少的二叉樹為____。，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為____個(gè)，其中____個(gè)用于鏈接孩子結(jié)點(diǎn)，____個(gè)空閑著。，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)為____個(gè)。7．二叉樹的遍歷分為____ ，樹與森林的遍歷包括____。 (4)編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是____：其右兄弟的編號(hào)是____。 (3)編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是____。 (2)編號(hào)為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號(hào)是____。 (1)第i層結(jié)點(diǎn)數(shù)目
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1