數(shù)據(jù)結(jié)構(gòu)-王紅梅-第5章樹和二叉樹ppt課件

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社樹的邏輯構(gòu)造樹的邏輯構(gòu)造樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造二叉樹的存儲(chǔ)構(gòu)造及實(shí)現(xiàn)二叉樹的存儲(chǔ)構(gòu)造及實(shí)現(xiàn)二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換哈夫曼樹和哈夫曼編碼哈夫曼樹和哈夫曼編碼第第 5 章章 樹和二叉樹樹和二叉樹本章的主要內(nèi)容是本章的主要內(nèi)容是數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社樹的定義樹的定義樹：樹：n nn0n0個(gè)結(jié)點(diǎn)的有限集合。當(dāng)個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n n0 0時(shí)，稱為時(shí)，稱為空樹；恣意一棵非空樹滿足以下條件

2、：空樹；恣意一棵非空樹滿足以下條件： 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)； 當(dāng)當(dāng)n n1 1時(shí)，除根結(jié)點(diǎn)之外的其他結(jié)點(diǎn)被分成時(shí)，除根結(jié)點(diǎn)之外的其他結(jié)點(diǎn)被分成m mm0m0個(gè)互不相交的有限集合個(gè)互不相交的有限集合T1,T2, ,TmT1,T2, ,Tm，其中，其中每個(gè)集合又是一棵樹，并稱為這個(gè)根結(jié)點(diǎn)的子樹。每個(gè)集合又是一棵樹，并稱為這個(gè)根結(jié)點(diǎn)的子樹。5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造樹的定義是采用遞歸方法樹的定義是采用遞歸方法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社(a) 一棵樹構(gòu)造一棵樹構(gòu)造 (b)一個(gè)非樹構(gòu)造一個(gè)非樹構(gòu)造 (c)一個(gè)非樹

3、構(gòu)造一個(gè)非樹構(gòu)造 5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造樹的定義樹的定義ACBGFEDHIACBGFDACBGFDE數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社樹的運(yùn)用舉例樹的運(yùn)用舉例文件構(gòu)造文件構(gòu)造5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社樹的根本術(shù)語樹的根本術(shù)語p 結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。p 樹的度：樹中各結(jié)點(diǎn)度的最大值。樹的度：樹中各結(jié)點(diǎn)度的最大值。5.1 樹的邏

4、輯構(gòu)造樹的邏輯構(gòu)造CGBDEFKLHMIJA數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造p 葉子結(jié)點(diǎn)：度為葉子結(jié)點(diǎn)：度為0 0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。p 分支結(jié)點(diǎn)：度不為分支結(jié)點(diǎn)：度不為0 0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。CGBDEFKLHMIJA樹的根本術(shù)語樹的根本術(shù)語數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社p 孩子、雙親：樹中某結(jié)點(diǎn)子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩孩子、雙親：樹中某結(jié)點(diǎn)子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；子結(jié)點(diǎn)，

5、這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；p 兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。 5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造CGBDEFKLHMIJA樹的根本術(shù)語樹的根本術(shù)語數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社p 途徑：假設(shè)樹的結(jié)點(diǎn)序列途徑：假設(shè)樹的結(jié)點(diǎn)序列n1, n2, , nk有如下關(guān)系：結(jié)點(diǎn)有如下關(guān)系：結(jié)點(diǎn)ni是是ni+1的雙親的雙親1=ik，那么把，那么把n1, n2, , nk稱為一條由稱為一條由n1至至nk的途徑；的途徑；p 途徑上經(jīng)過的邊的個(gè)數(shù)稱為途徑長度。途徑上經(jīng)過的邊的個(gè)數(shù)稱為途徑長度。 CGBDEFKLHMI

6、JA5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造樹的根本術(shù)語樹的根本術(shù)語數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社祖先、子孫：在樹中，假設(shè)有一條途徑從結(jié)點(diǎn)祖先、子孫：在樹中，假設(shè)有一條途徑從結(jié)點(diǎn)x x到結(jié)點(diǎn)到結(jié)點(diǎn)y y，那，那么么x x稱為稱為y y的祖先，而的祖先，而y y稱為稱為x x的子孫。的子孫。5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造CGBDEFKLHMIJA樹的根本術(shù)語樹的根本術(shù)語數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社p 結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1 1；對(duì)其他任何結(jié)點(diǎn)，假設(shè)某；對(duì)其他任何結(jié)點(diǎn)，假設(shè)某結(jié)點(diǎn)在第結(jié)點(diǎn)

7、在第k k層，那么其孩子結(jié)點(diǎn)在第層，那么其孩子結(jié)點(diǎn)在第k+1k+1層。層。p 樹的深度：樹中一切結(jié)點(diǎn)的最大層數(shù)，也稱高度。樹的深度：樹中一切結(jié)點(diǎn)的最大層數(shù)，也稱高度。1 1層層2層層4 4層層3層層高度高度4CGBDEFKLHMIJC5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造樹的根本術(shù)語樹的根本術(shù)語數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社CBDEFKLHJA71234568910層序編號(hào)：將樹中結(jié)點(diǎn)按照從上層到下層、同層從左到右的層序編號(hào)：將樹中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從次序依次給他們編以從1 1開場(chǎng)的延續(xù)自然數(shù)。開場(chǎng)的延續(xù)自然數(shù)。5.1 樹的

8、邏輯構(gòu)造樹的邏輯構(gòu)造樹的根本術(shù)語樹的根本術(shù)語數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社有序樹、無序樹：假設(shè)一棵樹中結(jié)點(diǎn)的各子樹從左到右是有有序樹、無序樹：假設(shè)一棵樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)構(gòu)造中討論的普通都是有序樹數(shù)據(jù)構(gòu)造中討論的普通都是有序樹 5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造樹的根本術(shù)語樹的根本術(shù)語ACBGFEDACBGFED數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社CBDEFKLHJ森林：森林：m (m0)棵互不相交的樹的集合。任何一棵樹刪去

