第3章 二叉樹

3.1 二叉樹基礎(chǔ)知識(shí)

二叉樹（Binary Tree）也稱為二分樹、二元樹、對(duì)分樹等，它是n(n≥0)個(gè)有限元素的集合，該集合或者為空或者由一個(gè)稱為根(root)的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當(dāng)集合為空時(shí)，稱該二叉樹為空二叉樹。

在二叉樹中，一個(gè)元素也稱為一個(gè)結(jié)點(diǎn)。二叉樹的遞歸定義為：二叉樹或者是一棵空樹，或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的分別稱為根結(jié)點(diǎn)的左子樹和右子樹所組成的非空樹，左子樹和右子樹又同樣都是一棵二叉樹。

以下是一些常見的二叉樹的基本概念：

（1）結(jié)點(diǎn)的度。結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。

（2）葉子結(jié)點(diǎn)。度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，或者稱為終端結(jié)點(diǎn)。

（3）分支結(jié)點(diǎn)。度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，或者稱為非終端結(jié)點(diǎn)。一棵樹的結(jié)點(diǎn)除葉子結(jié)點(diǎn)外，其余的都是分支結(jié)點(diǎn)。

（4）左孩子、右孩子、雙親。樹中一個(gè)結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子。這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親。具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。

（5）路徑、路徑長度。如果一棵樹的一串結(jié)點(diǎn)n1，n2，…，nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的父結(jié)點(diǎn)（1≤i<k），就把n1，n2，…，nk稱為一條由n1～nk的路徑。這條路徑的長度是k-1。

（6）祖先、子孫。在樹中，如果有一條路徑從結(jié)點(diǎn)M到結(jié)點(diǎn)N，那么M就稱為N的祖先，而N稱為M的子孫。

（7）結(jié)點(diǎn)的層數(shù)。規(guī)定樹的根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它的雙親結(jié)點(diǎn)的層數(shù)加1。

（8）樹的深度。樹中所有結(jié)點(diǎn)的最大層數(shù)稱為樹的深度。

（9）樹的度。樹中各結(jié)點(diǎn)度的最大值稱為該樹的度，葉子結(jié)點(diǎn)的度為0。

（10）滿二叉樹。在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的一棵二叉樹稱為滿二叉樹。

（11）完全二叉樹。一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹，對(duì)樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。完全二叉樹的特點(diǎn)是：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹的左部。需要注意的是滿二叉樹肯定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。

二叉樹的基本性質(zhì)如下：

性質(zhì)1：一棵非空二叉樹的第i層上最多有2^i-1個(gè)結(jié)點(diǎn)（i≥1）。

性質(zhì)2：一棵深度為k的二叉樹中，最多具有2^k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。

性質(zhì)3：對(duì)于一棵非空的二叉樹，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)，即如果葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則有n0=n2+1。

證明：用n0表示度為0（葉子結(jié)點(diǎn)）的結(jié)點(diǎn)總數(shù)，用n1表示度為1的結(jié)點(diǎn)總數(shù)，n2表示度為2的結(jié)點(diǎn)總數(shù)，n表示整個(gè)完全二叉樹的結(jié)點(diǎn)總數(shù)。則n=n0+n1+n2，根據(jù)二叉樹和樹的性質(zhì)，可知n=n1+2*n2+1（所有結(jié)點(diǎn)的度數(shù)之和+1=結(jié)點(diǎn)總數(shù)），根據(jù)兩個(gè)等式可知n0+n1+n2=n1+2*n2+1，所以，n2=n0-1，即n0=n2+1。所以，答案為1。

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為‘log2 n’+1。

證明：根據(jù)性質(zhì)2，深度為k的二叉樹最多只有2^k-1個(gè)結(jié)點(diǎn)，且完全二叉樹的定義是與同深度的滿二叉樹前面編號(hào)相同，即它的總結(jié)點(diǎn)數(shù)n位于k層和k-1層滿二叉樹容量之間，即2^k-1-1<n≤2^k-1或2^k-1≤n<2^k ，三遍同時(shí)取對(duì)數(shù)，于是有k-1≤log2 n<k ，因?yàn)閗是整數(shù)，所以，k=「log2 n」+1。

性質(zhì)5：對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1開始順序編號(hào)，則對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)，有：①如果i>1，則序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為i/2（其中“/”表示整除）；如果i=1，則序號(hào)為i的結(jié)點(diǎn)是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。②如果2i≤n，則序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i；如果2i>n，則序號(hào)為i的結(jié)點(diǎn)無左孩子。③如果2i+1≤n，則序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i+1；如果2i+1>n，則序號(hào)為i的結(jié)點(diǎn)無右孩子。

此外，若對(duì)二叉樹的根結(jié)點(diǎn)從0開始編號(hào)，則相應(yīng)的i號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為(i-1)/2，左孩子的編號(hào)為2i+1，右孩子的編號(hào)為2i+2。

例題1：一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是多少？

分析：二叉樹的公式：n=n0+n1+n2=n0+n1+(n0-1)=2*n0+n1-1。而在完全二叉樹中， n1只能取0或1。若n1=1，則2*n0=1001，可推出n0為小數(shù)，不符合題意；若n1=0，則2*n0-1=1001，則n0=501。所以，答案為501。

例題2：如果根的層次為1，具有61個(gè)結(jié)點(diǎn)的完全二叉樹的高度為多少？

分析：根據(jù)二叉樹的性質(zhì)，具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 +1，因此，含有61個(gè)結(jié)點(diǎn)的完全二叉樹的高度為 +1，即應(yīng)該為6層。所以，答案為6。

例題3：在具有100個(gè)結(jié)點(diǎn)的樹中，其邊的數(shù)目為多少？

分析：在一棵樹中，除了根結(jié)點(diǎn)之外，每一個(gè)結(jié)點(diǎn)都有一條入邊，因此，總邊數(shù)應(yīng)該是100-1，即99條。所以，答案為99。

二叉樹有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)，本章涉及的算法都采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，本章示例代碼用到的二叉樹的結(jié)構(gòu)如下：