算法與數(shù)據(jù)結(jié)構(gòu)課件習(xí)題樹(shù)

1、第七章 樹(shù)和二叉樹(shù)習(xí)題1. 已知一棵樹(shù)中的關(guān)系 R=(I, M), (I, N), (E, I), (B, E), (B,D), (A, B), (G, J), (G, K), (C, G), (C, F), (H,L), (C, H), (A, C)，試畫(huà)出該樹(shù)，并回答以下問(wèn)題：(1)(2)(3)(4)(5)(6)(7)哪個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)？哪些結(jié)點(diǎn)是葉子結(jié)點(diǎn)？哪些結(jié)點(diǎn)分別是 G 的雙親結(jié)點(diǎn)，祖先結(jié)點(diǎn)，孩子結(jié)點(diǎn)？哪些結(jié)點(diǎn)分別是 E 的子孫結(jié)點(diǎn)，兄弟結(jié)點(diǎn)？哪些結(jié)點(diǎn)是 F 的兄弟結(jié)點(diǎn)？結(jié)點(diǎn) B 和 N 的層次分別是多少？該樹(shù)的深度和度分別是多少？以結(jié)點(diǎn) C 為根的的深度是多少？2.一棵度為 2 的樹(shù)

2、與一棵二叉樹(shù)有何區(qū)別？3.試分別畫(huà)出具有 3 個(gè)結(jié)點(diǎn)的樹(shù)和 3 個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。將一棵有 100 個(gè)節(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右為 1，則為 493.，根節(jié)點(diǎn)的的節(jié)點(diǎn)的右孩子A97是（B98）。C99D1004. 設(shè)根結(jié)點(diǎn)的高度為 0，則高度為 k 的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為（）。2k-1-1A2kB2k+1-1C2k -1D5. 一棵有 n 個(gè)結(jié)點(diǎn)滿二叉樹(shù)有個(gè)度為 1 的結(jié)點(diǎn)，有個(gè)分支結(jié)點(diǎn)和個(gè)葉子結(jié)點(diǎn)，該滿二叉樹(shù)的深度為。6. 深度為 6（根的層次為 1）的完全二叉樹(shù)至多有結(jié)點(diǎn)，至少有結(jié)點(diǎn)。1.已知二叉樹(shù)，分別求該二叉樹(shù)的前序、中序、后序遍歷。2. 已知二叉樹(shù)的中序遍歷為：dgbaechif，后序遍歷為：gdbeihfca，求該二叉樹(shù)及其前序遍歷3. 已知二叉樹(shù)的后序遍歷為：echfjigdba，中序遍歷為：ec二叉樹(shù)djiga，求該二叉樹(shù)及其前序線索化4. 現(xiàn)有按中序遍歷二叉樹(shù)的結(jié)果為 abc，問(wèn)有幾種不同形態(tài)的二叉樹(shù)可以得到這一結(jié)果。FHABCDGIJEK1.請(qǐng)將以上三棵樹(shù)分別轉(zhuǎn)換為二叉樹(shù)。AABCDDBCEFGHIJGEFKLM2. 請(qǐng)將樹(shù)轉(zhuǎn)換為二叉樹(shù)。3. 請(qǐng)將二叉樹(shù)轉(zhuǎn)換為森林。12345678126/347aef*958bcd設(shè)給定權(quán)集w=2,3,4,7,8,9,試構(gòu)造一棵樹(shù)，并求其帶權(quán)路徑長(zhǎng)度