9、棵互不相交的樹的集合。任何一棵樹刪去根結(jié)點(diǎn)就變成了森林。根結(jié)點(diǎn)就變成了森林。 5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造樹的根本術(shù)語樹的根本術(shù)語A數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社樹構(gòu)造和線性構(gòu)造的比較樹構(gòu)造和線性構(gòu)造的比較第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素根結(jié)點(diǎn)只需一個(gè)根結(jié)點(diǎn)只需一個(gè)無前驅(qū)無前驅(qū)無雙親無雙親最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)(可以有多個(gè)可以有多個(gè))無后繼無后繼無孩子無孩子其它數(shù)據(jù)元素其它數(shù)據(jù)元素其它結(jié)點(diǎn)其它結(jié)點(diǎn)一個(gè)前驅(qū)一個(gè)前驅(qū),一個(gè)后繼一個(gè)后繼一個(gè)雙親一個(gè)雙親,多個(gè)孩子多個(gè)孩子5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）

10、第2版版清華大學(xué)出版社清華大學(xué)出版社樹的籠統(tǒng)數(shù)據(jù)類型定義樹的籠統(tǒng)數(shù)據(jù)類型定義ADT TreeData 樹是由一個(gè)根結(jié)點(diǎn)和假設(shè)干棵子樹構(gòu)成，樹是由一個(gè)根結(jié)點(diǎn)和假設(shè)干棵子樹構(gòu)成， 樹中結(jié)點(diǎn)具有一樣數(shù)據(jù)類型及層次關(guān)系樹中結(jié)點(diǎn)具有一樣數(shù)據(jù)類型及層次關(guān)系Operation5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造樹的運(yùn)用很廣泛，在不同的實(shí)踐運(yùn)用中，樹的根本操作不樹的運(yùn)用很廣泛，在不同的實(shí)踐運(yùn)用中，樹的根本操作不盡一樣。下面給出一個(gè)樹的籠統(tǒng)數(shù)據(jù)類型定義的例子，簡盡一樣。下面給出一個(gè)樹的籠統(tǒng)數(shù)據(jù)類型定義的例子，簡單起見，根本操作只包含樹的遍歷，針對(duì)詳細(xì)運(yùn)用，需求單起見，根本操作只包含樹的遍歷，針對(duì)詳細(xì)運(yùn)用，需求重新定

11、義其根本操作。重新定義其根本操作。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社InitTree 前置條件：樹不存在前置條件：樹不存在 輸入：無輸入：無 功能：初始化一棵樹功能：初始化一棵樹 輸出：無輸出：無 后置條件：構(gòu)造一個(gè)空樹后置條件：構(gòu)造一個(gè)空樹DestroyTree 前置條件：樹已存在前置條件：樹已存在 輸入：無輸入：無 功能：銷毀一棵樹功能：銷毀一棵樹 輸出：無輸出：無 后置條件：釋放該樹占用的存儲(chǔ)空間后置條件：釋放該樹占用的存儲(chǔ)空間 樹的籠統(tǒng)數(shù)據(jù)類型定義樹的籠統(tǒng)數(shù)據(jù)類型定義5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出

12、版社清華大學(xué)出版社 PreOrder 前置條件：樹已存在前置條件：樹已存在 輸入：無輸入：無 功能：前序遍歷樹功能：前序遍歷樹 輸出：樹的前序遍歷序列輸出：樹的前序遍歷序列 后置條件：樹堅(jiān)持不變后置條件：樹堅(jiān)持不變 PostOrder 前置條件：樹已存在前置條件：樹已存在 輸入：無輸入：無 功能：后序遍歷樹功能：后序遍歷樹 輸出：樹的后序遍歷序列輸出：樹的后序遍歷序列 后置條件：樹堅(jiān)持不變后置條件：樹堅(jiān)持不變endADT樹的籠統(tǒng)數(shù)據(jù)類型定義樹的籠統(tǒng)數(shù)據(jù)類型定義5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社樹的遍歷操作樹的遍歷操作 樹的遍歷

13、：從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問樹中一切結(jié)點(diǎn)，樹的遍歷：從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問樹中一切結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。 如何了解訪問如何了解訪問? ?籠統(tǒng)操作，可以是對(duì)結(jié)點(diǎn)進(jìn)展的各種處置，這里簡化為輸出籠統(tǒng)操作，可以是對(duì)結(jié)點(diǎn)進(jìn)展的各種處置，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)。結(jié)點(diǎn)的數(shù)據(jù)。如何了解次序如何了解次序? ?樹通常有前序根遍歷、后序根遍歷和層序次樹通常有前序根遍歷、后序根遍歷和層序次遍歷三種方式。遍歷三種方式。5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造樹構(gòu)造非線性構(gòu)造樹構(gòu)造非線性構(gòu)造線性構(gòu)造。線性構(gòu)造。遍歷的本質(zhì)遍歷的本質(zhì)? ?數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（

14、C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社前序遍歷前序遍歷 樹的前序遍歷操作定義為：樹的前序遍歷操作定義為：假設(shè)樹為空，那么空操作前假設(shè)樹為空，那么空操作前往；否那么往；否那么 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 按照從左到右的順序前序按照從左到右的順序前序遍歷根結(jié)點(diǎn)的每一棵子樹。遍歷根結(jié)點(diǎn)的每一棵子樹。 5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造前序遍歷序列：前序遍歷序列：A B D E H I F C GACBGFEDHI數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社后序遍歷后序遍歷 樹的后序遍歷操作定義為：樹的后序遍歷操作定義為：假設(shè)樹為空，那么空操作前假設(shè)樹為空，那么空操作

15、前往；否那么往；否那么 按照從左到右的順序后序按照從左到右的順序后序遍歷根結(jié)點(diǎn)的每一棵子樹；遍歷根結(jié)點(diǎn)的每一棵子樹； 訪問根結(jié)點(diǎn)。訪問根結(jié)點(diǎn)。 5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)造后序遍歷序列：后序遍歷序列：D H I E F B G C AACBGFEDHI數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社層序遍歷層序遍歷 樹的層序遍歷操作定義為：樹的層序遍歷操作定義為：從樹的第一層即根結(jié)點(diǎn)從樹的第一層即根結(jié)點(diǎn)開場(chǎng)，自上而下逐層遍歷，開場(chǎng)，自上而下逐層遍歷，在同一層中，按從左到右的在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。 5.1 樹的邏輯構(gòu)造樹的邏輯構(gòu)

