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