第3章 二叉樹

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

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

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

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

1）結(jié)點的度。結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為「log2 n」+1。

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

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

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

例題1：一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(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個結(jié)點的完全二叉樹的高度為多少？

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

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

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

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