第5章 樹(shù)與二叉樹(shù)

《第5章 樹(shù)與二叉樹(shù)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第5章樹(shù)與二叉樹(shù)5.1樹(shù)的基本概念5.2二叉樹(shù)及其基本概念5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)5.4遍歷二叉樹(shù)*5.5樹(shù)的存儲(chǔ)結(jié)構(gòu)5.6森林與二叉樹(shù)的轉(zhuǎn)換5.7赫夫曼樹(shù)及其應(yīng)用第5章樹(shù)與二叉數(shù)第頁(yè)2007-7-29第5章樹(shù)與二叉樹(shù)5.1樹(shù)的基本概念樹(shù)(tree)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性，如圖5-1所示。在樹(shù)的圖形表示中，通常用一個(gè)圓圈表示一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的名字寫(xiě)在圓圈內(nèi)或是圓圈旁邊，以區(qū)別于其他的結(jié)點(diǎn)并規(guī)定在用直線連起來(lái)的兩端結(jié)點(diǎn)中，總是認(rèn)為上端結(jié)點(diǎn)是前件，下端結(jié)點(diǎn)是后件

2、。樹(shù)這種數(shù)據(jù)結(jié)構(gòu)在客觀世界中大量存在，例如行政組織機(jī)構(gòu)、家譜等都可用樹(shù)形象表示。……第1層……第2層……第3層……第4層圖5-1樹(shù)的圖形表示ACDBEFGHIJMKL第5章樹(shù)與二叉數(shù)第頁(yè)2007-7-291.樹(shù)的定義樹(shù)（Tree）是n(n≥0)個(gè)結(jié)點(diǎn)的有限集T。當(dāng)n=0時(shí)，稱為空樹(shù)；當(dāng)n＞0時(shí)，該集合滿足如下條件：①有且僅有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)；②其余的結(jié)點(diǎn)可分為m（m≥0）個(gè)互不相交的子集T1，T2，...，Tm，其中每個(gè)子集本身又是一棵樹(shù)，并稱其為根的子樹(shù)（SubTree）。例如，圖5-1是一棵具

3、有13個(gè)結(jié)點(diǎn)的樹(shù)，其中A是根，余下的12個(gè)結(jié)點(diǎn)分成3個(gè)互不相交的子集：T1={B，E，F(xiàn)，G，K，L}，T2={C，H}，T3={D，I，J，M}。T1、T2、T3都是樹(shù)，而且是根結(jié)點(diǎn)A的子樹(shù)。第5章樹(shù)與二叉數(shù)第頁(yè)2007-7-292.樹(shù)的基本術(shù)語(yǔ)1）結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)稱為該結(jié)點(diǎn)的度。2）樹(shù)的度：樹(shù)的所有結(jié)點(diǎn)中的最大的度稱為樹(shù)的度。3）葉子：樹(shù)中度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)，簡(jiǎn)稱葉子。4）分支結(jié)點(diǎn)：樹(shù)中度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。5）雙親和孩子：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子，相應(yīng)地，該結(jié)

4、點(diǎn)稱為孩子的雙親。第5章樹(shù)與二叉數(shù)第頁(yè)2007-7-296）結(jié)點(diǎn)的層：規(guī)定樹(shù)的根結(jié)點(diǎn)的層（Level）為１，其余任一結(jié)點(diǎn)的層等于它的雙親的層加１。7）樹(shù)的深度：樹(shù)中各結(jié)點(diǎn)的層的最大值稱為樹(shù)的深度（Depth）或高度。８）兄弟和堂兄弟：同一雙親的孩子之間互稱為兄弟（Sibling）。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。9）祖先和子孫：一個(gè)結(jié)點(diǎn)的祖先是指從該結(jié)點(diǎn)到樹(shù)的根所經(jīng)分支上的所有結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的子樹(shù)上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫。10）有序樹(shù)和無(wú)序樹(shù)：如果樹(shù)中任一結(jié)點(diǎn)的各棵子樹(shù)規(guī)定從左至右是有次序的，即不能互換位置，則

5、稱該樹(shù)為有序樹(shù)，否則稱為無(wú)序樹(shù)（如圖5-3所示）。第5章樹(shù)與二叉數(shù)第頁(yè)2007-7-2911）森林：n（n≥0）棵互不相交的樹(shù)的集合稱為森林。刪去一棵樹(shù)的根結(jié)點(diǎn)便得到一個(gè)森林。圖5-3兩棵不同的有序樹(shù)ABCDBDAC5.2二叉樹(shù)及其基本性質(zhì)1.二叉樹(shù)的定義第5章樹(shù)與二叉數(shù)第頁(yè)2007-7-29二叉樹(shù)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集，它或者是空集（n=0），或者是由一個(gè)根結(jié)點(diǎn)和兩棵互不相交且分別稱為根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。這是二叉樹(shù)的遞歸定義。二叉樹(shù)共有５種基本形態(tài)，如圖5-4所示(a)(b)(c)(d)(e)圖

6、5-4二叉樹(shù)的五種基本形態(tài)(a)空二叉樹(shù)(b)僅有根結(jié)點(diǎn)的二叉樹(shù)(c)右子樹(shù)為空的二叉樹(shù)(d)左子樹(shù)為空的二叉樹(shù)(e)左、右子樹(shù)非空的二叉樹(shù)AABABABC第5章樹(shù)與二叉數(shù)第頁(yè)2007-7-292.二叉樹(shù)的基本性質(zhì)性質(zhì)１:在二叉樹(shù)的第i層上,最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）性質(zhì)２:深度為k的二叉樹(shù)最多有2k-1個(gè)結(jié)點(diǎn)。顯然將第1至第i層的最多結(jié)點(diǎn)數(shù)相加，即可得到此結(jié)果20+21+……+2k-1=2k-1性質(zhì)３：在任意一棵二叉樹(shù)中，若度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。設(shè)n1為二

7、叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)，n為二叉樹(shù)的總結(jié)點(diǎn)數(shù)，因?yàn)閚=n1+2n2+1=n0+n1+n2可得n0=n2+1第5章樹(shù)與二叉數(shù)第頁(yè)2007-7-29滿二叉樹(shù)：一棵深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉數(shù)。（對(duì)滿二叉樹(shù)的結(jié)點(diǎn)進(jìn)行順序編號(hào)，約定編號(hào)從根結(jié)點(diǎn)起，自上而下，同層的結(jié)點(diǎn)從左至右）完全二叉樹(shù)：深度為K，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)。（完全二叉樹(shù)除最后一層外，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，在最后一層上可能缺少右邊的若干結(jié)點(diǎn)。顯然滿二叉樹(shù)是完全二叉樹(shù)）。非完全二

8、叉樹(shù)：除完全二叉樹(shù)外的其它二叉樹(shù)。第5章樹(shù)與二叉數(shù)第頁(yè)2007-7-29在圖5-5中，(a)為滿而叉樹(shù)(b)為完全二叉樹(shù)(c)為非完全二叉樹(shù)。(a)滿二叉樹(shù)(b)完全二叉樹(shù)(c)非完全二叉樹(shù)圖5-5特殊形態(tài)的二叉樹(shù)123456123568741234567第5章樹(shù)與二叉數(shù)第頁(yè)2007-7-29性質(zhì)４：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為?log2n?+1。其中?