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