數(shù)據(jù)結(jié)構(gòu)章節(jié)程內(nèi)容ppt課件

1、數(shù)據(jù)構(gòu)造課程的內(nèi)容數(shù)據(jù)構(gòu)造課程的內(nèi)容第第6章章 樹和二叉樹樹和二叉樹 Tree & Binary Tree 6.1 樹的根本概念樹的根本概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其運用赫夫曼樹及其運用特點：非線性構(gòu)造，一個直接前驅(qū)，但能夠有多個特點：非線性構(gòu)造，一個直接前驅(qū)，但能夠有多個直接后繼直接后繼1 1：n n6.1 樹的根本概念樹的根本概念1. 樹的定義樹的定義2. 假設(shè)干術(shù)語假設(shè)干術(shù)語3. 邏輯構(gòu)造邏輯構(gòu)造4.存儲構(gòu)造存儲構(gòu)造5. 樹的運算樹的運算1. 樹的定義樹的定義注注1：過去許多書籍中都定義樹為

2、：過去許多書籍中都定義樹為n1，曾經(jīng)有，曾經(jīng)有“空樹不是空樹不是樹的說法，但如今樹的定義已修正。樹的說法，但如今樹的定義已修正。注注2：樹的定義具有遞歸性，即樹中還有樹。：樹的定義具有遞歸性，即樹中還有樹。由一個或多個由一個或多個(n0)(n0)結(jié)點組成的有限集合結(jié)點組成的有限集合T T，有，有且僅有一個結(jié)點稱為根且僅有一個結(jié)點稱為根rootroot，當，當n1n1時，其他的時，其他的結(jié)點分為結(jié)點分為m(m0)m(m0)個互不相交的有限集合個互不相交的有限集合T1,T2T1,T2，TmTm。每個集合本身又是棵樹，被稱作這個根的子樹。每個集合本身又是棵樹，被稱作這個根的子樹 。樹的表示法有幾種：

3、樹的表示法有幾種：圖形表示法圖形表示法嵌套集合表示法嵌套集合表示法廣義表表示法廣義表表示法目錄表示法目錄表示法左孩子右兄弟表示法左孩子右兄弟表示法這些表示法的表示圖這些表示法的表示圖參見教材參見教材P120P120樹的籠統(tǒng)數(shù)據(jù)類型定義參見教材樹的籠統(tǒng)數(shù)據(jù)類型定義參見教材P118-119圖形表示法：圖形表示法：教師教師學生學生其他人員其他人員20002000級級 20192019級級 20192019級級20192019級級太原科技大學太原科技大學經(jīng)管經(jīng)管應(yīng)科應(yīng)科外語外語葉子葉子根根子樹子樹廣義表表示法廣義表表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H

