在我們解釋二叉樹之前，首先來看一下樹的概念

一、樹的概念

樹也是一種數(shù)據(jù)結(jié)構(gòu)，大家可以想象一下，自然界中的樹木，樹木的葉子就相當(dāng)于樹的結(jié)點(diǎn)，那樹其實(shí)就是N(N>0)個結(jié)點(diǎn)的有限集合。其中有一個特殊的結(jié)點(diǎn)叫做樹根，這個結(jié)點(diǎn)沒有前趨，除了根結(jié)點(diǎn)之外，其余的結(jié)點(diǎn)可以看成是M(M>=0)個互不相交的集合，每一個集合又可以看成是一棵樹，也就是根的子樹。也就是說，樹其實(shí)就是由有限個子樹組成，而且沒有次序之分。如下圖一所示。

圖一

如上圖所示，這個樹組成了一個有限的集合T={A,B,C,D,E,F,G,H},其中A結(jié)點(diǎn)是根結(jié)點(diǎn)，它有兩顆子樹，T1 = {B,D,E,F}，以及T2 = {C,G,H},這兩個子集互不相交。而T1該子樹的根結(jié)點(diǎn)是B，它又有子集{D},{E},{F},同理可論證T2.

二、二叉樹的概念

首先要注意一個知識點(diǎn)就是二叉樹并不是樹的特殊情形，他們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。其次，二叉樹可以為空，也可以只有左子樹，或者右子樹，亦或者由一個根結(jié)點(diǎn)加上左右兩個互不相交的二叉樹構(gòu)成。

下面我們用python實(shí)現(xiàn)二叉樹，來看看二叉樹的實(shí)現(xiàn)原則：

1、第一個建立的元素是根結(jié)點(diǎn)

接下來我們再來看看二叉樹的幾種遍歷方法：

樹的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷，前者有前序、中序、后序，后者有層次遍歷。一般來說，深度優(yōu)先用遞歸，廣度優(yōu)先用隊列。

圖2

1、前序遍歷

前序遍歷是先遍歷根結(jié)點(diǎn)，再遍歷左子樹，最后才遍歷右子樹。根據(jù)前序遍歷，訪問順序?yàn)锳->B->D-G,C->E>H,F->I

2、中序遍歷

中序遍歷是先遍歷左子樹，再遍歷根結(jié)點(diǎn)，最后才遍歷右子樹。訪問順序?yàn)镚->D->B->A,H->E->C,F->I

3、后序遍歷

后續(xù)遍歷是先遍歷左子樹，再遍歷右子樹，最后才遍歷根結(jié)點(diǎn)。訪問順序是G->D->B->H->E-I->F->C->A

4、層次遍歷

層次遍歷是指從二叉樹的第一層（根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個訪問，訪問順序是A->B->C->D->E->F->G->H->I

下面是實(shí)現(xiàn)前3種遍歷的python代碼，使用遍歷

而對于層次遍歷需要使用隊列，可按如下步驟進(jìn)行：

（1）初始化一個隊列

（2）二叉樹的根結(jié)點(diǎn)放入隊列

（3）重復(fù)步驟(4)-(7)直至隊列為空

（4）從隊列中取出一個結(jié)點(diǎn)x

（5）訪問結(jié)點(diǎn)x

（6）如果x存在左子結(jié)點(diǎn)，將左子結(jié)點(diǎn)放入隊列

（7）如果x 存在右子結(jié)點(diǎn)，將右子結(jié)點(diǎn)放入隊列

下面是代碼實(shí)現(xiàn)：