在我們解釋二叉樹之前帽驯，首先來看一下樹的概念
一寸痢、樹的概念
樹也是一種數(shù)據(jù)結(jié)構(gòu)，大家可以想象一下印衔，自然界中的樹木啡捶，樹木的葉子就相當(dāng)于樹的結(jié)點，那樹其實就是N(N>0)個結(jié)點的有限集合奸焙。其中有一個特殊的結(jié)點叫做樹根瞎暑，這個結(jié)點沒有前趨，除了根結(jié)點之外与帆，其余的結(jié)點可以看成是M(M>=0)個互不相交的集合了赌，每一個集合又可以看成是一棵樹，也就是根的子樹玄糟。也就是說勿她，樹其實就是由有限個子樹組成，而且沒有次序之分阵翎。如下圖一所示嫂拴。
圖一
如上圖所示播揪，這個樹組成了一個有限的集合T={A,B,C,D,E,F,G,H},其中A結(jié)點是根結(jié)點，它有兩顆子樹筒狠，T1 = {B,D,E,F}猪狈，以及T2 = {C,G,H},這兩個子集互不相交。而T1該子樹的根結(jié)點是B辩恼，它又有子集{D},{E},{F},同理可論證T2.
二雇庙、二叉樹的概念
首先要注意一個知識點就是二叉樹并不是樹的特殊情形，他們是兩種不同的數(shù)據(jù)結(jié)構(gòu)灶伊。其次疆前，二叉樹可以為空，也可以只有左子樹聘萨，或者右子樹竹椒，亦或者由一個根結(jié)點加上左右兩個互不相交的二叉樹構(gòu)成。
下面我們用python實現(xiàn)二叉樹米辐，來看看二叉樹的實現(xiàn)原則：
1胸完、第一個建立的元素是根結(jié)點
接下來我們再來看看二叉樹的幾種遍歷方法：
樹的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷，前者有前序翘贮、中序赊窥、后序，后者有層次遍歷狸页。一般來說锨能，深度優(yōu)先用遞歸，廣度優(yōu)先用隊列芍耘。
圖2
1址遇、前序遍歷
前序遍歷是先遍歷根結(jié)點，再遍歷左子樹斋竞，最后才遍歷右子樹倔约。根據(jù)前序遍歷，訪問順序為A->B->D-G,C->E>H,F->I
2窃页、中序遍歷
中序遍歷是先遍歷左子樹，再遍歷根結(jié)點复濒，最后才遍歷右子樹脖卖。訪問順序為G->D->B->A,H->E->C,F->I
3、后序遍歷
后續(xù)遍歷是先遍歷左子樹巧颈，再遍歷右子樹畦木，最后才遍歷根結(jié)點。訪問順序是G->D->B->H->E-I->F->C->A
4砸泛、層次遍歷
層次遍歷是指從二叉樹的第一層（根結(jié)點）開始十籍，從上至下逐層遍歷蛆封，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問勾栗，訪問順序是A->B->C->D->E->F->G->H->I
下面是實現(xiàn)前3種遍歷的python代碼惨篱，使用遍歷
而對于層次遍歷需要使用隊列，可按如下步驟進行：
（1）初始化一個隊列
（2）二叉樹的根結(jié)點放入隊列
（3）重復(fù)步驟(4)-(7)直至隊列為空
（4）從隊列中取出一個結(jié)點x
（5）訪問結(jié)點x
（6）如果x存在左子結(jié)點围俘，將左子結(jié)點放入隊列
（7）如果x 存在右子結(jié)點砸讳，將右子結(jié)點放入隊列
下面是代碼實現(xiàn)：
