數(shù)據(jù)結(jié)構(gòu)課后習(xí)題及解析第六章(參考版)
2025-03-28 03:02本頁(yè)面
【正文】 [提示]：，用先根遍歷。[提示]：（1），實(shí)現(xiàn)逐層遍歷（2）隊(duì)中保存每個(gè)結(jié)點(diǎn)的打印位置，其左、右子的距離3．如題1要求建立好二叉樹(shù)，按凹入表形式打印二叉樹(shù)結(jié)構(gòu)。[測(cè)試數(shù)據(jù)] ABCффDEфGффFффф（其中ф表示空格字符）[基本要求] 從鍵盤(pán)接受輸入先序序列，以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹(shù)（以先序來(lái)建立）并對(duì)其進(jìn)行遍歷（先序、中序、后序），然后將遍歷結(jié)果打印輸出。20．計(jì)算二叉樹(shù)最大寬度的算法。[提示]：可利用任何遞歸、非遞歸遍歷算法。19．設(shè)二叉樹(shù)按二叉鏈表存放，寫(xiě)算法判別一棵二叉樹(shù)是否是一棵正則二叉樹(shù)。18．已知二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，利用棧的基本操作寫(xiě)出后序遍歷非遞歸的算法。[提示]：（1）可將孩子兄弟鏈表劃分為根、首子樹(shù)、兄弟樹(shù)，遞歸處理。（參例題）[提示]：（1）先查看線索，無(wú)線索時(shí)用下面規(guī)律：（2）結(jié)點(diǎn)*p在先序序列中的后繼為其左子或右子；（3）結(jié)點(diǎn)*p在后序序列中的前驅(qū)也是其左子或右子。}}[方法2]：（1）先序查找；（2）直接查看當(dāng)前根結(jié)點(diǎn)（3）用指針參數(shù)；[方法3]：（1）先序查找；（2）直接查看當(dāng)前根結(jié)點(diǎn)（3）通過(guò)函數(shù)值，返回刪除后結(jié)果；（參示例程序）14．分別寫(xiě)函數(shù)完成：在先序線索二叉樹(shù)T中，查找給定結(jié)點(diǎn)*p在先序序列中的后繼。DelTree(btRChild,DelTree(btLChild, btRChild=NULL。 btRChilddata==x){ FreeTree(btRChild)。 if (btRChild amp。 btLChild=NULL。 btLChilddata==x){ FreeTree(btLChild)。 { if (btLChild amp。 DataType x){ if ( bt ) x)}else FreeTree(*bt)。amp。 *bt,13．編寫(xiě)遞歸算法：對(duì)于二叉樹(shù)中每一個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹(shù)，并釋放相應(yīng)的空間。10．已知二叉樹(shù)采用二叉鏈表存放,要求返回二叉樹(shù)T的后序序列中的第一個(gè)結(jié)點(diǎn)的指針,是否可不用遞歸且不用棧來(lái)完成?請(qǐng)簡(jiǎn)述原因.[提示]：無(wú)右子的“左下端”8．畫(huà)出與下列已知序列對(duì)應(yīng)的樹(shù)Ｔ：樹(shù)的先根次序訪問(wèn)序列為GFKDAIEBCHJ；樹(shù)的后根次序訪問(wèn)序列為DIAEKFCJHBG。 D L R 與L R D 的相同點(diǎn)：D，如果無(wú) L R，則完全相同。c) D L R 與L D R 的相同點(diǎn)：D R，如果無(wú) L，則完全相同, 如果無(wú) LR，…。a) 前序和中序相同b) 給出滿足下列條件的所有二叉樹(shù)：a)（2）滿二叉樹(shù)或完全二叉樹(shù)具有最少的一度結(jié)點(diǎn)（3）可能的最大滿二叉樹(shù)是幾層？有多少葉結(jié)點(diǎn)？如何增補(bǔ)？255026可能的最大滿二叉樹(shù)是6層有 25 = 32個(gè)葉結(jié)點(diǎn)假設(shè)將其中x個(gè)變?yōu)?度結(jié)點(diǎn)后，總?cè)~結(jié)點(diǎn)數(shù)目為50則：2x + (32 – x) = 50得：x = 18此時(shí)總結(jié)點(diǎn)數(shù)目= ( 26 – 1) + 182[方法2]假設(shè)完全二叉樹(shù)的最大非葉結(jié)點(diǎn)編號(hào)為m，
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1