16、造層序遍歷序列：層序遍歷序列：A B C D E F G H IACBGFEDHI數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造實(shí)現(xiàn)樹的存儲(chǔ)構(gòu)造，關(guān)鍵是什么實(shí)現(xiàn)樹的存儲(chǔ)構(gòu)造，關(guān)鍵是什么? ?什么是存儲(chǔ)構(gòu)造什么是存儲(chǔ)構(gòu)造? ?樹中結(jié)點(diǎn)之間的邏輯關(guān)系是什么樹中結(jié)點(diǎn)之間的邏輯關(guān)系是什么? ?思索問題的出發(fā)點(diǎn)：如何表示結(jié)點(diǎn)的雙親和孩子思索問題的出發(fā)點(diǎn)：如何表示結(jié)點(diǎn)的雙親和孩子如何表示樹中結(jié)點(diǎn)之間的邏輯關(guān)系。如何表示樹中結(jié)點(diǎn)之間的邏輯關(guān)系。數(shù)據(jù)元素以及數(shù)據(jù)元素之間的邏輯關(guān)系在存儲(chǔ)器數(shù)據(jù)元素以及數(shù)據(jù)元素之間的邏輯關(guān)系在存儲(chǔ)器中的表示。中的表示。數(shù)據(jù)結(jié)

17、構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社根本思想：用一維數(shù)組來存儲(chǔ)樹的各個(gè)結(jié)點(diǎn)普通根本思想：用一維數(shù)組來存儲(chǔ)樹的各個(gè)結(jié)點(diǎn)普通按層序存儲(chǔ)，數(shù)組中的一個(gè)元素對(duì)應(yīng)樹中的一個(gè)按層序存儲(chǔ)，數(shù)組中的一個(gè)元素對(duì)應(yīng)樹中的一個(gè)結(jié)點(diǎn)，包括結(jié)點(diǎn)的數(shù)據(jù)信息以及該結(jié)點(diǎn)的雙親在數(shù)結(jié)點(diǎn)，包括結(jié)點(diǎn)的數(shù)據(jù)信息以及該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)。組中的下標(biāo)。 5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造 data parentdata：存儲(chǔ)樹中結(jié)點(diǎn)的數(shù)據(jù)信息：存儲(chǔ)樹中結(jié)點(diǎn)的數(shù)據(jù)信息parent：存儲(chǔ)該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)：存儲(chǔ)該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出

18、版社template struct PNode DataType data; /數(shù)據(jù)域數(shù)據(jù)域 int parent; /指針域，雙親在數(shù)組中的下標(biāo)指針域，雙親在數(shù)組中的下標(biāo) ; data parent5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造樹的雙親表示法本質(zhì)上是一個(gè)靜態(tài)鏈表。樹的雙親表示法本質(zhì)上是一個(gè)靜態(tài)鏈表。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社下標(biāo)下標(biāo) data parent012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造如何查找雙親結(jié)點(diǎn)？時(shí)間性能？如何查找雙親結(jié)點(diǎn)？時(shí)間性能？ACBHFE

19、DGI數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造ACBHFEDGI如何查找孩子結(jié)點(diǎn)？時(shí)間性能？如何查找孩子結(jié)點(diǎn)？時(shí)間性能？下標(biāo)下標(biāo) data parentfirstchild 1 3 6 -1 8 -1-1-1-1012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 添加第一添加第一個(gè)孩子的域個(gè)孩子的域數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社下標(biāo)下標(biāo) data parent rightsib-1-1 2 2-1-1 4 4 5 5 -1-17 7-1-1-1-15.

20、2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 ACBHFEDGI如何查找兄弟結(jié)點(diǎn)？時(shí)間性能？如何查找兄弟結(jié)點(diǎn)？時(shí)間性能？添加右兄弟的域添加右兄弟的域數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。 如何表示孩子？如何表示孩子？5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造孩子鏈表表示法孩子鏈表表示法方案一：指針域的個(gè)數(shù)等于樹的度方案一：指針域的個(gè)數(shù)等于樹

21、的度data child1 child2 childd其中：其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息；：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息； child1childd：指針域，指向該結(jié)點(diǎn)的孩子。：指針域，指向該結(jié)點(diǎn)的孩子。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造缺陷：浪費(fèi)空間缺陷：浪費(fèi)空間ACBHFEDGIABCDEFGHI 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。每個(gè)指針域指向該

22、結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。 如何表示孩子？如何表示孩子？5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造孩子鏈表表示法孩子鏈表表示法方案二：方案二： 指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度 data degree child1 child2 childd其中：其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息；：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息； degree：度域，存放該結(jié)點(diǎn)的度；：度域，存放該結(jié)點(diǎn)的度； child1childd：指針域，指向該結(jié)點(diǎn)的孩子。：指針域，指向該結(jié)點(diǎn)的孩子。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造缺陷：結(jié)點(diǎn)構(gòu)造不一致缺

23、陷：結(jié)點(diǎn)構(gòu)造不一致ACBHFEDGIA 2B 3C 2E 1I 0G 0H 0F 0D 0數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社孩子鏈表表示法孩子鏈表表示法孩子鏈表的根本思想：把每個(gè)結(jié)點(diǎn)的孩子陳列起來，看成是孩子鏈表的根本思想：把每個(gè)結(jié)點(diǎn)的孩子陳列起來，看成是一個(gè)線性表，且以單鏈表存儲(chǔ)，那么一個(gè)線性表，且以單鏈表存儲(chǔ)，那么n個(gè)結(jié)點(diǎn)共有個(gè)結(jié)點(diǎn)共有 n 個(gè)孩子鏈個(gè)孩子鏈表。這表。這 n 個(gè)單鏈表共有個(gè)單鏈表共有 n 個(gè)頭指針，這個(gè)頭指針，這 n 個(gè)頭指針又組成了個(gè)頭指針又組成了一個(gè)線性表，為了便于進(jìn)展查找采用順序存儲(chǔ)。最后，將存一個(gè)線性表，為了便于進(jìn)展查找采用順序存

