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

1、算法分析與設(shè)計(jì)（JAVA版）講師：牛牧樹(shù)與二叉樹(shù)概念設(shè)計(jì)二叉樹(shù)類 Lesson20樹(shù)與二叉樹(shù)的基本概念二叉樹(shù)類設(shè)計(jì)樹(shù)的概念樹(shù)是由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)和樹(shù)結(jié)構(gòu)類同的子樹(shù)。樹(shù)的概念只有根結(jié)點(diǎn)的樹(shù) 一般的樹(shù) 樹(shù)的基本概念結(jié)點(diǎn)：結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。 結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(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)：樹(shù)中一個(gè)結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)稱作這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)。 樹(shù)的基本概念雙親結(jié)點(diǎn)：若樹(shù)中某結(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)。 樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值稱為該樹(shù)的度。 結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)到樹(shù)中某結(jié)點(diǎn)所經(jīng)路徑上的分支數(shù)。樹(shù)的基本概念樹(shù)的深度：樹(shù)中所有結(jié)點(diǎn)的層次的最大值稱為該樹(shù)的深度。 無(wú)序樹(shù)：樹(shù)中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)的排列沒(méi)有嚴(yán)格次序的樹(shù)稱為無(wú)序樹(shù)。 有序樹(shù)：樹(shù)中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)的排列有嚴(yán)格次序的樹(shù)稱為有序樹(shù)。 森林：m（m0）棵樹(shù)的集

3、合稱為森林。 樹(shù)的抽象數(shù)據(jù)類型 數(shù)據(jù)集合 ：樹(shù)的結(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）遍歷樹(shù)traverse(vs) 樹(shù)的存儲(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)的仿真指針域。樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)及其使用仿真指針的雙親表示法 樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子表示法 孩子表示法就是用指針表示出每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)。常規(guī)指針的

4、孩子表示法樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親孩子表示法 雙親孩子表示法就是用指針既表示出每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)，也表示出每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)。樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法 孩子兄弟表示法就是用指針既表示出每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，也表示出每個(gè)結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。二叉樹(shù)二叉樹(shù)的定義 二叉樹(shù)是n（n0）個(gè)結(jié)點(diǎn)構(gòu)成的、每個(gè)結(jié)點(diǎn)最多只有兩個(gè)子樹(shù)的有序樹(shù)。 滿二叉樹(shù)：在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上。 完全二叉樹(shù)：如果一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的邏輯結(jié)構(gòu)與滿二叉樹(shù)的前n個(gè)結(jié)點(diǎn)的邏輯結(jié)構(gòu)相同。二叉樹(shù)兩棵不同的二叉樹(shù)二叉樹(shù)滿二叉樹(shù)和完全二叉樹(shù) 二叉樹(shù)抽象數(shù)據(jù)類型數(shù)據(jù)集合：二叉樹(shù)的結(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）左刪除子樹(shù)deleteLeftTree() （7）右刪除子樹(shù)deleteRightTree() （8）遍歷二叉樹(shù)traverse(vs)二叉樹(shù)的性質(zhì) 性質(zhì)1 若規(guī)定根結(jié)點(diǎn)的層次為0，則一棵非空二叉樹(shù)的第i層上最多有2i（i0）個(gè)結(jié)點(diǎn)。 性質(zhì)2 若規(guī)定空二叉樹(shù)樹(shù)的深度為-1(即根結(jié)點(diǎn)的深度為0)，

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