4、 ( M ), I, J ) ) 根作為由子樹森林組成的表的名字寫在表的左邊根作為由子樹森林組成的表的名字寫在表的左邊左孩子右兄弟表示法左孩子右兄弟表示法數(shù)據(jù)數(shù)據(jù)左孩子左孩子 右兄弟( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 樹的籠統(tǒng)數(shù)據(jù)類型定義樹的籠統(tǒng)數(shù)據(jù)類型定義見教材見教材P118-119P118-119ADT Tree數(shù)據(jù)對象數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R:根本操作根本操作 P：ADT Tree假設(shè)假設(shè)D為空集，那么稱為空樹；為空集，那么稱為空樹；/允許允許n=0假設(shè)假設(shè)D中僅含一個數(shù)據(jù)元素，那么中僅含一個數(shù)據(jù)元

5、素，那么R為空集；為空集；其他情況下的其他情況下的R存在二元關(guān)系：存在二元關(guān)系： root 獨一獨一 /關(guān)于根的闡明關(guān)于根的闡明 DjDk= /關(guān)于子樹不相交的闡明關(guān)于子樹不相交的闡明 /關(guān)于數(shù)據(jù)元素的闡明關(guān)于數(shù)據(jù)元素的闡明D是具有一樣特性的數(shù)據(jù)元素的集合。是具有一樣特性的數(shù)據(jù)元素的集合。/至少有至少有15個個2. 假設(shè)干術(shù)語假設(shè)干術(shù)語即上層的那個結(jié)點即上層的那個結(jié)點(直接前驅(qū)直接前驅(qū))即下層結(jié)點的子樹的根即下層結(jié)點的子樹的根(直接后繼直接后繼)同一雙親下的同層結(jié)點孩子之間互稱兄弟同一雙親下的同層結(jié)點孩子之間互稱兄弟即雙親位于同一層的結(jié)點但并非同一雙親即雙親位于同一層的結(jié)點但并非同一雙親即從根

6、到該結(jié)點所經(jīng)分支的一切結(jié)點即從根到該結(jié)點所經(jīng)分支的一切結(jié)點即該結(jié)點下層子樹中的任一結(jié)點即該結(jié)點下層子樹中的任一結(jié)點ABCGEIDHFJMLK 根根 葉子葉子 森林森林有序樹有序樹無序樹無序樹即根結(jié)點即根結(jié)點(沒有前驅(qū)沒有前驅(qū))即終端結(jié)點即終端結(jié)點(沒有后繼沒有后繼)指指m棵不相交的樹的集棵不相交的樹的集合合(例如刪除例如刪除A后的子樹個數(shù)后的子樹個數(shù))雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孫子孫結(jié)點各子樹從左至右有序，不能互換左為第一結(jié)點各子樹從左至右有序，不能互換左為第一結(jié)點各子樹可互換位置。結(jié)點各子樹可互換位置。2. 假設(shè)干術(shù)語續(xù)假設(shè)干術(shù)語續(xù)即樹的數(shù)據(jù)元素即樹的數(shù)據(jù)元素結(jié)點掛接的子

7、樹數(shù)結(jié)點掛接的子樹數(shù)有幾個直接后繼就是有幾個直接后繼就是幾度，亦稱幾度，亦稱“次數(shù)次數(shù)結(jié)點結(jié)點結(jié)點的度結(jié)點的度結(jié)點的層次結(jié)點的層次終端結(jié)點終端結(jié)點分支結(jié)點分支結(jié)點樹的度樹的度樹的深度樹的深度(或高度或高度)ABCGEIDHFJMLK從根到該結(jié)點的層數(shù)根結(jié)點算第一層從根到該結(jié)點的層數(shù)根結(jié)點算第一層即度為即度為0的結(jié)點，即葉子的結(jié)點，即葉子即度不為即度不為0的結(jié)點也稱為內(nèi)部結(jié)點的結(jié)點也稱為內(nèi)部結(jié)點一切結(jié)點度中的最大值一切結(jié)點度中的最大值Max各結(jié)點的度各結(jié)點的度指一切結(jié)點中最大的層數(shù)指一切結(jié)點中最大的層數(shù)Max各結(jié)點的層次各結(jié)點的層次問：右上圖中的結(jié)點數(shù)問：右上圖中的結(jié)點數(shù) ；樹的度；樹的度 ；樹

8、的深度；樹的深度13133 34 43. 樹的邏輯構(gòu)造樹的邏輯構(gòu)造 ( (特點特點) )： 一對多一對多1:n1:n，有多個直接后繼如家譜，有多個直接后繼如家譜樹、目錄樹等等，但只需一個根結(jié)點，樹、目錄樹等等，但只需一個根結(jié)點，且子樹之間互不相交。且子樹之間互不相交。 4. 樹的存儲構(gòu)造樹的存儲構(gòu)造 討論討論1：樹是非線性構(gòu)造，該怎樣存儲？：樹是非線性構(gòu)造，該怎樣存儲？依然有順序存儲、鏈式存儲等方式。依然有順序存儲、鏈式存儲等方式。 討論討論3：樹的鏈式存儲方案應(yīng)該怎樣制定？：樹的鏈式存儲方案應(yīng)該怎樣制定？可規(guī)定為：從上至下、從左至右將樹的結(jié)點依次存入內(nèi)存?？梢?guī)定為：從上至下、從左至右將樹的結(jié)