24、儲(chǔ)。最后，將存放放 n 個(gè)頭指針的數(shù)組和存放個(gè)頭指針的數(shù)組和存放n個(gè)結(jié)點(diǎn)的數(shù)組結(jié)合起來，構(gòu)成孩個(gè)結(jié)點(diǎn)的數(shù)組結(jié)合起來，構(gòu)成孩子鏈表的表頭數(shù)組。子鏈表的表頭數(shù)組。 5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造如何表示孩子？如何表示孩子？將結(jié)點(diǎn)的一切孩子放在一同，構(gòu)成線性表。將結(jié)點(diǎn)的一切孩子放在一同，構(gòu)成線性表。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社child next孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)struct CTNode int child; CTNode *next;5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造template struct CBNode DataType data; CTNode

25、*firstchild; ;孩子鏈表表示法孩子鏈表表示法data firstchild表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社ACBHFEDGI012345678下標(biāo)下標(biāo) data firstchild A B C D E F G H I 5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造如何查找孩子結(jié)點(diǎn)？時(shí)間性能？如何查找孩子結(jié)點(diǎn)？時(shí)間性能？12 345 7 68 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社ACBHFEDGI012345678下標(biāo)下標(biāo) data firstchild A B C D E F G H I 5.2 樹的存儲(chǔ)構(gòu)

26、造樹的存儲(chǔ)構(gòu)造12 345 7 68 如何查找雙親結(jié)點(diǎn)？時(shí)間性能？如何查找雙親結(jié)點(diǎn)？時(shí)間性能？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 data parent firstchild12 345 7 68 ACBHFEDGI數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造ACBHFEDGI某結(jié)點(diǎn)的第一個(gè)孩子是獨(dú)一的某結(jié)點(diǎn)的第一個(gè)孩子是獨(dú)一的某結(jié)點(diǎn)的右兄弟是獨(dú)一的某結(jié)點(diǎn)的右兄弟是獨(dú)一的設(shè)置兩個(gè)

27、分別指向該結(jié)點(diǎn)的設(shè)置兩個(gè)分別指向該結(jié)點(diǎn)的第一個(gè)孩子和右兄弟的指針第一個(gè)孩子和右兄弟的指針 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template struct TNode DataType data; TNode *firstchild, *rightsib;5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造結(jié)點(diǎn)構(gòu)造結(jié)點(diǎn)構(gòu)造firstchild data rightsibdata：數(shù)據(jù)域，存儲(chǔ)該結(jié)點(diǎn)的數(shù)據(jù)信息；：數(shù)據(jù)域，存儲(chǔ)該結(jié)點(diǎn)的數(shù)據(jù)信息；firstchild：指針域，指向該結(jié)點(diǎn)第一個(gè)孩子；：指針域，指向該結(jié)點(diǎn)第一個(gè)孩子；rightsib：指針域，指向該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)。：指針

28、域，指向該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造ACBHFEDGI A B C D E F G H I如何查找兄弟結(jié)點(diǎn)？時(shí)間性能？如何查找兄弟結(jié)點(diǎn)？時(shí)間性能？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.2 樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造ACBHFEDGI A B C D E F G H I如何查找孩子結(jié)點(diǎn)？時(shí)間性能？如何查找孩子結(jié)點(diǎn)？時(shí)間性能？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社二叉樹是二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集合，該集合或者為個(gè)結(jié)點(diǎn)的有限集合，該

29、集合或者為空集稱為空二叉樹，或者由一個(gè)根結(jié)點(diǎn)和兩棵空集稱為空二叉樹，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。二叉樹組成。5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造研討二叉樹的意義？研討二叉樹的意義？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社二叉樹的特點(diǎn)二叉樹的特點(diǎn) 每個(gè)結(jié)點(diǎn)最多有兩棵子樹；每個(gè)結(jié)點(diǎn)最多有兩棵子樹； 二叉樹是有序的，其次序不二叉樹是有序的，其次序不能恣意顛倒。能恣意顛倒。 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造留意：二叉樹和樹是兩種樹構(gòu)造。留意：二叉樹和樹是兩種樹構(gòu)造。A

30、BCDEFGABAB數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社二叉樹的根本形狀二叉樹的根本形狀空二叉樹空二叉樹只需一個(gè)根結(jié)點(diǎn)只需一個(gè)根結(jié)點(diǎn)左子樹左子樹根結(jié)點(diǎn)只需左子樹根結(jié)點(diǎn)只需左子樹右子樹右子樹根結(jié)點(diǎn)只需右子樹根結(jié)點(diǎn)只需右子樹左子樹左子樹右子樹右子樹根結(jié)點(diǎn)同時(shí)有左右子樹根結(jié)點(diǎn)同時(shí)有左右子樹5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造具有具有3 3個(gè)結(jié)點(diǎn)的樹和具有個(gè)結(jié)點(diǎn)的樹和具有3 3個(gè)結(jié)點(diǎn)的二叉樹的形狀個(gè)結(jié)點(diǎn)的二叉樹的形狀v二叉樹和樹是兩種樹構(gòu)造。二叉樹和樹是兩

31、種樹構(gòu)造。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社特殊的二叉樹特殊的二叉樹斜樹斜樹1 .一切結(jié)點(diǎn)都只需左一切結(jié)點(diǎn)都只需左子樹的二叉樹稱為左子樹的二叉樹稱為左斜樹；斜樹；2 .一切結(jié)點(diǎn)都只需右一切結(jié)點(diǎn)都只需右子樹的二叉樹稱為右子樹的二叉樹稱為右斜樹；斜樹；3.左斜樹和右斜樹統(tǒng)左斜樹和右斜樹統(tǒng)稱為斜樹。稱為斜樹。1. 在斜樹中，每一層只需一個(gè)結(jié)點(diǎn)；在斜樹中，每一層只需一個(gè)結(jié)點(diǎn)；2.斜樹的結(jié)點(diǎn)個(gè)數(shù)與其深度一樣。斜樹的結(jié)點(diǎn)個(gè)數(shù)與其深度一樣。 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造斜樹的特點(diǎn)：斜樹的特點(diǎn)：ABCABC數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社

