一、樹的定義

樹形結構是一類重要的非線性結構。樹形結構是結點之間有分支，并具有層次關系的結構。它非常類似于自然界中的樹。
樹的遞歸定義：
樹(Tree)是n(n≥0)個結點的有限集T，T為空時稱為空樹，否則它滿足如下兩個條件：
(1)有且僅有一個特定的稱為根(Root)的結點；
(2)其余的結點可分為m(m≥0)個互不相交的子集Tl，T2，…，Tm，其中每個子集本身又是一棵樹，并稱其為根的子樹(Subree)。

二、二叉樹的定義

二叉樹是由n（n≥0）個結點組成的有限集合、每個結點最多有兩個子樹的有序樹。它或者是空集，或者是由一個根和稱為左、右子樹的兩個不相交的二叉樹組成。
特點：
（1）二叉樹是有序樹，即使只有一個子樹，也必須區分左、右子樹；
（2）二叉樹的每個結點的度不能大于2，只能取0、1、2三者之一；
（3）二叉樹中所有結點的形態有5種：空結點、無左右子樹的結點、只有左子樹的結點、只有右子樹的結點和具有左右子樹的結點。

三、二叉樹的性質

性質1：二叉樹的第i層上最多有個結點。
性質2：深度為h的二叉樹上最多有-1個結點。
性質3：具有n個結點的二叉樹的高度不小于的最大整數。
性質4：任意一棵二叉樹中，如果葉子結點的個數為n0，度為2的結點的個數為n2，則必然有n0＝n2＋1。
滿二叉樹：若深度為h的二叉樹，恰好具有-1個結點，則稱為滿二叉樹。
完全二叉樹：若一棵具有n個結點的二叉樹的邏輯結構與滿二叉樹的前n個結點的邏輯結構完全相同，則稱該二叉樹為完全二叉樹
擴充二叉樹：除葉子結點外，其余結點都必須有兩個孩子的二叉樹。

四、二叉樹的存儲結構

二叉樹的存儲結構有順序存儲結構、鏈式存儲結構
順序存儲：結構采用一維數組存儲的。根據二叉樹的性質6可計算出雙親結點、左右孩子結點的下標。因此滿二叉樹、完全二叉樹的存儲可采用一維數組，把結點按從上到下、從左到右的順序存放在數組中，結點之間的關系可由性質6的公式計算得到。
鏈式存儲：結構采用鏈表存儲二叉樹中的數據元素，用鏈建立二叉樹中結點之間的關系。二叉樹最常用的鏈式存儲結構是二叉鏈，每個結點包含三個域，分別是數據元素域data、左孩子鏈域lChild和右孩子鏈域rChild。與單鏈表帶頭結點和不帶頭結點的兩種情況相似，二叉鏈存儲結構的二叉樹也有帶頭結點和不帶頭結點兩種

五、二叉樹的操作

python數據結構之二叉樹的建立實例

python數據結構之二叉樹的遍歷實例

python數據結構之二叉樹的統計與轉換實例