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

二叉樹是n個結(jié)點的有限集合，它的定義具有遞歸性：

（1）當(dāng)n=0時，為空樹；

（2）當(dāng)n=1時，只有一個結(jié)點，該節(jié)點稱為根結(jié)點；

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

圖1二叉樹

根據(jù)二叉樹的結(jié)構(gòu)和定義，可總結(jié)出二叉樹的特點：

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

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

二叉樹的存儲結(jié)構(gòu)

二叉樹是非線性的結(jié)構(gòu)，其每個結(jié)點最多有一個“前驅(qū)”，但可以有多個“后繼”。它可以采用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

1、順序存儲結(jié)構(gòu)

二叉樹的順序存儲，就是用一組連續(xù)的存儲單元存放二叉樹的結(jié)點。必須把二叉樹的所有結(jié)點安排成一個恰當(dāng)?shù)男蛄薪Y(jié)點在這個序列中的相互位置能反映出結(jié)點之間的邏輯關(guān)系。

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

對于一個二叉樹，如果其不是一個完全二叉樹，則首先增添一些并不存在的空結(jié)點，使之稱為一個完全二叉樹的形式，然后按照從上到下、從左到右的順序?qū)渲械慕Y(jié)點存儲在數(shù)組中。

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

圖2補(bǔ)完后的二叉樹

其順序存儲狀態(tài)為：

ABCDE∧H∧∧FGI

顯然，當(dāng)一個非完全二叉樹采用順序存儲結(jié)構(gòu)時，由于需要增加許多空結(jié)點，因此會造成空間的大量浪費。

2、鏈?zhǔn)酱鎯Y(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用鏈來表示二叉樹結(jié)點之間的邏輯關(guān)系。

通常的方法是鏈表中的每個結(jié)點由3個域組成：

左指針域＋數(shù)據(jù)域＋右指針域

即：Lchild+data+Rchild

其中：data域存放結(jié)點的數(shù)據(jù)信息；

Lchild和Rchild分別存放左、右支的指針，當(dāng)某一支不存在時，相應(yīng)的指針域為空(用符號∧國NULL表示)。

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

三、二叉樹的遍歷算法

二叉樹常用的遍歷方式有：前序遍歷、中序遍歷、后續(xù)遍歷以及層序遍歷。

1、前序遍歷

先訪問根結(jié)點，然后是左子樹，最后是右子樹。

圖1的前序遍歷結(jié)果為：

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

2、中序遍歷

先訪問左子樹，然后是根結(jié)點，最后是右子樹。

圖1的中序遍歷結(jié)果為：

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

3、后續(xù)遍歷

先訪問左子樹，然后是右子樹，最后是根結(jié)點。

圖1的后續(xù)遍歷結(jié)果為：

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

4、層序遍歷

從頂層的結(jié)點開始，從左向右依次遍歷，之后轉(zhuǎn)到第二層，繼續(xù)從左向右遍歷，……，直到所有的結(jié)點都遍歷完成。

圖1的層序遍歷結(jié)果為：

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