32、清華大學(xué)出版社滿二叉樹滿二叉樹在一棵二叉樹中，假在一棵二叉樹中，假設(shè)一切分支結(jié)點(diǎn)都存設(shè)一切分支結(jié)點(diǎn)都存在左子樹和右子樹，在左子樹和右子樹，并且一切葉子都在同并且一切葉子都在同一層上。一層上。滿二叉樹的特點(diǎn)：滿二叉樹的特點(diǎn)： 葉子只能出如今最下一層；葉子只能出如今最下一層； 只需度為只需度為0和度為和度為2的結(jié)點(diǎn)。的結(jié)點(diǎn)。5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造特殊的二叉樹特殊的二叉樹CDEFGHIJKLM NO1112 13 14 15數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社滿二叉樹滿二叉樹5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造不是滿二

33、叉樹，雖然不是滿二叉樹，雖然一切分支結(jié)點(diǎn)都有左一切分支結(jié)點(diǎn)都有左右子樹，但葉子不在右子樹，但葉子不在同一層上。同一層上。滿二叉樹在同樣深度的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹在同樣深度的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)最多A1523467BCDEFGLM89特殊的二叉樹特殊的二叉樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社完全二叉樹完全二叉樹對(duì)一棵具有對(duì)一棵具有n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，二叉樹按層序編號(hào)，假設(shè)編號(hào)為假設(shè)編號(hào)為i1in的結(jié)點(diǎn)與同樣深度的的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為滿二叉樹

34、中編號(hào)為i的的結(jié)點(diǎn)在二叉樹中的位結(jié)點(diǎn)在二叉樹中的位置完全一樣。置完全一樣。5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造特殊的二叉樹特殊的二叉樹CDEFGHIJKLM NO1112 13 14 15CDEFGHIJ數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社在滿二叉樹中，從最后在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開場(chǎng)，延續(xù)去一個(gè)結(jié)點(diǎn)開場(chǎng)，延續(xù)去掉恣意個(gè)結(jié)點(diǎn)，即是一掉恣意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹?？猛耆鏄?。5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造A1523467910BCDEFGHIJK11L12M13N14O158A1523

35、4678910BCDEFGHIJ不是完全二叉樹，結(jié)點(diǎn)不是完全二叉樹，結(jié)點(diǎn)10與滿二叉樹中的結(jié)點(diǎn)與滿二叉樹中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)不是同一個(gè)結(jié)點(diǎn)特殊的二叉樹特殊的二叉樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社1. 葉子結(jié)點(diǎn)只能出如今最下兩層葉子結(jié)點(diǎn)只能出如今最下兩層且最下層的葉子結(jié)點(diǎn)都集中在二且最下層的葉子結(jié)點(diǎn)都集中在二叉樹的左面；叉樹的左面；2. 完全二叉樹中假設(shè)有度為完全二叉樹中假設(shè)有度為1的的結(jié)點(diǎn)，只能夠有一個(gè)，且該結(jié)點(diǎn)結(jié)點(diǎn)，只能夠有一個(gè)，且該結(jié)點(diǎn)只需左孩子。只需左孩子。3. 深度為深度為k的完全二叉樹在的完全二叉樹在k-1層層上一定是滿二叉樹。上一定是滿二

36、叉樹。4. 在同樣結(jié)點(diǎn)個(gè)數(shù)的二叉樹中，在同樣結(jié)點(diǎn)個(gè)數(shù)的二叉樹中，完全二叉樹的深度最小。完全二叉樹的深度最小。 完全二叉樹的特點(diǎn)完全二叉樹的特點(diǎn)5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造特殊的二叉樹特殊的二叉樹CDEFGHIJ數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社性質(zhì)性質(zhì)5-1 二叉樹的第二叉樹的第i層上最多有層上最多有2i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)i1。 證明：當(dāng)證明：當(dāng)i=1時(shí)，第時(shí)，第1層只需一個(gè)根結(jié)點(diǎn)，而層只需一個(gè)根結(jié)點(diǎn)，而 2i-1=20 =1，結(jié)論顯然成立。，結(jié)論顯然成立。假定假定i=k1ki時(shí)結(jié)論成立，即第時(shí)結(jié)論成立，即第k層上至多有層

37、上至多有2k-1個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)， 那么那么 i=k+1時(shí)，由于第時(shí)，由于第k+1層上的結(jié)點(diǎn)層上的結(jié)點(diǎn)是第是第k層上結(jié)點(diǎn)的孩子，而二叉樹中每個(gè)結(jié)點(diǎn)最多有層上結(jié)點(diǎn)的孩子，而二叉樹中每個(gè)結(jié)點(diǎn)最多有2個(gè)孩子，故在第個(gè)孩子，故在第k+1層上最大結(jié)點(diǎn)個(gè)數(shù)為第層上最大結(jié)點(diǎn)個(gè)數(shù)為第k層上的層上的最大結(jié)點(diǎn)個(gè)數(shù)的二倍，即最大結(jié)點(diǎn)個(gè)數(shù)的二倍，即22k-12k。結(jié)論成立。結(jié)論成立。5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社性質(zhì)性質(zhì)5-2 一棵深度為一棵深度為k的二叉樹中，最多有的二叉樹中，最多有2k-1個(gè)結(jié)個(gè)結(jié)點(diǎn)，最少有點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。