9、點依次存入內(nèi)存。艱苦缺陷：復原困難不能獨一復原就沒有適用價值。艱苦缺陷：復原困難不能獨一復原就沒有適用價值。討論討論2：樹的順序存儲方案應(yīng)該怎樣制定？：樹的順序存儲方案應(yīng)該怎樣制定？可用多重鏈表：一個前趨指針，可用多重鏈表：一個前趨指針，n n個后繼指針。個后繼指針。細節(jié)問題：樹中結(jié)點的構(gòu)造類型款式該如何設(shè)計？細節(jié)問題：樹中結(jié)點的構(gòu)造類型款式該如何設(shè)計？ 即應(yīng)該設(shè)計成即應(yīng)該設(shè)計成“等長還是等長還是“不等長？不等長？缺陷：等長構(gòu)造太浪費每個結(jié)點的度不一定一樣；缺陷：等長構(gòu)造太浪費每個結(jié)點的度不一定一樣； 不等長構(gòu)造太復雜要定義好多種構(gòu)造類型。不等長構(gòu)造太復雜要定義好多種構(gòu)造類型。處理思緒：先研討

10、最簡單、最有規(guī)律的樹，然后設(shè)法把處理思緒：先研討最簡單、最有規(guī)律的樹，然后設(shè)法把普通的樹轉(zhuǎn)化為簡單樹。普通的樹轉(zhuǎn)化為簡單樹。5. 樹的運算樹的運算 要明確：要明確：1. 普通樹即多叉樹假設(shè)不轉(zhuǎn)化為二叉樹，那普通樹即多叉樹假設(shè)不轉(zhuǎn)化為二叉樹，那么運算很難實現(xiàn)。么運算很難實現(xiàn)。2. 二叉樹的運算依然是插入、刪除、修正、查找、二叉樹的運算依然是插入、刪除、修正、查找、排序等，但這些操作必需建立在對樹結(jié)點可以排序等，但這些操作必需建立在對樹結(jié)點可以“遍歷的根底上！遍歷的根底上！遍歷遍歷指每個結(jié)點都被訪問且僅訪問一次，指每個結(jié)點都被訪問且僅訪問一次，不脫漏不反復。不脫漏不反復。本章重點：二叉樹的表示和實

11、現(xiàn)本章重點：二叉樹的表示和實現(xiàn)6.2 6.2 二叉樹二叉樹為何要重點研討每結(jié)點最多只需兩個為何要重點研討每結(jié)點最多只需兩個 “叉叉 的樹？的樹？二叉樹的構(gòu)造最簡單，規(guī)律性最強；二叉樹的構(gòu)造最簡單，規(guī)律性最強；可以證明，一切樹都能轉(zhuǎn)為獨一對應(yīng)的二叉樹，不失普通性?？梢宰C明，一切樹都能轉(zhuǎn)為獨一對應(yīng)的二叉樹，不失普通性。1. 二叉樹的定義二叉樹的定義2. 二叉樹的性質(zhì)二叉樹的性質(zhì)3. 二叉樹的存儲構(gòu)造二叉樹的存儲構(gòu)造二叉樹的運算見二叉樹的運算見6.3節(jié)節(jié)定義：是定義：是nn0個結(jié)點的有限集合，由一個根結(jié)點以及兩個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成棵互不

12、相交的、分別稱為左子樹和右子樹的二叉樹組成 。邏輯構(gòu)造：邏輯構(gòu)造： 一對二一對二1：2 根本特征根本特征: 每個結(jié)點最多只需兩棵子樹不存在度大于每個結(jié)點最多只需兩棵子樹不存在度大于2的結(jié)點；的結(jié)點； 左子樹和右子樹次序不能顛倒有序樹。左子樹和右子樹次序不能顛倒有序樹。根本形狀：根本形狀： 5種種/2種種二叉樹的籠統(tǒng)數(shù)據(jù)類型定義見教材二叉樹的籠統(tǒng)數(shù)據(jù)類型定義見教材P121-122P121-122ADT BinaryTree數(shù)據(jù)對象數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R:根本操作根本操作 P：ADT BinaryTree假設(shè)假設(shè)D=，那么，那么R= ；假設(shè)假設(shè)D，那么，那么R= H；存在二元關(guān)系：；存在二

