樹和二叉樹講解課件

1、第7講 樹和二叉樹7.1 樹7.2 二叉樹7.3 二叉樹的設(shè)計(jì)7.4 線索二叉樹7.5樹與二叉樹的轉(zhuǎn)換本章主要知識點(diǎn)：樹的定義、表示方法和存儲結(jié)構(gòu)二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)，滿二叉樹和完全二叉樹的概念二叉樹的前序、中序、后序和層序遍歷算法二叉樹中序和層序游標(biāo)類的設(shè)計(jì)方法線索二叉樹的基本概念哈夫曼樹和哈夫曼編碼，哈夫曼編碼的軟件設(shè)計(jì)方法樹與二叉樹的轉(zhuǎn)換，樹的遍歷7.1 樹7.1.1 樹的定義樹是由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)沒有前驅(qū)結(jié)點(diǎn)；（2）當(dāng)n1時(shí)，除根結(jié)點(diǎn)外的其他結(jié)點(diǎn)被分成m（m0）個(gè)互不相交的集合T1, T2, Tm，

2、其中每一個(gè)集合Ti（1im）本身又是一棵結(jié)構(gòu)和樹結(jié)構(gòu)類同的子樹。A只有根結(jié)點(diǎn)的樹ABCDEFGHIJKLM有子樹的樹根子樹樹的表示法樹的基本術(shù)語結(jié)點(diǎn)表示樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹的分支結(jié)點(diǎn)的度結(jié)點(diǎn)擁有的子樹數(shù)葉子度為0的結(jié)點(diǎn)，也叫終端結(jié)點(diǎn)分支結(jié)點(diǎn)度不為0的結(jié)點(diǎn)，也叫非終端結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)除根結(jié)點(diǎn)之外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn) 樹的基本術(shù)語樹的度一棵樹中最大的結(jié)點(diǎn)度數(shù)孩子結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子雙親孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親兄弟同一雙親的孩子之間互成為兄弟祖先結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)子孫以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都成為該結(jié)點(diǎn)的子孫樹的基本術(shù)語結(jié)點(diǎn)的層次從根

3、結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層堂兄弟其雙親在同一層的結(jié)點(diǎn)互稱為堂兄弟。深度樹中結(jié)點(diǎn)的最大層次數(shù)有序樹 如果將樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的（即不能互換），則稱該樹為有序樹，否則稱為無序樹。在有序樹中最左邊的子樹的根稱為第一個(gè)孩子，最右邊的稱為最后一個(gè)孩子。森林m(m0)棵互不相交的樹的集合ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)

4、點(diǎn)F，G的祖先7.1.2 樹的表示方法1 直觀表示法2 形式化表示法 樹的形式化表示法主要用于樹的理論描述。樹的形式化表示法定義樹T為T=（D，R）其中D為樹T中結(jié)點(diǎn)的集合，R為樹T中結(jié)點(diǎn)之間關(guān)系的集合。當(dāng)樹T為空樹時(shí)D=；當(dāng)樹T不為空樹時(shí)有D=RootDF，其中Root為樹T的根結(jié)點(diǎn)，DF為樹T的根Root的子樹集合，DF可由下式表示： DF = D1D2Dm （1i, jm, DiDj=）7.1.3 樹的基本操作 （1）雙親結(jié)點(diǎn)parent() （2）左孩子結(jié)點(diǎn)leftChild() （3）右兄弟結(jié)點(diǎn)rightSibling() （4）遍歷樹traverse(vs) 7.1.4 樹的存儲結(jié)

5、構(gòu) 1 雙親表示法 雙親表示法就是用指針表示出每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)。 對于使用仿真指針的雙親表示法來說，每個(gè)結(jié)點(diǎn)應(yīng)有兩個(gè)域，一個(gè)是數(shù)據(jù)元素域，另一個(gè)是指示其雙親結(jié)點(diǎn)在數(shù)組中下標(biāo)序號的仿真指針域。樹及其使用仿真指針的雙親表示法 2 孩子表示法孩子表示法就是用指針表示出每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)。常規(guī)指針的孩子表示法3 雙親孩子表示法 雙親孩子表示法就是用指針既表示出每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)，也表示出每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)。4 孩子兄弟表示法 由于每個(gè)結(jié)點(diǎn)的孩子數(shù)可以變化很大并且事先不知道，建立到各個(gè)孩子結(jié)點(diǎn)的鏈接不可行class TreeNode Object element; TreeNode firstChil

