二叉樹的頂點？

分析一些樹的算法時，我們常常需要以給定的二叉樹的頂點數n(T) 來度量問題實例的規模。而這個頂點數n(T) 指的就是樹的擴展形式中所有頂點的個數，這些頂點分兩類，一類是外部頂點，一類就是內部頂點。根據定義，一顆擴展的空二叉樹是一個單獨的外部頂點。

為了確定一些算法(遞歸的求樹的高度，遞歸的前序、中序、后續遍歷，求葉節點數等等)的效率，我們需要知道一顆包含n 個內部頂點的擴展二叉樹最多能夠具有幾個外部頂點。考察幾個例子后，我們容易做出這種假設：外部頂點的數量x 比內部頂點的數量大一，即

x = n + 1。

在n ≥ 0 的情況下，我們對內部頂點使用強數學歸納法來證明該等式。

歸納基礎：n = 0 時，根據定義，一顆空樹只有一個外部頂點，滿足等式 x = n + 1。

歸納假設：假設當任意二叉樹具有0 ≤ k ≤ n 個內部頂點時，x = k + 1。

下面我們證明當k = n + 1 時命題依然成立。不失一般性，假設T 的左子樹的內部頂點和外部頂點的個數分別是nL 和 xL，T 的右子樹的內部頂點和外部頂點的個數分別是nR 和xR，左右子樹內部節點的個數滿足我們的歸納假設，因此我們有

x = xL + xR = (nL+1) + (nR+1) = n + 1。命題得證。