13、元關(guān)系： root 獨一獨一 /關(guān)于根的闡明關(guān)于根的闡明 DjDk= /關(guān)于子樹不相交的闡明關(guān)于子樹不相交的闡明 /關(guān)于數(shù)據(jù)元素的闡明關(guān)于數(shù)據(jù)元素的闡明 /關(guān)于左子樹和右子樹的闡明關(guān)于左子樹和右子樹的闡明D是具有一樣特性的數(shù)據(jù)元素的集合。是具有一樣特性的數(shù)據(jù)元素的集合。/至少有至少有20個個討論討論1 1：第：第i i層的結(jié)點數(shù)至多是多少？層的結(jié)點數(shù)至多是多少？ 利用二進制性質(zhì)可輕利用二進制性質(zhì)可輕松求出松求出 性質(zhì)性質(zhì)1: 1: 在二叉樹的第在二叉樹的第i i層上至多有層上至多有2i-12i-1個結(jié)點個結(jié)點i0i0。性質(zhì)性質(zhì)2: 2: 深度為深度為k k的二叉樹至多有的二叉樹至多有2k-12

14、k-1個結(jié)點個結(jié)點k0k0。2i-12i-1個個討論討論2 2：深度為：深度為k k的二叉樹，至多有多少個結(jié)點？的二叉樹，至多有多少個結(jié)點？ 利用二進制性質(zhì)可利用二進制性質(zhì)可輕松求出輕松求出2k-12k-1討論討論3 3：二叉樹的葉子數(shù)和度為：二叉樹的葉子數(shù)和度為2 2的結(jié)點數(shù)之間有關(guān)系嗎？的結(jié)點數(shù)之間有關(guān)系嗎？性質(zhì)性質(zhì)3: 3: 對于任何一棵二叉樹，假設(shè)對于任何一棵二叉樹，假設(shè)2 2度的結(jié)點數(shù)有度的結(jié)點數(shù)有n2n2個，那么葉子數(shù)個，那么葉子數(shù)n0n0必定為必定為n2n21 1 即即n0=n2+1n0=n2+1ABCGEIDHFJ對于兩種特殊方式的二叉樹滿二叉樹和完全二叉樹，對于兩種特殊方式的

15、二叉樹滿二叉樹和完全二叉樹，還特別具備以下還特別具備以下2 2個性質(zhì)：個性質(zhì)：性質(zhì)性質(zhì)4: 4: 具有具有n n個結(jié)點的完全二叉樹的深度必為個結(jié)點的完全二叉樹的深度必為log2nlog2n1 1性質(zhì)性質(zhì)5: 5: 對完全二叉樹，假設(shè)從上至下、從左至右編對完全二叉樹，假設(shè)從上至下、從左至右編號，那么編號為號，那么編號為i i 的結(jié)點，其左孩子編號必為的結(jié)點，其左孩子編號必為2i2i，其右孩子編號必為其右孩子編號必為2i2i1 1；其雙親的編號必為；其雙親的編號必為i/2i/2i i1 1 時為根時為根, ,除外。除外。 證明：根據(jù)性質(zhì)證明：根據(jù)性質(zhì)2 2，深度為，深度為k k的二叉樹最多只需的二

