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

1、第七章 樹和二叉樹習(xí)題1. 已知一棵樹中的關(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)，試畫出該樹，并回答以下問題：(1)(2)(3)(4)(5)(6)(7)哪個結(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 的層次分別是多少？該樹的深度和度分別是多少？以結(jié)點(diǎn) C 為根的的深度是多少？2.一棵度為 2 的樹

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