資源描述：
《數(shù)據(jù)結(jié)構(gòu) C語言版 教學課件 作者 嚴蔚敏 李冬梅 吳偉民 第5章 樹和二叉樹.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在應用文檔-天天文庫。
1、2021年8月4日北京林業(yè)大學信息學院李冬梅數(shù)據(jù)結(jié)構(gòu)2021年8月4日北京林業(yè)大學信息學院線性結(jié)構(gòu)——一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu)——一個對多個，如樹集合——數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關系圖形結(jié)構(gòu)——多個對多個，如圖邏輯結(jié)構(gòu)2021年8月4日北京林業(yè)大學信息學院第5章 樹和二叉樹5.1樹的定義和基本術(shù)語5.2二叉樹5.3遍歷二叉樹與線索二叉樹5.4樹和森林5.5霍夫曼樹及其應用2021年8月4日北京林業(yè)大學信息學院1.掌握二叉樹的基本概念、性質(zhì)和存儲結(jié)構(gòu)2.熟練掌握二叉樹的
2、前、中、后序遍歷方法3.了解線索化二叉樹的思想4.熟練掌握：霍夫曼樹的實現(xiàn)方法、構(gòu)造霍夫曼編碼的方法5.了解：森林與二叉樹的轉(zhuǎn)換，樹的遍歷方法教學目標2021年8月4日北京林業(yè)大學信息學院5.1樹的定義和基本術(shù)語樹是n個結(jié)點的有限集T1T2T32021年8月4日北京林業(yè)大學信息學院ADTTree{數(shù)據(jù)對象D:數(shù)據(jù)關系R:基本操作P：}ADTTree若D為空集，則稱為空樹；//允許n=0若D中僅含一個數(shù)據(jù)元素，則R為空集；其他情況下的R存在二元關系：①root唯一//關于根的說明②Dj∩Dk=Φ//
3、關于子樹不相交的說明③……//關于數(shù)據(jù)元素的說明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有15個樹的抽象數(shù)據(jù)類型定義2021年8月4日北京林業(yè)大學信息學院凹入表示嵌套集合廣義表樹的其它表示方式2021年8月4日北京林業(yè)大學信息學院根葉子森林有序樹無序樹——即根結(jié)點(沒有前驅(qū))——即終端結(jié)點(沒有后繼)——指m棵不相交的樹的集合(例如刪除A后的子樹個數(shù))——結(jié)點各子樹從左至右有序，不能互換（左為第一）——結(jié)點各子樹可互換位置?；拘g(shù)語2021年8月4日北京林業(yè)大學信息學院——即上層的那個結(jié)點(直接
4、前驅(qū))——即下層結(jié)點的子樹的根(直接后繼)——同一雙親下的同層結(jié)點（孩子之間互稱兄弟）——即雙親位于同一層的結(jié)點（但并非同一雙親）——即從根到該結(jié)點所經(jīng)分支的所有結(jié)點——即該結(jié)點下層子樹中的任一結(jié)點雙親孩子兄弟堂兄弟祖先子孫基本術(shù)語2021年8月4日北京林業(yè)大學信息學院——即樹的數(shù)據(jù)元素——結(jié)點掛接的子樹數(shù)結(jié)點結(jié)點的度結(jié)點的層次終端結(jié)點分支結(jié)點樹的度樹的深度(或高度)——從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）——即度為0的結(jié)點，即葉子——即度不為0的結(jié)點（也稱為內(nèi)部結(jié)點）——所有結(jié)點度中的最大值——
5、指所有結(jié)點中最大的層數(shù)層次1234基本術(shù)語2021年8月4日北京林業(yè)大學信息學院5.2二叉樹普通樹（多叉樹）若不轉(zhuǎn)化為二叉樹，則運算很難實現(xiàn)為何要重點研究每結(jié)點最多只有兩個“叉”的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；可以證明，所有樹都能轉(zhuǎn)為唯一對應的二叉樹，不失一般性。2021年8月4日北京林業(yè)大學信息學院二叉樹基本特點：結(jié)點的度小于等于2有序樹（子樹有序，不能顛倒）二叉樹的五種不同形態(tài)2021年8月4日北京林業(yè)大學信息學院具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？普通樹呢？練習5種/2種2021年
6、8月4日北京林業(yè)大學信息學院ADTBinaryTree{數(shù)據(jù)對象D:數(shù)據(jù)關系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關系：①root唯一//關于根的說明②Dj∩Dk=Φ//關于子樹不相交的說明③……//關于數(shù)據(jù)元素的說明④……//關于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有20個二叉樹的抽象數(shù)據(jù)類型定義2021年8月4日北京林業(yè)大學信息學院性質(zhì)1:在二叉樹的第i層上至多有2i-1個結(jié)點二叉樹的性質(zhì)提問：第i層上至少有個
7、結(jié)點？性質(zhì)2:深度為k的二叉樹至多有2k-1個結(jié)點提問：深度為k時至少有個結(jié)點？1k2021年8月4日北京林業(yè)大學信息學院性質(zhì)3:對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)n0必定為n2＋1（即n0=n2+1）2021年8月4日北京林業(yè)大學信息學院滿二叉樹：一棵深度為k且有2k-1個結(jié)點的二叉樹。（特點：每層都“充滿”了結(jié)點）特殊形態(tài)的二叉樹完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應只有最后一層葉子不滿，且全部集中在
8、左邊2021年8月4日北京林業(yè)大學信息學院滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前n-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點。滿二叉樹是完全二叉樹的一個特例。滿二叉樹和完全二叉樹的區(qū)別2021年8月4日北京林業(yè)大學信息學院一棵完全二叉樹有5000個結(jié)點，可以計算出其葉結(jié)點的個數(shù)是（）。練習25002021年8月4日北京林業(yè)大學信息學院性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度必為[log2n]＋1k層nk-1層2021年8月4日北京林業(yè)大學信息學院性質(zhì)5:對完全二叉
