一、樹的定義

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

二、二叉樹的定義

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

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

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

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

二叉樹的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
順序存儲(chǔ)：結(jié)構(gòu)采用一維數(shù)組存儲(chǔ)的。根據(jù)二叉樹的性質(zhì)6可計(jì)算出雙親結(jié)點(diǎn)、左右孩子結(jié)點(diǎn)的下標(biāo)。因此滿二叉樹、完全二叉樹的存儲(chǔ)可采用一維數(shù)組，把結(jié)點(diǎn)按從上到下、從左到右的順序存放在數(shù)組中，結(jié)點(diǎn)之間的關(guān)系可由性質(zhì)6的公式計(jì)算得到。
鏈?zhǔn)酱鎯?chǔ)：結(jié)構(gòu)采用鏈表存儲(chǔ)二叉樹中的數(shù)據(jù)元素，用鏈建立二叉樹中結(jié)點(diǎn)之間的關(guān)系。二叉樹最常用的鏈?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)的二叉樹也有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種

五、二叉樹的操作

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

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

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

最新評(píng)論