申論題

2.二元樹(binarytree)的定義是:樹的每個內部節點(internalnode)最多只有兩個子節點。如下圖的二元樹所示，每個節點最多只有兩個子節點，亦即最多只可以有兩棵子樹(subtree)。 它有一個性質:例如第3階層最多有2³⁻¹=2²=4個節點，據此推論，第五階層最多應該 有2⁵⁻¹=16個節點。只要簡單畫出幾階層滿滿的二元樹，應該可以看出其規律性。請使用數學歸納法(MathematicalInduction)分成三個步驟證明「高度為i階層的二元樹所有節 點數目最多為2ⁱ−1個」。(11分)