一、首先，簡單介紹一下什麼是“二叉樹”

二叉樹是n個結點的有限集合，它的定義具有遞迴性：

（1）當n=0時，為空樹；

（2）當n=1時，只有一個結點，該節點稱為根結點；

（3）當n>1時，除了根結點外的其他節點可分為互不相交的兩個子集，稱為左右子樹，且左右子樹本質上也都是二叉樹。

圖1 二叉樹

根據二叉樹的結構和定義，可總結出二叉樹的特點：

（1）非空二叉樹的第i層最多有2∧（i-1）個結點；

（2）深度為k的二叉樹最多有2∧k-1個結點

二叉樹的儲存結構

二叉樹是非線性的結構，其每個結點最多有一個“前驅”，但可以有多個“後繼”。它可以採用順序儲存結構和鏈式儲存結構。

1、順序儲存結構

二叉樹的順序儲存，就是用一組連續的儲存單元存放二叉樹的結點。必須把二叉樹的所有結點安排成一個恰當的序列結點在這個序列中的相互位置能反映出結點之間的邏輯關係。

要介紹順序儲存結構，首先要了解一個概念——完全二叉樹。如果深度為k，有n個結點的二叉樹，當k與n滿足2∧(k-1)≦n≦2∧k-1時，該二叉樹稱為完全二叉樹。

對於一個二叉樹，如果其不是一個完全二叉樹，則首先增添一些並不存在的空結點，使之稱為一個完全二叉樹的形式，然後按照從上到下、從左到右的順序將樹中的結點儲存在陣列中。

以圖1為例，其補成完全二叉樹如圖2所示。

圖2 補完後的二叉樹

其順序儲存狀態為：

A B C D E ∧ H ∧ ∧ F G I

顯然，當一個非完全二叉樹採用順序儲存結構時，由於需要增加許多空結點，因此會造成空間的大量浪費。

2、鏈式儲存結構

二叉樹的鏈式儲存結構是指用鏈來表示二叉樹結點之間的邏輯關係。

通常的方法是連結串列中的每個結點由3個域組成：

左指標域＋資料域＋右指標域即：Lchild + data + Rchild其中：data域存放結點的資料資訊；Lchild和Rchild分別存放左、右支的指標，當某一支不存在時，相應的指標域為空(用符號∧國NULL表示)。

如圖1中的c結點，因其左支不存在，因此其Lchild的值為NULL。

三、二叉樹的遍歷演算法

二叉樹常用的遍歷方式有：前序遍歷、中序遍歷、後續遍歷以及層序遍歷。

1、前序遍歷

先訪問根結點，然後是左子樹，最後是右子樹。

圖1的前序遍歷結果為：

A->B->D->E->F->G->C->H->I

2、中序遍歷

先訪問左子樹，然後是根結點，最後是右子樹。

圖1的中序遍歷結果為：

D->B->F->E->G->A->C->I->H

3、後續遍歷

先訪問左子樹，然後是右子樹，最後是根結點。

圖1的後續遍歷結果為：

D->>F->G->E-> I->H->B->C->A

4、層序遍歷

從頂層的結點開始，從左向右依次遍歷，之後轉到第二層，繼續從左向右遍歷，……，直到所有的結點都遍歷完成。

圖1的層序遍歷結果為：

A->B->C-> D->E->H->F->G->I

說一下建立，因為底層儲存一般都選擇陣列和連結串列，所以對二叉樹有一定的要求，儲存完全二叉樹選擇陣列儲存，比較節省空間，而且透過下標可以快速訪問元素；非完全二叉樹使用陣列儲存會有很多空洞，可以選擇連結串列，用指標來指向左右節點。

對於一棵完全二叉樹，為了便於計算和記憶，我們需要申請一個記憶體空間是樹的元素數量+1的記憶體地址，比如需要建一個10個元素的樹，則需要申請11個長度的記憶體空間。將樹的根節點儲存在下標為1的位置，浪費下標為0的位置，便於尋找時少做一次算數運算。

因此，陣列下標為1的位置儲存根節點，推斷就是對於下標 i，下標 2*i 的位置儲存左子節點，下標 2*i + 1 儲存右子節點，i/2 儲存父節點。

借王爭老師的圖，比如完全二叉樹

儲存過程就是下標為1的位置儲存根節點A，那根據公式 2*i = 2*1 = 2 的位置儲存左子節點B，2*i + 1 = 2*1 +1 = 3 的位置儲存右子節點C，根據下標依次推斷即可。遍歷的話就簡單了，只需要知道根節點位置，而根節點一般選擇下標1，都是明確的位置。

然而非完全二叉樹

使用陣列就會有很大的空洞，故需要使用比如連結串列來儲存。