38、證明：由性質(zhì)證明：由性質(zhì)1 1，深度為，深度為k k的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多 = = =2k-1=2k-1；每一層至少要有一個(gè)結(jié)點(diǎn)，因此深度為每一層至少要有一個(gè)結(jié)點(diǎn)，因此深度為k k的二叉樹，的二叉樹，至少有至少有k k個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。kii1)(層上結(jié)點(diǎn)的最大個(gè)數(shù)第5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造深度為深度為k且具有且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹一定是滿二叉樹，個(gè)結(jié)點(diǎn)的二叉樹一定是滿二叉樹，深度為深度為k且具有且具有k個(gè)結(jié)點(diǎn)的二叉樹不一定是斜樹。個(gè)結(jié)點(diǎn)的二叉樹不一定是斜樹。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社性質(zhì)性質(zhì)5-3 在一棵二

39、叉樹中，假設(shè)葉子結(jié)點(diǎn)數(shù)為在一棵二叉樹中，假設(shè)葉子結(jié)點(diǎn)數(shù)為n0，度為度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，那么有，那么有: n0n21。 證明證明: 設(shè)設(shè)n為二叉樹的結(jié)點(diǎn)總數(shù)，為二叉樹的結(jié)點(diǎn)總數(shù)，n1為二叉樹中度為二叉樹中度為為1的結(jié)點(diǎn)數(shù)，那么有：的結(jié)點(diǎn)數(shù)，那么有： nn0n1n2 在二叉樹中，除了根結(jié)點(diǎn)外，其他結(jié)點(diǎn)都有獨(dú)一的在二叉樹中，除了根結(jié)點(diǎn)外，其他結(jié)點(diǎn)都有獨(dú)一的一個(gè)分枝進(jìn)入，一個(gè)度為一個(gè)分枝進(jìn)入，一個(gè)度為1的結(jié)點(diǎn)射出一個(gè)分枝，的結(jié)點(diǎn)射出一個(gè)分枝，一個(gè)度為一個(gè)度為2的結(jié)點(diǎn)射出兩個(gè)分枝，所以有：的結(jié)點(diǎn)射出兩個(gè)分枝，所以有： nn12n21因此可以得到：因此可以得到：n0n21 。5.3 二叉樹的邏

40、輯構(gòu)造二叉樹的邏輯構(gòu)造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造n個(gè)結(jié)點(diǎn)的滿二叉樹有多少個(gè)葉子結(jié)點(diǎn)？個(gè)結(jié)點(diǎn)的滿二叉樹有多少個(gè)葉子結(jié)點(diǎn)？解：由于在滿二叉樹中沒有度為解：由于在滿二叉樹中沒有度為1的結(jié)點(diǎn)，只需度為的結(jié)點(diǎn)，只需度為0的葉子結(jié)點(diǎn)和度為的葉子結(jié)點(diǎn)和度為2的分支結(jié)點(diǎn)，所以，的分支結(jié)點(diǎn)，所以，n n0 + n2n0n2 + 1 即葉子結(jié)點(diǎn)即葉子結(jié)點(diǎn)n0n + 1/2 性質(zhì)性質(zhì)5-3 在一棵二叉樹中，假設(shè)葉子結(jié)點(diǎn)數(shù)為在一棵二叉樹中，假設(shè)葉子結(jié)點(diǎn)數(shù)為n0，度為度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，那么有，那么有: n0n21。 數(shù)據(jù)結(jié)

41、構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社性質(zhì)性質(zhì)5-4 具有具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1。 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造證明：假設(shè)具有證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立，有下式成立 2k-1 n 2k 2k-1-12k-12k-1第第k-1層層第第k層層最少結(jié)點(diǎn)數(shù)最少結(jié)點(diǎn)數(shù)最多結(jié)點(diǎn)數(shù)最多結(jié)點(diǎn)數(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造證明：假

42、設(shè)具有證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立，有下式成立 2k-1 n 2k性質(zhì)性質(zhì)5-4 具有具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1。 對(duì)不等式取對(duì)數(shù)，有：對(duì)不等式取對(duì)數(shù)，有： k-1log2nk即：即： log2nklog2n+1由于由于k是整數(shù)，故必有是整數(shù)，故必有k log2n +1。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社性質(zhì)性質(zhì)5-5 對(duì)一棵具有對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中從個(gè)結(jié)點(diǎn)的完全二叉樹中從1開開場(chǎng)按層序

43、編號(hào)，那么對(duì)于恣意的序號(hào)為場(chǎng)按層序編號(hào)，那么對(duì)于恣意的序號(hào)為i1in的的結(jié)點(diǎn)簡稱為結(jié)點(diǎn)結(jié)點(diǎn)簡稱為結(jié)點(diǎn)i，有：，有： 1假設(shè)假設(shè)i1，那么結(jié)點(diǎn)，那么結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號(hào)為的雙親結(jié)點(diǎn)的序號(hào)為 i/2；假設(shè)假設(shè)i1，那么結(jié)點(diǎn)，那么結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。 2假設(shè)假設(shè)2in，那么結(jié)點(diǎn)，那么結(jié)點(diǎn)i的左孩子的序號(hào)為的左孩子的序號(hào)為2i；假設(shè)假設(shè)2in，那么結(jié)點(diǎn)，那么結(jié)點(diǎn)i無左孩子。無左孩子。 3假設(shè)假設(shè)2i+1n，那么結(jié)點(diǎn)，那么結(jié)點(diǎn)i的右孩子的序號(hào)為的右孩子的序號(hào)為2i+1；假設(shè)；假設(shè)2i+1n，那么結(jié)點(diǎn)，那么結(jié)點(diǎn) i無右孩子。無右孩子。 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)

44、造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版一棵具有對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全個(gè)結(jié)點(diǎn)的完全二叉樹中從二叉樹中從1開場(chǎng)按層序編開場(chǎng)按層序編號(hào)，那么號(hào)，那么 結(jié)點(diǎn)結(jié)點(diǎn)i的雙親結(jié)點(diǎn)為的雙親結(jié)點(diǎn)為 i/2； 結(jié)點(diǎn)結(jié)點(diǎn)i的左孩子為的左孩子為2i； 結(jié)點(diǎn)結(jié)點(diǎn)i的右孩子為的右孩子為2i1。 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造性質(zhì)性質(zhì)5闡明，在完全二叉樹中，結(jié)點(diǎn)的層序編號(hào)反映闡明，在完全二叉樹中，結(jié)點(diǎn)的層序編號(hào)反映了結(jié)點(diǎn)之間的邏輯關(guān)系。了結(jié)點(diǎn)之間的邏輯關(guān)系。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社ADT BiTreeData

45、 由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左右子樹構(gòu)成，由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左右子樹構(gòu)成， 結(jié)點(diǎn)具有一樣數(shù)據(jù)類型及層次關(guān)系結(jié)點(diǎn)具有一樣數(shù)據(jù)類型及層次關(guān)系Operation 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造同樹類似，在不同的運(yùn)用中，二叉樹的根本操作不盡一樣。下同樹類似，在不同的運(yùn)用中，二叉樹的根本操作不盡一樣。下面給出一個(gè)二叉樹籠統(tǒng)數(shù)據(jù)類型定義的例子，簡單起見，根本面給出一個(gè)二叉樹籠統(tǒng)數(shù)據(jù)類型定義的例子，簡單起見，根本操作只包含二叉樹的遍歷，在實(shí)踐運(yùn)用中，應(yīng)根據(jù)詳細(xì)需求重操作只包含二叉樹的遍歷，在實(shí)踐運(yùn)用中，應(yīng)根據(jù)詳細(xì)需求重新定義其根本操作。新定義其根本操作。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版

46、）第2版版清華大學(xué)出版社清華大學(xué)出版社 InitBiTree 前置條件：無前置條件：無 輸入：無輸入：無 功能：初始化一棵二叉樹功能：初始化一棵二叉樹 輸出：無輸出：無 后置條件：構(gòu)造一個(gè)空的二叉樹后置條件：構(gòu)造一個(gè)空的二叉樹DestroyBiTree 前置條件：二叉樹已存在前置條件：二叉樹已存在 輸入：無輸入：無 功能：銷毀一棵二叉樹功能：銷毀一棵二叉樹 輸出：無輸出：無 后置條件：釋放二叉樹占用的存儲(chǔ)空間后置條件：釋放二叉樹占用的存儲(chǔ)空間 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 PreOrder 前置條件：二叉樹已存在

47、前置條件：二叉樹已存在 輸入：無輸入：無 功能：前序遍歷二叉樹功能：前序遍歷二叉樹 輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性陳列輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性陳列 后置條件：二叉樹不變后置條件：二叉樹不變 InOrder 前置條件：二叉樹已存在前置條件：二叉樹已存在 輸入：無輸入：無 功能：中序遍歷二叉樹功能：中序遍歷二叉樹 輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性陳列輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性陳列 后置條件：二叉樹不變后置條件：二叉樹不變 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 PostOrder 前置條件：二叉樹已存在前置條件：二叉樹已存在

48、輸入：無輸入：無 功能：后序遍歷二叉樹功能：后序遍歷二叉樹 輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性陳列輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性陳列 后置條件：二叉樹不變后置條件：二叉樹不變 LeverOrder 前置條件：二叉樹已存在前置條件：二叉樹已存在 輸入：無輸入：無 功能：層序遍歷二叉樹功能：層序遍歷二叉樹 輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性陳列輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性陳列 后置條件：二叉樹不變后置條件：二叉樹不變 endADT5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，

49、按照某種次序訪問二叉樹中的一切結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一訪問二叉樹中的一切結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。次且僅被訪問一次。二叉樹遍歷操作的結(jié)果？二叉樹遍歷操作的結(jié)果？非線性構(gòu)造線性化非線性構(gòu)造線性化5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造籠統(tǒng)操作，可以是對(duì)結(jié)點(diǎn)進(jìn)展的各種籠統(tǒng)操作，可以是對(duì)結(jié)點(diǎn)進(jìn)展的各種處置，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)。處置，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)。前序遍歷前序遍歷中序遍歷中序遍歷后序遍歷后序遍歷層序遍歷層序遍歷 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社二叉樹的遍歷方式：二叉樹的遍歷方式：DLRDLR、LDRLDR、LRDLRD、DRL

