1.1.5 樹與二叉樹

本節要求考生掌握樹和二叉樹的基本定義，重點考查二叉樹的基本性質和二叉樹的遍歷。

1.樹的定義

樹是由n（n≥0）個節點組成的有限集合。若n=0，稱為空樹；若n＞0，則：

1）有一個特定的稱為根（Root）的節點。它只有直接后繼節點，而沒有直接前驅節點。

2）除根節點以外的其他節點可以劃分為m（m≥0）個互不相交的有限集合T0,T1,…,Tm-1，每個集合Ti（i=0,1,…,m-l）又是一棵樹，稱為根的子樹；每棵子樹的根節點有且僅有一個直接前驅節點，但可以有0個或多個直接后繼節點。

如圖1-6所示是一棵樹的示例。

2.二叉樹的定義及其性質

二叉樹（Binary Tree）是由n（n≥0）個節點的有限集合構成，此集合或者為空集，或者由一個根節點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹，如圖1-7所示。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。

（1）二叉樹的特點

二叉樹具有以下兩個特點：

1）非空二叉樹只有一個根節點。

2）每一個節點最多有兩棵子樹，且分別稱為該節點的左子樹和右子樹。

在二叉樹中，一個節點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個節點既沒有左子樹也沒有右子樹時，該節點即為葉子節點。

（2）滿二叉樹與完全二叉樹

1）滿二叉樹：除最后一層外，每一層上的所有節點都有兩個子節點，如圖1-8所示。

2）完全二叉樹：除最后一層外，每一層上的節點數均達到最大值；在最后一層上只缺少右邊的若干節點，如圖1-9所示。

如果有一棵具有n個節點的深度為k的完全二叉樹，則它的每一個節點都與深度為k的滿二叉樹中編號為1~n的節點一一對應。

（3）二叉樹的基本性質

性質1：在二叉樹的第k層上至多有2k-1個節點（k≥1）。

性質2：深度為m的二叉樹至多有2m-1個節點。

性質3：對任何一棵二叉樹，度為0的節點（即葉子節點）總是比度為2的節點多一個。

性質4：具有n個節點的完全二叉樹的深度至少為【log2n】+1，其中【log2n】表示log2n的整數部分。

性質5：具有n個節點的完全二叉樹深度為【log2n】+1或【log2（n+1）】。

性質6：如果對一棵有n個節點的完全二叉樹的節點按層序編號（從第1層到第【log2n】+1層，每層從左到右），則對任一節點i（1≤i≤n）有：

1）如果i=1，則節點i無雙親，是二叉樹的根；如果i>1，則其雙親是節點【i/2】。

2）如果2i≤n，則節點i為葉子節點，無左孩子；否則，其左孩子是節點2i。

3）如果2i+1≤n，則節點i無右孩子；否則，其右孩子是節點2i+1。

（4）二叉樹的存儲結構

在計算機中，二叉樹通常采用鏈式存儲結構。用于存儲二叉樹中各元素的存儲節點由兩部分組成：數據域與指針域。但在二叉樹中，由于每一個元素可以有兩個后繼節點（兩個子節點），因此，用于存儲二叉樹的存儲節點的指針域有兩個：一個用于指向該節點的左子節點的存儲地址，稱為左指針域；另一個用于指向該節點的右子節點的存儲地址，稱為右指針域。

3.二叉樹的遍歷

所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有節點，使得每個節點僅被訪問一次。

（1）前序遍歷

前序遍歷是指在訪問根節點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根節點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根節點，然后遍歷左子樹，最后遍歷右子樹。圖1-10中的二叉樹，前序遍歷序列：ABCDEF。

（2）中序遍歷

中序遍歷是指在訪問根節點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根節點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根節點，最后遍歷右子樹。圖1-10中的二叉樹，中序遍歷序列：CBDAEF。

（3）后序遍歷

后序遍歷是指在訪問根節點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根節點；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根節點。圖1-10中的二叉樹，后序遍歷序列：CDBFEA。

例，已知二叉樹的中序遍歷序列為ABCDEFG，后序遍歷序列為BDCAFGE，則前序遍歷序列是什么？

解題過程如下：

1）從后序中，可以先得到根節點是E，然后再看中序的序列：ABCDEFG，可以發現ABCD位于根節點的左邊，而FG位于根節點的右邊，于是得到圖1-11所示的圖形。

2）先來看ABCD這部分，然后看后序序列，在后序序列中有BDCA這一部分，可以確定A是這部分的根，再看中序序列中的ABCD，發現BCD都在A的后面。因此，可以畫出如圖1-12所示的圖形。

3）再看BCD這部分，從后序中看到的順序是BDC，所以C是這部分的根節點，中序序列是BCD，可以斷定B在C的左邊，D在C的右邊。這樣，得到如圖1-13所示的圖形。

4）再看看右邊的FG這部分，從后序序列FG和中序FG中，可以推出，G是這部分的根節點，而F位于G的左邊。得到如圖1-14所示的圖形。

5）根據以上步驟合成一個二叉樹，如圖1-15所示。

6）寫出前序遍歷序列：EACBDGF。