6、d; /第一個(gè)孩子 TreeNode nextSibling; /下一個(gè)兄弟4 孩子兄弟表示法 孩子兄弟表示法就是用指針既表示出每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，也表示出每個(gè)結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。7.9 樹的遍歷及應(yīng)用樹的用法之一就是許多操作系統(tǒng)中的目錄結(jié)構(gòu)如果要列出目錄中所有文件的名字，輸出格式是：層次為di的文件將在di次跳格（tab）縮進(jìn)后打印其名private void listAll(int depth) printName(depth); /Print the name of the object; if(isDeirectory() for each file c in this directory

7、 (for each child) c.listAll(depth+1);public void listAll()listAll(0);1 先根遍歷 樹的先根遍歷遞歸算法為：（1）訪問根結(jié)點(diǎn)；（2）按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每一棵子樹。在每個(gè)結(jié)點(diǎn)上的工作量是常數(shù)。如果有N個(gè)文件名需要輸出，則運(yùn)行時(shí)間就是O(N)2 后根遍歷 樹的后根遍歷遞歸算法為：（1）按照從左到右的次序后根遍歷根結(jié)點(diǎn)的每一棵子樹；（2）訪問根結(jié)點(diǎn)。例如：計(jì)算文件系統(tǒng)某目錄下所有文件占用的磁盤區(qū)塊的總數(shù)（由于目錄也是文件，也有大?。﹑ublic int size() int totalSize=sizeOfThisF

8、ile(); if(isDirectory() for each file c in this directory(for each child) totalSize+=c.size(); return totalSize();先根遍歷得到的結(jié)點(diǎn)序列為：A B E J F C G K L D H I后根遍歷得到的結(jié)點(diǎn)序列為：J E F B K L G C H I D AABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO一般樹的遍歷（續(xù)）7.2二叉樹的定義及特點(diǎn)定義： 二叉樹是結(jié)點(diǎn)的有限集合，這個(gè)

9、集合或者是空的，或者由一個(gè)根結(jié)點(diǎn)或兩棵互不相交的稱為左子樹的和右子樹的二叉樹組成。 特點(diǎn)：1）每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn))2）二叉樹的子樹有左、右之分，且其次序不能任意顛倒二叉樹的五種基本形態(tài)滿二叉樹定義：一顆深度為k的滿二叉樹，是由k 個(gè)結(jié)點(diǎn)的深度為K的二叉樹。k -個(gè)結(jié)點(diǎn)是二叉樹所具有的最大結(jié)點(diǎn)個(gè)數(shù)。為從第一層的結(jié)點(diǎn)（即根）便于訪問滿二叉樹的結(jié)點(diǎn)，對滿二叉樹開始，自上而下，從左到右，按順序給結(jié)點(diǎn)編號，便得到滿二叉樹的一個(gè)順序表。 完全二叉樹定義：一顆具有n個(gè)結(jié)點(diǎn)、深度為K的二叉樹，當(dāng)且僅當(dāng)其所有結(jié)點(diǎn)對應(yīng)于深度為k的滿二叉樹中編號由1到n的那些結(jié)點(diǎn)時(shí)，該二叉樹便是完全二叉

10、樹。12311458912136710141512311458912671012345671234567.2.2 二叉樹的基本操作 （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) 7.2.3 二叉樹的性質(zhì) 性質(zhì)1 若規(guī)定根結(jié)點(diǎn)的層次為0，則一棵非空二叉樹的第i層上最多有2i（

11、i0）個(gè)結(jié)點(diǎn)。 性質(zhì)2 若規(guī)定空二叉樹樹的深度為-1(即根結(jié)點(diǎn)的深度為0)，則深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)是2k+1-1（k-1）個(gè)。 性質(zhì)3 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為不超過log2(n+1)-1的最大整數(shù)。 性質(zhì)4 對于一棵非空的二叉樹，如果葉結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有n0= n2+1。 性質(zhì)5 對于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下和從左至右的順序?qū)λ薪Y(jié)點(diǎn)從0開始順序編號，則對于序號為i的結(jié)點(diǎn)，有： （1）如果i0，則序號為i結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號為 (i-1)/2（“/”表示整除）；如果i=0，則序號為i結(jié)點(diǎn)為根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。 （2）如果2i+1n，

12、則序號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號為2i+1；如果2i+1n，則序號為i結(jié)點(diǎn)無左孩子結(jié)點(diǎn)。 （3）如果2i+2BDCD L RL D RBL D RL D RADCL D R中序遍歷序列：B D A C中序遍歷: L R DL R DL R DADCL R D后序遍歷序列： D B C A后序遍歷:B二叉樹的遍歷練習(xí)先根次序遍歷：1,2,4,8,9,5,10,11,3,6,12,7中根次序遍歷：8,4,9,2,10,5,11,1,12,6,3,7后根次序遍歷：8,9,4,10,11,5,2,12,6,7,3,1 除前序、中序和后序遍歷算法外，二叉樹還有層序遍歷。層序遍歷的要求是：按二叉樹的層序次