50、DRL、RDLRDL、RLD RLD 假設(shè)限定先左后右，那么二叉樹遍歷方式有三種：假設(shè)限定先左后右，那么二叉樹遍歷方式有三種：前序：前序：DLR中序：中序：LDR后序：后序：LRD層序遍歷：按二叉樹的層序編號(hào)的次序訪問各結(jié)點(diǎn)。層序遍歷：按二叉樹的層序編號(hào)的次序訪問各結(jié)點(diǎn)。 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造思索二叉樹的組成：思索二叉樹的組成：根結(jié)點(diǎn)根結(jié)點(diǎn)D左子樹左子樹L右子樹右子樹R二二叉叉樹樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社前序根遍歷前序根遍歷假設(shè)二叉樹為空，那么空操作假設(shè)二叉樹為空，那么空操作前往；否那么：前往；否那么：訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)；前

51、序遍歷根結(jié)點(diǎn)的左子樹；前序遍歷根結(jié)點(diǎn)的左子樹；前序遍歷根結(jié)點(diǎn)的右子樹。前序遍歷根結(jié)點(diǎn)的右子樹。5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造前序遍歷序列：前序遍歷序列：A B D G C E FABCDEFG數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社中序根遍歷中序根遍歷假設(shè)二叉樹為空，那么空操作前假設(shè)二叉樹為空，那么空操作前往；否那么：往；否那么：中序遍歷根結(jié)點(diǎn)的左子樹；中序遍歷根結(jié)點(diǎn)的左子樹；訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)；中序遍歷根結(jié)點(diǎn)的右子樹。中序遍歷根結(jié)點(diǎn)的右子樹。 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造中序遍歷序列：中序遍歷序列：D G B A E C FABCDEF

52、G數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社后序根遍歷后序根遍歷假設(shè)二叉樹為空，那么空操作前假設(shè)二叉樹為空，那么空操作前往；否那么：往；否那么：后序遍歷根結(jié)點(diǎn)的左子樹；后序遍歷根結(jié)點(diǎn)的左子樹；后序遍歷根結(jié)點(diǎn)的右子樹。后序遍歷根結(jié)點(diǎn)的右子樹。訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)；5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造后序遍歷序列：后序遍歷序列：G D B E F C AABCDEFG數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社層序遍歷層序遍歷二叉樹的層次遍歷是指從二二叉樹的層次遍歷是指從二叉樹的第一層即根結(jié)點(diǎn)叉樹的第一層即根結(jié)點(diǎn)開場(chǎng)，從上至下逐層遍歷，開

53、場(chǎng)，從上至下逐層遍歷，在同一層中，那么按從左到在同一層中，那么按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造層序遍歷序列：層序遍歷序列：A B C D E F GABCDEFG數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造二叉樹遍歷操作練習(xí)二叉樹遍歷操作練習(xí)前序遍歷結(jié)果：前序遍歷結(jié)果：- + a * b - c d / e f中序遍歷結(jié)果：中序遍歷結(jié)果：a + b * c - d - e / f后序遍歷結(jié)果：后序遍歷結(jié)果：a b c d - * + e f / -數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)

