數(shù)據(jù)結(jié)構(gòu)課后習(xí)題及解析六-wenkub
2023-04-09 03:02:25 本頁(yè)面
【正文】 1 + …… + nk樹(shù)中分支數(shù)目為B,則B=n1 + 2n2 + 3n3 + …… + knk因?yàn)槌Y(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有n= B + 1即n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1由上式可得葉子結(jié)點(diǎn)數(shù)為：n0 = n2 + 2n3 + …… + (k1nk + 1，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)？【解答】n0表示葉子結(jié)點(diǎn)數(shù)，n2表示度為2的結(jié)點(diǎn)數(shù)，則n0 = n2+16．1分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。3．如題1要求建立好二叉樹(shù)，按凹入表形式打印二叉樹(shù)結(jié)構(gòu)，如下圖所示。[基本要求] 從鍵盤(pán)接受輸入先序序列，以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹(shù)以先序來(lái)建立）并對(duì)其進(jìn)行遍歷先序、中序、后序），然后將遍歷結(jié)果打印輸出。22. 證明：給定一棵二叉樹(shù)的前序序列與中序序列，可唯一確定這棵二叉樹(shù)； 給定一棵二叉樹(shù)的后序序列與中序序列，可唯一確定這棵二叉樹(shù)；23. 二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，編寫(xiě)算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。正則二叉樹(shù)是指：在二叉樹(shù)中不存在子樹(shù)個(gè)數(shù)為1的結(jié)點(diǎn)。16．編寫(xiě)算法，對(duì)一棵以孩子兄弟鏈表表示的樹(shù)統(tǒng)計(jì)其葉子的個(gè)數(shù)。13．編寫(xiě)遞歸算法：對(duì)于二叉樹(shù)中每一個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹(shù)，并釋放相應(yīng)的空間。，中序序列為ABCDEFGHIJK，請(qǐng)畫(huà)出該二叉樹(shù)。 個(gè)人資料整理 僅限學(xué)習(xí)使用第六章習(xí)題1．試分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。5．已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)？6．給出滿足下列條件的所有二叉樹(shù)：① 前序和后序相同② 中序和后序相同③ 前序和后序相同7． n個(gè)結(jié)點(diǎn)的K叉樹(shù)，若用具有k個(gè)child域的等長(zhǎng)鏈結(jié)點(diǎn)存儲(chǔ)樹(shù)的一個(gè)結(jié)點(diǎn)，則空的Child域有多少個(gè)？8．畫(huà)出與下列已知序列對(duì)應(yīng)的樹(shù)Ｔ：樹(shù)的先根次序訪問(wèn)序列為GFKDAIEBCHJ；樹(shù)的后根次序訪問(wèn)序列為DIAEKFCJHBG。14．分別寫(xiě)函數(shù)完成：在先序線索二叉樹(shù)T中，查找給定結(jié)點(diǎn)*p在先序序列中的后繼。17．對(duì)以孩子兄弟鏈表表示的樹(shù)編寫(xiě)計(jì)算樹(shù)的深度的算法。20．計(jì)算二叉樹(shù)最大寬度的算法。24. 二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，編寫(xiě)算法，將二叉樹(shù)左右子樹(shù)進(jìn)行交換。要求采用遞歸和非遞歸兩種方法實(shí)現(xiàn)。 中序：CBEGDFA2. 按凹入表形式打印樹(shù)形結(jié)構(gòu)，如下圖所示?！窘獯稹烤哂?個(gè)結(jié)點(diǎn)的樹(shù)(2 中序序列與后序序列相同。 (1 前序與中序相同：空樹(shù)或缺左子樹(shù)的單支樹(shù)； (3 前序與后序相同：空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)。哈夫曼編碼為：I1：11111I5：1100 I7： 01【解答】 pre = pLChild。else q=qRChild。 *p/*在中序線索二叉樹(shù)中查找p的中序后繼結(jié)點(diǎn)，并用succ指針?lè)祷亟Y(jié)果*/{ if (pRtag= =1 /*直接利用線索*/ qLtag=
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1