假設一棵二元樹（Binary tree）總共有n 個節點，其中每個節點都恰有0 個或2 個子節點（Children），該二元樹的內部節點（Internal no…

題目

假設一棵二元樹（Binary tree）總共有n 個節點，其中每個節點都恰有0 個或2 個子節點（Children），該二元樹的內部節點（Internal nodes）有幾個？ A. (n+1)/2 B. (n+1)/2–1 C. n/2–1 D. (n–1)/2

官方答案

• 答案：D. (n–1)/2

解析

此為「滿二元樹」：每個節點恰有 0 或 2 個子節點。設內部節點（有 2 子節點者）為 I，葉節點（0 子節點）為 L，總節點 n = I + L。由邊數 = n−1，且每個內部節點貢獻 2 條邊，故 2I = n−1，得 I = (n−1)/2，選 D。同時葉節點數 L = (n+1)/2，即選項 A 所給的是葉節點而非內部節點，須分辨。B、C 的式子不符此關係。關鍵公式：滿二元樹中內部節點 = (n−1)/2、葉 = (n+1)/2，且 n 必為奇數。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。