54、構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造假設(shè)知一棵二叉樹的前序或中序，或后序，或假設(shè)知一棵二叉樹的前序或中序，或后序，或?qū)有蛐蛄?，能否?dú)一確定這棵二叉樹呢？層序序列，能否獨(dú)一確定這棵二叉樹呢？ABC例：知前序序列為例：知前序序列為ABC，那么能夠的二叉樹有，那么能夠的二叉樹有5種。種。ABC數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造例：知前序遍歷序列為例：知前序遍歷序列為ABC，后序遍歷序列為，后序遍歷序列為CBA，那么以下二叉樹都滿足條件。，那么以下二叉樹都滿足條件。AB

55、CABC假設(shè)知一棵二叉樹的前序序列和后序序列，能否假設(shè)知一棵二叉樹的前序序列和后序序列，能否獨(dú)一確定這棵二叉樹呢？獨(dú)一確定這棵二叉樹呢？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社假設(shè)知一棵二叉樹的前序序列和中序序列，能否假設(shè)知一棵二叉樹的前序序列和中序序列，能否獨(dú)一確定這棵二叉樹呢？怎樣確定？獨(dú)一確定這棵二叉樹呢？怎樣確定？ 例如：知一棵二叉樹的前序遍歷序列和中序遍歷序例如：知一棵二叉樹的前序遍歷序列和中序遍歷序列分別為列分別為ABCDEFGHI ABCDEFGHI 和和BCAEDGHFIBCAEDGHFI，如何構(gòu)造該二叉，如何構(gòu)造該二叉樹呢樹呢? ? 5.3 二叉

56、樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社前序：前序：A B C D E F G H IA B C D E F G H I中序：中序：B C A E D G H F IB C A E D G H F I前序：前序：B CB C中序：中序：B CB C5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造 B C D EF GH IA前序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHI數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社前序：前序：F G H IF G H I中序：中序：G H F

57、IG H F I5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造前序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHIABCDEFIGH數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社1. 根據(jù)前序序列的第一個(gè)元素建立根結(jié)點(diǎn)；根據(jù)前序序列的第一個(gè)元素建立根結(jié)點(diǎn)；2. 在中序序列中找到該元素，確定根結(jié)點(diǎn)的左右子樹在中序序列中找到該元素，確定根結(jié)點(diǎn)的左右子樹的中序序列；的中序序列；3. 在前序序列中確定左右子樹的前序序列；在前序序列中確定左右子樹的前序序列；4. 由左子樹的前序序列和中序序列建立左子樹；由左子樹的前序序列和中序序列建立左子樹；5.

58、由右子樹的前序序列和中序序列建立右子樹。由右子樹的前序序列和中序序列建立右子樹。 5.3 二叉樹的邏輯構(gòu)造二叉樹的邏輯構(gòu)造知一棵二叉樹的前序序列和中序序列，構(gòu)造該二叉樹知一棵二叉樹的前序序列和中序序列，構(gòu)造該二叉樹的過程如下：的過程如下： 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社順序存儲(chǔ)構(gòu)造順序存儲(chǔ)構(gòu)造二叉樹的順序存儲(chǔ)構(gòu)培育是用一維數(shù)組存儲(chǔ)二叉樹二叉樹的順序存儲(chǔ)構(gòu)培育是用一維數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置下標(biāo)應(yīng)能表達(dá)中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置下標(biāo)應(yīng)能表達(dá)結(jié)點(diǎn)之間的邏輯關(guān)系結(jié)點(diǎn)之間的邏輯關(guān)系父子關(guān)系。父子關(guān)系。 如何利用數(shù)組下標(biāo)來反映結(jié)點(diǎn)之間的邏輯關(guān)系

59、如何利用數(shù)組下標(biāo)來反映結(jié)點(diǎn)之間的邏輯關(guān)系? ?完全二叉樹和滿二叉樹中結(jié)點(diǎn)的序號(hào)可以獨(dú)一地完全二叉樹和滿二叉樹中結(jié)點(diǎn)的序號(hào)可以獨(dú)一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系反映出結(jié)點(diǎn)之間的邏輯關(guān)系 。5.4 二叉樹的存儲(chǔ)構(gòu)造及實(shí)現(xiàn)二叉樹的存儲(chǔ)構(gòu)造及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 A B C D E F G H I J數(shù)組下標(biāo)數(shù)組下標(biāo) 1 2 3 4 5 6 7 8 9 10完全二叉樹的順序存儲(chǔ)完全二叉樹的順序存儲(chǔ)5.4 二叉樹的存儲(chǔ)構(gòu)造及實(shí)現(xiàn)二叉樹的存儲(chǔ)構(gòu)造及實(shí)現(xiàn)CDEFGHIJ以以編編號(hào)號(hào)為為下下標(biāo)標(biāo)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版

60、版清華大學(xué)出版社清華大學(xué)出版社二叉樹的順序存儲(chǔ)二叉樹的順序存儲(chǔ)ABC DE F G數(shù)組下標(biāo)數(shù)組下標(biāo) 1 2 3 4 5 6 7 8 9 10 11 12 135.4 二叉樹的存儲(chǔ)構(gòu)造及實(shí)現(xiàn)二叉樹的存儲(chǔ)構(gòu)造及實(shí)現(xiàn)ABCDFGE以以編編號(hào)號(hào)為為下下標(biāo)標(biāo)ABCDFGE123561013按照完全按照完全二叉樹編號(hào)二叉樹編號(hào)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社二叉樹的順序存儲(chǔ)二叉樹的順序存儲(chǔ)ABC DE F G數(shù)組下標(biāo)數(shù)組下標(biāo) 0 1 2 3 4 5 6 7 8 9 10 11 125.4 二叉樹的存儲(chǔ)構(gòu)造及實(shí)現(xiàn)二叉樹的存儲(chǔ)構(gòu)造及實(shí)現(xiàn)ABCDFGEABCDFGE1235