第5章 樹與二叉樹

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

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

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

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

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

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

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

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

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