1
、給出一棵樹的邏輯結構T=（N，R），其中：
N={A，B，C，D，E，F，G，H，I，J，K}
R={r}
r={（A，B），（B，E），（B，F），（F，G），（F，H），（A，C），（C，I），（C，J），（J，K），（A，D）}
試回答下列問題：
（1）哪個是F的父結點？
（2）哪些是B的子孫？
（3）以結點C為根的子樹的深度是多少？
（注：
根的層數為0，獨根樹深度為0，高度為1
，其他題目同樣如此）
解析
答案： B EFGH 2
2、
將下圖的
二叉樹轉換為對應的森林
，按照
後根次序
列出其結點。
解析：
轉化後的森林如下所示：
參考：
後根深度優先遍歷森林 = 按中序法遍歷對應的二叉樹（左根右）
後根次序列
：EBFCDAIJKHGL
3、
對於以下等價類，採用“
加權合併規則
”（也稱“
重量權衡合併規則
”），進行並查運算，給出最後父節點索引序列。
8-9 3-2 7-4 5-9 6-1 8-6 7-3 2-5 8-0
//右指向左
注意：當合並大小相同的兩棵樹的時候，將第二棵樹的根指向第一棵樹的根；根節點的索引是它本身；數字之間用空格隔開。
解析：（合併時，結點數少的指向結點數多的）
4、
若一個具有
N個頂點
，
K條邊的無向圖
是一個森林（N>K且2K>=N），則該森林有多少棵樹？
解析：
在一棵樹中，結點比邊多一個，即結點比邊多幾個就有幾棵樹。
答案： N-K
5、
一棵
完全三叉樹
，下標為121的結點在第幾層？（注：下標號從0開始，根的層數為0）
解析：
第h層的下標是從（3^h-1）/2到（3^（h+1）-1）/2-1，
第5層的下標是從121到363。
答案： 5