16、叉樹最多只需2k-12k-1個結(jié)點，且完全二叉樹個結(jié)點，且完全二叉樹的定義是與同深度的滿二叉樹前面編號一樣，即它的總結(jié)點數(shù)的定義是與同深度的滿二叉樹前面編號一樣，即它的總結(jié)點數(shù)n n位于位于k k層和層和k-1k-1層滿二叉樹容量之間，即層滿二叉樹容量之間，即 2k-1-1n2k-1 2k-1-1n2k-1 或或2k-1n2k2k-1n2k三邊同時取對數(shù)，于是有：三邊同時取對數(shù)，于是有：k-1log2nk k-1log2nk 由于由于k k是整數(shù)，所以是整數(shù)，所以k=log2n+1k=log2n+1可根據(jù)歸納法證明?？筛鶕?jù)歸納法證明。滿二叉樹：一棵深度為滿二叉樹：一棵深度為k k 且有且有2k

17、 -12k -1個結(jié)點的二叉樹。個結(jié)點的二叉樹。 特點：每層都特點：每層都“充溢了結(jié)點充溢了結(jié)點完全二叉樹：深度為完全二叉樹：深度為k k 的，有的，有n n個結(jié)點個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與的二叉樹，當且僅當其每一個結(jié)點都與深度為深度為k k 的滿二叉樹中編號從的滿二叉樹中編號從1 1至至n n的結(jié)的結(jié)點一一對應(yīng)。點一一對應(yīng)。AOBCGEKDJFIHNML深度為深度為4 4的滿二叉樹的滿二叉樹深度為深度為4 4的完全二叉樹的完全二叉樹ABCGEIDHFJ為何要研討這兩種特殊方式？為何要研討這兩種特殊方式？由于它們在順序存儲方式下可以復原！由于它們在順序存儲方式下可以復原！ 解釋：

18、完全二叉樹的特點就是，只需最后解釋：完全二叉樹的特點就是，只需最后一層葉子不滿，且全部集中在左邊。一層葉子不滿，且全部集中在左邊。 3. 3. 深度為深度為9 9的二叉樹中至少有的二叉樹中至少有 個結(jié)點。個結(jié)點。 ) )9 9 ) )8 8 ) ) ) )9 91 12.2.深度為深度為k k 的二叉樹的結(jié)點總數(shù)，最多為的二叉樹的結(jié)點總數(shù)，最多為 個。個。 ) )k-1 k-1 ) log2k ) log2k ) ) k k ) )k k課堂練習：課堂練習：1. 1. 樹中各結(jié)點的度的最大值稱為樹的樹中各結(jié)點的度的最大值稱為樹的 。 ) ) 高度高度 ) ) 層次層次 ) ) 深度深度 ) )

19、 度度課堂討論：課堂討論： 二叉樹是不是樹的特殊情況？二叉樹是不是樹的特殊情況？答：不是！雖然二叉樹也屬于一種樹構(gòu)造，但它是另外單獨定答：不是！雖然二叉樹也屬于一種樹構(gòu)造，但它是另外單獨定義的一種樹，并非普通樹的特例。它的子樹有順序規(guī)定，分為義的一種樹，并非普通樹的特例。它的子樹有順序規(guī)定，分為左子樹和右子樹。不能隨意顛倒。左子樹和右子樹。不能隨意顛倒。：滿二叉樹和完全二叉樹有什么區(qū)別？：滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前n-n-1 1層是滿的，但最底層卻允許在右邊短少延續(xù)假設(shè)干個結(jié)點。層是滿

20、的，但最底層卻允許在右邊短少延續(xù)假設(shè)干個結(jié)點。滿二叉樹是完全二叉樹的一個特例。滿二叉樹是完全二叉樹的一個特例。課堂討論：課堂討論：Q1Q1：滿二叉樹和完全二叉樹有什么區(qū)別？：滿二叉樹和完全二叉樹有什么區(qū)別？A1A1：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前n-n-1 1層是滿的，但最底層卻允許在右邊短少延續(xù)假設(shè)干個結(jié)點。層是滿的，但最底層卻允許在右邊短少延續(xù)假設(shè)干個結(jié)點。 滿二叉樹是完全二叉樹的一個特例。滿二叉樹是完全二叉樹的一個特例。Q3: Q3: 設(shè)一棵完全二叉樹具有設(shè)一棵完全二叉樹具有10001000個結(jié)點，那么它有個結(jié)點，那么它

