一、樹的定義

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

二、二叉樹的定義

二叉樹是由n（n≥0）個結(jié)點(diǎn)組成的有限集合、每個結(jié)點(diǎn)最多有兩個子樹的有序樹。它或者是空集，或者是由一個根和稱為左、右子樹的兩個不相交的二叉樹組成。
特點(diǎn)：
（1）二叉樹是有序樹，即使只有一個子樹，也必須區(qū)分左、右子樹；
（2）二叉樹的每個結(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層上最多有個結(jié)點(diǎn)。
性質(zhì)2：深度為h的二叉樹上最多有-1個結(jié)點(diǎn)。
性質(zhì)3：具有n個結(jié)點(diǎn)的二叉樹的高度不小于的最大整數(shù)。
性質(zhì)4：任意一棵二叉樹中，如果葉子結(jié)點(diǎn)的個數(shù)為n0，度為2的結(jié)點(diǎn)的個數(shù)為n2，則必然有n0＝n2＋1。
滿二叉樹：若深度為h的二叉樹，恰好具有-1個結(jié)點(diǎn)，則稱為滿二叉樹。
完全二叉樹：若一棵具有n個結(jié)點(diǎn)的二叉樹的邏輯結(jié)構(gòu)與滿二叉樹的前n個結(jié)點(diǎn)的邏輯結(jié)構(gòu)完全相同，則稱該二叉樹為完全二叉樹
擴(kuò)充二叉樹：除葉子結(jié)點(diǎn)外，其余結(jié)點(diǎn)都必須有兩個孩子的二叉樹。

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

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

五、二叉樹的操作