一、樹(shù)的定義

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

二、二叉樹(shù)的定義

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

三、二叉樹(shù)的性質(zhì)

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

四、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
順序存儲(chǔ)：結(jié)構(gòu)采用一維數(shù)組存儲(chǔ)的。根據(jù)二叉樹(shù)的性質(zhì)6可計(jì)算出雙親結(jié)點(diǎn)、左右孩子結(jié)點(diǎn)的下標(biāo)。因此滿二叉樹(shù)、完全二叉樹(shù)的存儲(chǔ)可采用一維數(shù)組，把結(jié)點(diǎn)按從上到下、從左到右的順序存放在數(shù)組中，結(jié)點(diǎn)之間的關(guān)系可由性質(zhì)6的公式計(jì)算得到。
鏈?zhǔn)酱鎯?chǔ)：結(jié)構(gòu)采用鏈表存儲(chǔ)二叉樹(shù)中的數(shù)據(jù)元素，用鏈建立二叉樹(shù)中結(jié)點(diǎn)之間的關(guān)系。二叉樹(shù)最常用的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是二叉鏈，每個(gè)結(jié)點(diǎn)包含三個(gè)域，分別是數(shù)據(jù)元素域data、左孩子鏈域lChild和右孩子鏈域rChild。與單鏈表帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)的兩種情況相似，二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)也有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種

五、二叉樹(shù)的操作

python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的建立實(shí)例

python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的遍歷實(shí)例

python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的統(tǒng)計(jì)與轉(zhuǎn)換實(shí)例