13、序（即從根結(jié)點(diǎn)層至葉結(jié)點(diǎn)層），同一層中按先左子樹再右子樹的次序遍歷二叉樹。二叉樹的層序遍歷算法如下：（1）初始化設(shè)置一個(gè)隊(duì)列；（2）把根結(jié)點(diǎn)指針入隊(duì)列；（3）當(dāng)隊(duì)列非空時(shí)，循環(huán)執(zhí)行步驟（3.a）到步驟（3.c）； （3.a）出隊(duì)列取得當(dāng)前隊(duì)頭結(jié)點(diǎn)，訪問該結(jié)點(diǎn)； （3.b）若該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)非空，則將該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)指針入隊(duì)列； （3.c）若該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)非空，則將該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)指針入隊(duì)列；（4）結(jié)束。7.3.3 二叉樹遍歷的應(yīng)用 1 打印二叉樹 2 查找數(shù)據(jù)元素7.3.4 應(yīng)用舉例表達(dá)式樹：葉子是操作數(shù)，其他結(jié)點(diǎn)為操作符，只考慮操作是二元的情況+ab*c *g*fde中序遍歷的結(jié)果

14、是中綴表達(dá)式；后序遍歷的結(jié)果是后綴表達(dá)式構(gòu)造表達(dá)式樹 把后綴表達(dá)式變成表達(dá)式樹，方法類似后綴求值算法：一次一個(gè)符號地讀入表達(dá)式，如果是操作數(shù)，那么就建立一個(gè)單節(jié)點(diǎn)樹并將它入棧，如果是操作符，那么就沖棧中彈出兩棵樹T1和T2并形成一棵新樹，該樹的根就是操作符，然后將這棵新樹入棧例如：ab+cde+*7.3.5 非遞歸的二叉樹遍歷算法 非遞歸的二叉樹前序遍歷算法如下：（1）初始化設(shè)置一個(gè)堆棧；（2）把根結(jié)點(diǎn)指針入棧；（3）當(dāng)堆棧非空時(shí)，循環(huán)執(zhí)行步驟（3.a）到步驟（3.c）； （3.a）出棧取得棧頂結(jié)點(diǎn)，訪問該結(jié)點(diǎn)； （3.b）若該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)非空，則將該結(jié)點(diǎn)的右孩子 結(jié)點(diǎn)指針入棧； （3.c

15、）若該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)非空，則將該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)指針入棧；（4）結(jié)束。 對于上圖所示的二叉樹，非遞歸的二叉樹前序遍歷算法的執(zhí)行過程 如下頁圖所示：中根序遍歷的非遞歸算法ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問：C(4)pABCDEFGiP-A訪問：C B(5)ABCDEFGiP-AP-D訪問：C Bp(6)ABCDEFGiP-AP-DP-E訪問：C Bp(7)ABCDEFGiP-AP-D訪問：C B Ep(8)ABCDEFGiP-AP-DP-G訪問：C B EP=NULL(9)AB

16、CDEFGiP-A訪問：C B E G Dp(11)ABCDEFGiP-AP-F訪問：C B E G Dp(12)ABCDEFGiP-AP-D訪問：C B E Gp(10)ABCDEFGiP-A訪問：C B E G D Fp=NULL(13)ABCDEFGi訪問：C B E G D F Ap(14)ABCDEFGi訪問：C B E G D F Ap=NULL(15)7.4 線索二叉樹 把結(jié)點(diǎn)中指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針稱為線索。在二叉樹的結(jié)點(diǎn)上加上線索的二叉樹稱作線索二叉樹。對二叉樹以某種方法（如前序、中序或后序方法）遍歷使其變?yōu)榫€索二叉樹的過程稱作按該方法對二叉樹進(jìn)行的線索化。 二叉樹中序線索二叉樹前序線索二叉樹 后序線索二叉樹7.5 樹與二叉樹的轉(zhuǎn)換1 樹轉(zhuǎn)換為二叉樹 樹轉(zhuǎn)換為二叉樹的方法是： （1）樹中所有相同雙親結(jié)點(diǎn)的兄弟結(jié)點(diǎn)之間加一條連線。 （2）對樹中不是雙親結(jié)點(diǎn)第一個(gè)孩子的結(jié)點(diǎn)，只保留新添加的該