一、題目：
在度為4的樹中，若有20個度為4的節點，10個度為3的節點，1個度為2的節點，10個度為1的節點，則樹T的葉節點個數是？
這道題是2010年計算機聯考真題。我用手算（半蠻力）解出答案是82，結果是對的，但是耗時較長，而且如果數字再大點也不好算了，是以肯定存在一種更加高效的方法。
我們知道，
- 樹的節點的個數=樹的度+1
于是樹的節點個數
N = 1 + 20*4 + 10*3 + 1*2 + 10*1
但同時，樹的節點個數也可以寫成是：葉子節點數+度為1的節點數+…+度為4的節點數
即
N = N0 + 20 + 10 + 1 + 10
，其中N0為葉子節點個數
由上述兩個式子就可解出葉子節點個數為82了。
這個方法解題效率比半蠻力法高多了，而且更準确
二、題目
設二叉樹有2n個節點，且m<n
，不可能存在（）的節點
A. n個度為0 B. 2m個度為0 C. 2m個度為1 D. 2m個度為2
這道題涉及到的知識為：
- 二叉樹中，葉節點的數目N0等于度為2的節點數目N2加一。 即
N0 = N2 + 1
設度為
i
的節點的數量為
Ni
，則
2n = N0 + N1 + N2
又因
N0 = N2 + 1
，故
2n = N1 + 2N2 + 1
是以可以推算出
N1 = 2n - 2N2 -1
，必為奇數，由此直接判斷本題選C
三、題目
【2009年計算機聯考真題】若一顆完全二叉樹有768個結點，則該二叉樹葉節點個數為？
該題有兩種算法。
算法一：
- 完全二叉樹中最後一個樹枝節點的編号為
n/2
是以該完全二叉樹最後一個數值結點的編号為
768/2=384
（從1開始編号），是以葉子節點個數為
768-384=384
算法二：
設
N
為二叉樹總節點數，
Ni
為 度為
i
的節點數
N = N0 + N1 + N2
，
N0 = N2 + 1
，即
N = N1 + 2N2 + 1
是以768 = N1 + 2N2+1，而N1隻能等于0或1（完全二叉樹中）
是以可以解出N1 = 1，N2 = 383，是以N0 = N2+1=384
四、題目
已知一棵有2011個結點的樹，其葉結點個數是11個，該樹對應的二叉樹中無右孩子的結點的個數是？
該題可參考該部落格：連結跳轉 需要注意的是樹轉換為二叉樹時，是左孩子右兄弟，上述部落格中有筆誤。
五、題目
在二叉樹中有兩個結點m和n,如果m是n的祖先,可以找到從m到n的路徑的周遊方式是?
這道題想了我很久，答案是 後序周遊
似乎有點難以了解，試想先序周遊、中序周遊、層次周遊都會周遊到m和n啊，層次周遊和路徑無關，自然不選，但是先序和中序為何不行？
這就得先看清楚，題目中所寫為 m是n的祖先，祖先可不僅僅隻能是父節點。如果是父節點，那麼不管哪一種都好說。而祖先的話，試想 n是m的第18代兒子，假設又是滿二叉樹，天呐，從記錄下m開始到找到n，中間可能性有多少？2的18次方種可能，顯然全部記錄下來然後從中選一個是不現實的吧，是以從上往下找，這種思路本就是不可行的。（沒說清楚？和這個問題很像，可以參考：戳）打個更簡單的比方，一個皇帝想從幾十億的人中找到你是很難的，但是你想找那個皇帝，卻是很簡單的。
而既然排除了從上往下，也就排除了先序和中序，那後序為什麼可以呢？因為後序周遊，無論是在左子樹還是右子樹，在傳回的路上，都必然會經過祖先節點，是以，不管是不是遞歸的方法，都可以找得到這條路徑。
非遞歸求解該問題的僞代碼見第八題，隻要從棧中提出n，則棧裡面剩下的就是從根節點到n的路徑節點。
六、題目
線索二叉樹是一種( )結構？
A. 邏輯
B. 邏輯和存儲
C. 實體
D. 線性
答案選C，解題方案見：該題題解
七、題目
（）的周遊仍需要棧的支援
A. 前序線索樹
B. 中序線索樹
C. 後序線索樹
D. 所有線索樹
這是一道很簡單的題目，顯然選C，因為後序線索樹可能不能根據線索找到直接後繼節點。
這裡小結一下：
- 先序線索二叉樹可以求先序後繼
- 先序線索二叉樹不可以求先序前驅
- 中序線索二叉樹可以求中序後繼
- 中序線索二叉樹可以求中序前驅
- 後序線索二叉樹不可以求後序後繼
- 後序線索二叉樹可以求後序前驅
八、程式設計題
編寫後序周遊二叉樹的非遞歸算法
後序周遊二叉樹，如果使用遞歸很簡單，就三五句話
void PostOrder(BiTree T)
{
if(T != NULL)
{
PostOrder(T->lchild);
PostOrder(T->Rchild);
visit(T);
}
} 但是使用非遞歸算法，後序周遊是最麻煩的一種了，代碼如下：
void PostOrder(BiTree T)
{
InitStack(S);
BiTree *p = T;
//r指針用來指向上一個通路過的節點
//用于在通路一棵子樹的根節點時判斷是從左子樹傳回還是右子樹傳回
BiTree *r = T;
while(p && !IsEmpty(S))
{
if(p)
{
//找到最左端的節點，路徑上的節點全部入棧,包括葉子節點
push(S,p);
p = p->lchild;
}
else
{
GetTop(S,p);
if(p->rchild && p->rchild!=r)
{
//如果p有右孩子，且右孩子未被通路過
p = p->rchild;
push(S,p);
p = p->lchild; //再走到最左
}
else
{
pop(S,p);
visit(p);
r = p;
p = NULL;
}
}
}
} 請畫圖了解上述代碼。且上述代碼适用于其他情況。
當通路一個節點
*p
時，棧裡節點恰好是
*p
節點的所有祖先。這構成了從根節點到
*p
節點的一條路徑，是以本算法可以求最短路徑、兩個節點的最近公共祖先等。
九、題目
含有二十個節點的平衡二叉樹的最大深度為（）
A. 4 B. 5 C. 6 D. 7
這道題涉及到的就是平衡二叉樹裡的一個規律：
- 假設以Nh表示深度為h的平衡樹中含有的最少節點數，那麼
N0 = 0 ,N1 = 1, N2 = 2
Nh = Nh-1 + Nh-2 + 1
是以這道題很明顯了，N0 = 0, N1 = 1, N2 = 2, N3 = 4, N4 = 7, N5 = 12, N6 = 20
是以選 C
十、綜合應用題
畫出一個二叉樹，使它既滿足大根堆的要求又滿足二叉排序樹的要求
這道題看似是一道開放性的題，是以看着覺得很奇怪。然而這是因為我不知道大根堆是什麼東西的原因。
所謂大根堆，下面是百度百科的解釋：
最大堆是堆的兩種形式之一。
根結點（亦稱為堆頂）的關鍵字是堆裡所有結點關鍵字中最大者，稱為大根堆，又稱最大堆（大頂堆）。
大根堆要求根節點的關鍵字既大于或等于左子樹的關鍵字值，又大于或等于右子樹的關鍵字值。
而且，大根堆還要求樹是完全二叉樹。
資料結構老師沒教過堆排序的弱渣飄過
然後就很簡單了，首先，根節點比左右節點都大，而且二叉排序樹要求根節點比右節點小，那麼沒有右節點就得了。然後因為又要求必須是完全二叉樹，是以這棵樹隻能有兩個節點，一個根節點，一個是根節點的左節點。
是以這棵樹是唯一的！！！