二元樹 - tw511教學網

二元樹是一種特殊型別的通用樹，它的每個節點最多可以有兩個子節點。二元樹通常被劃分為三個不相交的子集。

二元樹的結構，如在下圖中顯示。

1. 二元樹的型別

在嚴格二元樹中，每個非葉節點包含非空的左和右子樹。換句話說，每個非葉節點的等級將始終為2。具有n個葉子的嚴格二元樹將具有(2n-1)個節點。

嚴格二元樹如下圖所示。

如果所有葉子都位於相同的水平d，則稱二元樹是完全二元樹。完全二元樹是二元樹，在0級和d級之間的每個級別包含正好2 ^ 1個節點。具有深度d的完全二元樹中的節點總數是2^d+1 -1，其中葉節點是2d而非葉節點是2^d-1。

二元樹遍歷的方法有以下幾種：

編號	遍歷	描述
1	前序遍歷	首先遍歷根，然後分別遍歷左子樹和右子樹。該過程將遞回地應用於樹的每個子樹。
2	中序遍歷	首先遍歷左子樹，然後分別遍歷根和右子樹。該過程將遞回地應用於樹的每個子樹。
3	後序遍歷	遍歷左子樹，然後分別遍歷右子樹和根。該過程將遞回地應用於樹的每個子樹。

二元樹有兩種表示形式：

在這種表示中，二元樹以連結串列的形式儲存在儲存器中，其節點的數量儲存在非連續的儲存器位置並通過像樹一樣繼承父子關係而連結在一起。每個節點包含三個部分：指向左節點的指標，資料元素和指向右節點的指標。每個二元樹都有一個根指標，指向二元樹的根節點。在空二進位制樹中，根指標將指向null。

如下圖中給出的二元樹。

在上圖中，樹被視為節點的集合，其中每個節點包含三個部分：左指標，資料元素和右指標。左指標儲存左子節點的地址，而右指標儲存右子節點的地址。葉節點的左右指標包含null。

下圖顯示了如何使用連結表示為二元樹分配記憶體。記憶體中維護了一個特殊指標，指向樹的根節點。樹中的每個節點都包含其左右子節點的地址。葉節點的左右指標包含null。

這是儲存樹元素的最簡單的記憶體分配技術，但它是一種效率低下的技術，因為它需要大量空間來儲存樹元素。下圖顯示了二元樹及其記憶體分配。

在這種表示方式中，陣列用於儲存樹元素。陣列的大小將等於樹中存在的節點數。樹的根節點將出現在陣列的第一個索引處。如果節點儲存在第i個索引處，則其左右子節點將儲存在2i和2i + 1位置。如果陣列的第一個索引，即tree[1]為0，則表示樹為空。