21、有 個個葉子結(jié)點，有葉子結(jié)點，有 個度為個度為2 2的結(jié)點，有的結(jié)點，有 個結(jié)點只需非空左個結(jié)點只需非空左子樹，有子樹，有 個結(jié)點只需非空右子樹。個結(jié)點只需非空右子樹。4894894884881 10 0Q2Q2：為什么要研討滿二叉樹和完全二叉樹這兩種特殊方式？：為什么要研討滿二叉樹和完全二叉樹這兩種特殊方式？A1A1：由于只需這兩種方式可以實現(xiàn)順序存儲?。河捎谥恍柽@兩種方式可以實現(xiàn)順序存儲！由于最后一層葉子數(shù)為由于最后一層葉子數(shù)為489489個，是奇數(shù)，闡明有個，是奇數(shù)，闡明有1 1個結(jié)點只需非空個結(jié)點只需非空左子樹；而完全二叉樹中不能夠出現(xiàn)非空右子樹左子樹；而完全二叉樹中不能夠出現(xiàn)非空右子

22、樹(0(0個個) )。A3A3：易求出總層數(shù)和末層葉子數(shù)?？倢訑?shù)：易求出總層數(shù)和末層葉子數(shù)?？倢訑?shù)k=k=log2nlog2n 1 =10;1 =10;且前且前9 9層總結(jié)點數(shù)為層總結(jié)點數(shù)為29-1=511 (29-1=511 (完全二叉樹的前完全二叉樹的前k-1k-1層一定是層一定是滿的滿的) )所以末層葉子數(shù)為所以末層葉子數(shù)為1000-511=4891000-511=489個。個。請留意葉子結(jié)點總數(shù)請留意葉子結(jié)點總數(shù)末層葉子數(shù)！末層葉子數(shù)！還該當加上第還該當加上第k-1k-1層靠右邊的層靠右邊的0 0度結(jié)點個數(shù)。度結(jié)點個數(shù)。分析：末層的分析：末層的489489個葉子只占據(jù)了上層的個葉子只占

23、據(jù)了上層的245245個結(jié)點個結(jié)點489/2489/2 ) )上層上層k=9)k=9)右邊的右邊的0 0度結(jié)點數(shù)還有度結(jié)點數(shù)還有29-1-245=1129-1-245=11個！個！ 另一法：可先求另一法：可先求2 2度結(jié)點數(shù)度結(jié)點數(shù), ,再由此得到葉子總數(shù)。再由此得到葉子總數(shù)。首先，首先，k-2k-2層的層的28-128-1255255個結(jié)點一定都是個結(jié)點一定都是2 2度的完全二叉度的完全二叉另外，末層葉子剛剛已求出為另外，末層葉子剛剛已求出為489489所對應(yīng)的雙親也是度所對應(yīng)的雙親也是度2 2， 共有共有489/2489/2 244244個。個。所以，全部所以，全部2 2度結(jié)點數(shù)為度結(jié)點數(shù)為255(k-2255(k-2層層) )244(k-1244(k-1層層)=499)=499個；個；總?cè)~子數(shù)總?cè)~子數(shù)2 2度結(jié)點數(shù)度結(jié)點數(shù)1=5001=500個。個。第第i i層上的滿層上的滿結(jié)點數(shù)為結(jié)點數(shù)為2i-12i-1所以，所以，全部葉子數(shù)全部葉子數(shù)489(489(末層末層) )11(k-111(k-1層層)=500)=500個。個。 度為度為2 2的結(jié)點葉子總數(shù)的結(jié)點葉子總數(shù)1=4991=499個。個。4. 4. 二叉樹的存儲構(gòu)造二叉樹的存儲構(gòu)造一、順序存儲構(gòu)造一、順序存儲構(gòu)造按二叉樹的結(jié)