20.二叉樹的基本概念以及設(shè)計(jì)類

1、算法分析與設(shè)計(jì)（JAVA版）講師：牛牧樹與二叉樹概念設(shè)計(jì)二叉樹類 Lesson20樹與二叉樹的基本概念二叉樹類設(shè)計(jì)樹的概念樹是由n（n0）個(gè)結(jié)點(diǎn)構(gòu)成的滿足以下條件的結(jié)點(diǎn)集合：（1）當(dāng)n0時(shí)，有一個(gè)特殊的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)；（2）當(dāng)n1時(shí)，除根結(jié)點(diǎn)外的其他結(jié)點(diǎn)被分成m（m0）個(gè)互不相交的集合T1, T2, Tm，其中每一個(gè)集合Ti（1im）本身又是一棵結(jié)構(gòu)和樹結(jié)構(gòu)類同的子樹。樹的概念只有根結(jié)點(diǎn)的樹 一般的樹 樹的基本概念結(jié)點(diǎn)：結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。 結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。 葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，葉結(jié)點(diǎn)也稱作終端結(jié)點(diǎn)。

2、分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，分支結(jié)點(diǎn)也稱 作非終端結(jié)點(diǎn)。 孩子結(jié)點(diǎn)：樹中一個(gè)結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱作這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)。 樹的基本概念雙親結(jié)點(diǎn)：若樹中某結(jié)點(diǎn)有孩子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)就稱作它的孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。 兄弟結(jié)點(diǎn)：具有相同的雙親結(jié)點(diǎn)的結(jié)點(diǎn)稱為兄弟結(jié)點(diǎn)。 樹的度：樹中所有結(jié)點(diǎn)的度的最大值稱為該樹的度。 結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)到樹中某結(jié)點(diǎn)所經(jīng)路徑上的分支數(shù)。樹的基本概念樹的深度：樹中所有結(jié)點(diǎn)的層次的最大值稱為該樹的深度。 無(wú)序樹：樹中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)的排列沒(méi)有嚴(yán)格次序的樹稱為無(wú)序樹。 有序樹：樹中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)的排列有嚴(yán)格次序的樹稱為有序樹。 森林：m（m0）棵樹的集

3、合稱為森林。 樹的抽象數(shù)據(jù)類型 數(shù)據(jù)集合 ：樹的結(jié)點(diǎn)集合，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。 操作集合： （1）雙親結(jié)點(diǎn)parent() （2）左孩子結(jié)點(diǎn)leftChild() （3）右兄弟結(jié)點(diǎn)rightSibling() （4）遍歷樹traverse(vs) 樹的存儲(chǔ)結(jié)構(gòu)雙親表示法 雙親表示法就是用指針表示出每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)。 對(duì)于使用仿真指針的雙親表示法來(lái)說(shuō)，每個(gè)結(jié)點(diǎn)應(yīng)有兩個(gè)域，一個(gè)是數(shù)據(jù)元素域，另一個(gè)是指示其雙親結(jié)點(diǎn)在數(shù)組中下標(biāo)序號(hào)的仿真指針域。樹的存儲(chǔ)結(jié)構(gòu)樹及其使用仿真指針的雙親表示法 樹的存儲(chǔ)結(jié)構(gòu)孩子表示法 孩子表示法就是用指針表示出每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)。常規(guī)指針的

4、孩子表示法樹的存儲(chǔ)結(jié)構(gòu)雙親孩子表示法 雙親孩子表示法就是用指針既表示出每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)，也表示出每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)。樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法 孩子兄弟表示法就是用指針既表示出每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，也表示出每個(gè)結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。二叉樹二叉樹的定義 二叉樹是n（n0）個(gè)結(jié)點(diǎn)構(gòu)成的、每個(gè)結(jié)點(diǎn)最多只有兩個(gè)子樹的有序樹。 滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在同一層上。 完全二叉樹：如果一棵具有n個(gè)結(jié)點(diǎn)的二叉樹的邏輯結(jié)構(gòu)與滿二叉樹的前n個(gè)結(jié)點(diǎn)的邏輯結(jié)構(gòu)相同。二叉樹兩棵不同的二叉樹二叉樹滿二叉樹和完全二叉樹 二叉樹抽象數(shù)據(jù)類型數(shù)據(jù)集合：二叉樹的結(jié)點(diǎn)

5、集合，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。操作集合： （1）雙親結(jié)點(diǎn)parent()： （2）左孩子結(jié)點(diǎn)leftChild() （3）右孩子結(jié)點(diǎn)rightSibling() （4）左插入結(jié)點(diǎn)insertLeftNode(x) （5）右插入結(jié)點(diǎn)insertRightNode(x)： （6）左刪除子樹deleteLeftTree() （7）右刪除子樹deleteRightTree() （8）遍歷二叉樹traverse(vs)二叉樹的性質(zhì) 性質(zhì)1 若規(guī)定根結(jié)點(diǎn)的層次為0，則一棵非空二叉樹的第i層上最多有2i（i0）個(gè)結(jié)點(diǎn)。 性質(zhì)2 若規(guī)定空二叉樹樹的深度為-1(即根結(jié)點(diǎn)的深度為0)，

6、則深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)是2k+1-1（k-1）個(gè)。 性質(zhì)3 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為不超過(guò)log2(n+1)-1的最大整數(shù)。 性質(zhì)4 對(duì)于一棵非空的二叉樹，如果葉結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有n0= n2+1。二叉樹的性質(zhì)性質(zhì)5 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下和從左至右的順序?qū)λ薪Y(jié)點(diǎn)從0開始順序編號(hào)，則對(duì)于序號(hào)為i的結(jié)點(diǎn)，有： （1）如果i0，則序號(hào)為i結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為 (i-1)/2（“/”表示整除）；如果i=0，則序號(hào)為i結(jié)點(diǎn)為根結(jié)點(diǎn)，無(wú)雙親結(jié)點(diǎn)。 （2）如果2i+1n，則序號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i+1；如果2i+1n，則序號(hào)為i結(jié)點(diǎn)無(wú)左孩子結(jié)點(diǎn)。 （3）如果2i+2n，則序號(hào)為i結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i+2；如果2i+2n，則序號(hào)為i結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)。二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu) 非完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下圖二叉樹的存儲(chǔ)結(jié)構(gòu) 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用指針建立二叉樹中結(jié)點(diǎn)之間的關(guān)系。 二叉鏈存儲(chǔ)結(jié)構(gòu)的每個(gè)結(jié)點(diǎn)包含三個(gè)域 。leftChilddatarightChild二叉樹的存儲(chǔ)結(jié)構(gòu)二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹（