第六章 樹和二叉樹

1、6.1 樹的類型定義樹的類型定義6.2 二叉樹的類型二叉樹的類型定義定義6.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)6.4 二叉樹的遍歷二叉樹的遍歷6.5 線索二叉樹線索二叉樹6.6 樹和森林的表示方法樹和森林的表示方法6.7 哈夫曼樹與哈夫曼編碼哈夫曼樹與哈夫曼編碼第六章第六章 樹和二叉樹樹和二叉樹6.1 樹的類型定義樹的類型定義 A C G T2D H I T3J M B E L KT1 F例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系數(shù)據(jù)對象數(shù)據(jù)對象 D： D是具有相同特

2、性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：若若D為空集，則稱為為空集，則稱為空樹空樹 。否則否則: (1) 在在D中中存在唯一存在唯一的稱為的稱為根根的數(shù)據(jù)元素的數(shù)據(jù)元素root； (2) 當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互不相個(gè)互不相交的有限集交的有限集T1, 2, , Tm，其中每一棵子集本身又是一棵，其中每一棵子集本身又是一棵符合本定義的樹，稱為根符合本定義的樹，稱為根root的的子樹子樹。樹的邏輯表示方法樹的邏輯表示方法 A C G J B E D F I H M K L 樹形表示法樹形表示法 H L D K I M C G

3、J E B F 文氏圖表示法文氏圖表示法 A 括號(hào)表示法括號(hào)表示法 A(B(E,F),C(G(J),D(H,I(K,L,M) 樹根T1T2T3（廣義表表示法）（廣義表表示法）主要分為三大類：主要分為三大類： 第一類第一類, ,尋找滿足某種特定關(guān)系的結(jié)點(diǎn)尋找滿足某種特定關(guān)系的結(jié)點(diǎn), ,如尋如尋找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等；找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等； 第二類第二類, ,插入或刪除某個(gè)結(jié)點(diǎn)插入或刪除某個(gè)結(jié)點(diǎn), ,如在樹的當(dāng)前如在樹的當(dāng)前結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第i i個(gè)個(gè)孩子結(jié)點(diǎn)等；孩子結(jié)點(diǎn)等； 第三類第三類, ,遍歷樹中每個(gè)結(jié)點(diǎn)遍歷樹中每個(gè)結(jié)點(diǎn)。樹的基本操

4、作：樹的基本操作：樹的遍歷可有三條搜索路徑樹的遍歷可有三條搜索路徑:按層次遍歷按層次遍歷:先根先根(次序次序)遍歷遍歷:后根后根(次序次序)遍歷遍歷: 若樹不空，則先訪問根結(jié)點(diǎn)，然后若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。依次先根遍歷各棵子樹。 若樹不空，則先依次后根遍歷各棵若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。子樹，然后訪問根結(jié)點(diǎn)。 若樹不空，則自上而下自左至右若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。訪問樹中每個(gè)結(jié)點(diǎn)。 A B C DE F G H I J K 先根遍歷時(shí)頂點(diǎn)先根遍歷時(shí)頂點(diǎn)的訪問次序：的訪問次序：A B E F C D G H I J K 后根

5、遍歷時(shí)頂點(diǎn)后根遍歷時(shí)頂點(diǎn)的訪問次序：的訪問次序：E F B C I J K H G D A 層次遍歷時(shí)頂點(diǎn)層次遍歷時(shí)頂點(diǎn)的訪問次序：的訪問次序：A B C D E F G H I J K() 有確定的根；() 樹根和子樹根之間為有向關(guān)系。有向樹：有向樹：有序樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：無序樹：子樹之間不存在確定的次序關(guān)系。對比對比樹型結(jié)構(gòu)樹型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)的結(jié)構(gòu)特點(diǎn)線性結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無前驅(qū)無前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無后繼無后繼)多個(gè)葉子結(jié)點(diǎn)多個(gè)

6、葉子結(jié)點(diǎn) ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )基基 本本 術(shù)術(shù) 語語結(jié)點(diǎn)結(jié)點(diǎn): :結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :樹的度樹的度: :葉子結(jié)點(diǎn)葉子結(jié)點(diǎn): :分支結(jié)點(diǎn)分支結(jié)點(diǎn): :數(shù)據(jù)元素+ +若干指向子樹的分支分支的個(gè)數(shù)樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM(從根到結(jié)點(diǎn)的)路徑路徑：孩子孩子結(jié)點(diǎn)、雙親雙親結(jié)點(diǎn)兄弟兄弟結(jié)點(diǎn)、堂兄弟祖先祖先結(jié)點(diǎn)、子孫子孫結(jié)點(diǎn)結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次: :樹的深度：樹的深度： 由從根根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGH

7、IJMKL假設(shè)根結(jié)點(diǎn)的層次為1，第l 層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹中葉子結(jié)點(diǎn)所在的最大層次任何一棵非空樹是一個(gè)二元組 Tree = （root，F(xiàn)）其中：root 被稱為根結(jié)點(diǎn) F 被稱為子樹森林森林：森林：是m（m0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF6.2 二叉樹的類型定義二叉樹的類型定義 二叉樹或?yàn)榭諛淇諛?，或是由一個(gè)根結(jié)根結(jié)點(diǎn)點(diǎn)加上兩棵兩棵分別稱為左子樹左子樹和右子樹的、互不交的互不交的二叉樹二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹二叉樹的五種基本形態(tài)：二叉樹的五種基本形態(tài)：N空樹空樹只含根結(jié)點(diǎn)只含根結(jié)點(diǎn)NNNLRR右子樹為空樹右子樹為空樹L左子樹

8、為空樹左子樹為空樹左右子左右子樹均不樹均不為空樹為空樹二叉樹二叉樹的重要特性的重要特性 性質(zhì)性質(zhì) 1 ：在二叉樹的第 i 層上至多有2i-1 個(gè)結(jié)點(diǎn)。 (i1)用歸納法證明用歸納法證明： 歸納基歸納基： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)：層時(shí)，只有一個(gè)根結(jié)點(diǎn)： 2i-1 = 20 = 1；假設(shè)對所有的假設(shè)對所有的 j，1 j i，命題成立；命題成立；二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第則第 i 層的結(jié)點(diǎn)數(shù)層的結(jié)點(diǎn)數(shù) = 2i-2 2 = 2i-1 。423167891011121314155第三層上第三層上(i=3)(i

9、=3)，有，有2 23-13-1=4=4個(gè)節(jié)點(diǎn)。個(gè)節(jié)點(diǎn)。第四層上第四層上(i=4)(i=4)，有，有2 24-14-1=8=8個(gè)節(jié)點(diǎn)。個(gè)節(jié)點(diǎn)。 性質(zhì)性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k-1 個(gè)結(jié)點(diǎn)（k1）。證明：證明： 基于上一條性質(zhì)，深度為基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為的二叉樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2k-1 = 2k-1 。423167891011121314155此樹的深度此樹的深度k =4=4，共有，共有2 24 4-1=15-1=15個(gè)節(jié)點(diǎn)。個(gè)節(jié)點(diǎn)。 性質(zhì)性質(zhì) 3 ： 對任何一棵二叉樹，若它含有對任何一棵二叉樹，若它含有n0 個(gè)葉子結(jié)點(diǎn)、個(gè)

10、葉子結(jié)點(diǎn)、n2 個(gè)度為個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式：的結(jié)點(diǎn)，則必存在關(guān)系式：n0 = n2+1。證明：證明：設(shè)設(shè) 二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2又又 二叉樹上分支總數(shù) b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。423167891011121314155n n0 0=8=8n n2 2=7=7兩類兩類特殊特殊的二叉樹：的二叉樹：滿二叉樹滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹完全二叉樹：樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為編號(hào)為 1 至至 n 的結(jié)點(diǎn)的結(jié)點(diǎn)一一對應(yīng)。1

11、23456789 10 11 12 13 14 15abcdefghij特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。 性質(zhì)性質(zhì) 4 ： 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1 。證明：證明：設(shè)設(shè)完全二叉樹的深度為 k 則根據(jù)第二條性質(zhì)得 2k-1 n 2k 即 k-1 log2 n n，則該結(jié)點(diǎn)無左孩子，則該結(jié)點(diǎn)無左孩子， 否則，編號(hào)為否則，編號(hào)為 2i 的結(jié)點(diǎn)為其的結(jié)點(diǎn)為其左孩子左孩子結(jié)點(diǎn)；結(jié)點(diǎn)；(3) 若若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否則，編號(hào)為否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其的結(jié)點(diǎn)為其右孩子右孩子結(jié)點(diǎn)結(jié)點(diǎn)。4231678

12、910 11125 完全二叉樹完全二叉樹6.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)蕉?、二叉樹的鏈?zhǔn)?存儲(chǔ)表示存儲(chǔ)表示一、一、 二叉樹的順序二叉樹的順序 存儲(chǔ)表示存儲(chǔ)表示#define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點(diǎn)數(shù)typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTree bt;一、一、 二叉樹的順序存儲(chǔ)表示二叉樹的順序存儲(chǔ)表示用一組連續(xù)的存儲(chǔ)單元存放二叉樹用一組連續(xù)的存儲(chǔ)單元存放二叉樹的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。位置蘊(yùn)含著結(jié)點(diǎn)之間的

13、關(guān)系。二叉樹二叉樹順序順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) bt16若父結(jié)點(diǎn)在數(shù)組中若父結(jié)點(diǎn)在數(shù)組中i下標(biāo)處，其左孩子在下標(biāo)處，其左孩子在2*i處，右孩子在處，右孩子在2*i+1處處。11 A B c F E D 1 2 4 8 910 5 6 3 7121314152h-1= 24-1 = 15用一組連續(xù)的存儲(chǔ)單元存放二叉樹的數(shù)據(jù)用一組連續(xù)的存儲(chǔ)單元存放二叉樹的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對位置蘊(yùn)含著結(jié)元素。結(jié)點(diǎn)在數(shù)組中的相對位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。點(diǎn)之間的關(guān)系。0000FE000DC0BA15141312111098765432100一般二叉樹必須按完全二叉樹的形式存儲(chǔ)，將造成存儲(chǔ)的浪費(fèi)。一般二叉樹必須按

14、完全二叉樹的形式存儲(chǔ)，將造成存儲(chǔ)的浪費(fèi)。typedef TElemType SqBiTreeMAX_TREE_SIZE+1; / 0號(hào)單元未用SqBiTree bt例如例如:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示1. 1. 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表3 3雙親鏈表雙親鏈表4線索鏈表線索鏈表ADEBCF rootlchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)

15、:1. 1. 二叉鏈表二叉鏈表typedef struct node / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data;/數(shù)據(jù)元素?cái)?shù)據(jù)元素 struct node *lchild, *rchild; / 左右孩子指針左右孩子指針 BTNode;ADEBCF root 2三叉鏈表三叉鏈表parent lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):typedef struct TriTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針左右孩子指針 struct TriTNode *paren

16、t; /雙親指針雙親指針 TriTNode, *TriTree;0123456B2C0A -1D2E3F4 data parent結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):3 3雙親鏈表雙親鏈表LRTagLRRRL typedef struct BPTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; int *parent; / 指向雙親的指針 char LRTag; / 左、右孩子標(biāo)志域 BPTNode typedef struct BPTree / 樹結(jié)構(gòu)樹結(jié)構(gòu) BPTNode nodesMAX_TREE_SIZE; int num_node; / 結(jié)點(diǎn)數(shù)目結(jié)點(diǎn)數(shù)目 int root; / 根結(jié)點(diǎn)的

17、位置根結(jié)點(diǎn)的位置 BPTree6.4二叉樹的遍歷二叉樹的遍歷一、問題的提出一、問題的提出二、先左后右的遍歷算法二、先左后右的遍歷算法三、算法的遞歸描述三、算法的遞歸描述四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述五五、遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例遍歷：遍歷：按某條搜索路線按某條搜索路線尋訪尋訪樹中樹中每個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)且且只被訪問一次只被訪問一次。一、問題的提出一、問題的提出“訪問訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。查找某個(gè)結(jié)點(diǎn)，或?qū)Χ鏄渲腥拷Y(jié)點(diǎn)進(jìn)行某種處理，就需要遍歷。查找某個(gè)結(jié)點(diǎn)，或?qū)Χ鏄渲腥拷Y(jié)點(diǎn)進(jìn)行某種處理，就需要遍歷。 “遍歷遍歷”是任何類型均有的操作

18、，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷存在如何遍歷即按什么樣的搜索路徑搜索路徑遍歷的問題。對對“二叉樹二叉樹”而言，可以有三條搜索路徑而言，可以有三條搜索路徑 1先上后下先上后下的按層次遍歷； 2先左先左（子樹）后右后右（子樹）的遍歷； 3先右先右（子樹）后左后左（子樹）的遍歷。二、先左后右的遍歷算法二、先左后右的遍歷算法按按先左后右先左后右的原則，一般使用的原則，一般使用三種遍歷：三種遍歷：先根遍歷先根遍歷(D L R):(D L R): 訪問根結(jié)點(diǎn)，按先序訪問根結(jié)點(diǎn)，按先

19、序遍歷左子樹，按先序遍歷右子樹。遍歷左子樹，按先序遍歷右子樹。中根遍歷中根遍歷(L D R):(L D R): 按中序遍歷左子樹，訪按中序遍歷左子樹，訪問根結(jié)點(diǎn)，按中序遍歷右子樹。問根結(jié)點(diǎn)，按中序遍歷右子樹。后根遍歷后根遍歷(L R D):(L R D): 按后序遍歷左子樹，按按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點(diǎn)。后序遍歷右子樹，訪問根結(jié)點(diǎn)。 二叉樹為空時(shí)，執(zhí)行空二叉樹為空時(shí)，執(zhí)行空操作，即空二叉樹已遍歷完。操作，即空二叉樹已遍歷完。遍歷算法例：遍歷算法例：先序遍歷：先序遍歷：D L R中序遍歷：中序遍歷：L D R后序遍歷：后序遍歷：L R DADBCT1T2T3D L RAD L

20、 RD L RBDCD L R以先序遍歷以先序遍歷D L RD L R為例演示遍歷過程為例演示遍歷過程 ABDCBDAC DBCA三、算法的遞歸描述三、算法的遞歸描述void Preorder (BTree *b)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，先序遍歷二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，先序遍歷二叉樹b b / / 初始條件：二叉樹初始條件：二叉樹b b存在，存在， / / 操作結(jié)果：先序遞歸遍操作結(jié)果：先序遞歸遍歷歷b b，打印每，打印每個(gè)結(jié)個(gè)結(jié)點(diǎn)一點(diǎn)一次且僅一次次且僅一次 if (T) / b不空不空 print(“%c”,b-data); /先訪問根結(jié)點(diǎn)先訪問根結(jié)點(diǎn) Preorder(b-lchild

21、); /再先序遍歷左子樹再先序遍歷左子樹 Preorder(b-rchild);/最后先序遍歷右子樹最后先序遍歷右子樹 A B C E F D G A B C D E F G (a) (b) typedef struct node / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data;/數(shù)據(jù)元素?cái)?shù)據(jù)元素 struct node *lchild, *rchild; / 左右孩子指針左右孩子指針 BTNode;b四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述 A B C E F D G A B C D E F G (a) (b) T void InOrder(BTNode *b) BTNo

22、de *StMaxSize,*p; int top=-1;if (b!=NULL) p=b; while (top-1 | p!=NULL) while (p!=NULL) /掃描掃描*p的所有左結(jié)點(diǎn)并進(jìn)棧的所有左結(jié)點(diǎn)并進(jìn)棧 top+; Sttop=p; p=p-lchild; if (top-1) p=Sttop;top-; /出棧出棧*p結(jié)點(diǎn)結(jié)點(diǎn) printf(%c ,p-data); /訪問之訪問之 p=p-rchild; /掃描掃描*p的右孩子結(jié)點(diǎn)的右孩子結(jié)點(diǎn) /end of while(top-1 | p!=NULL) 找找*b的最左下結(jié)點(diǎn)的最左下結(jié)點(diǎn)b五五、遍歷算法的應(yīng)用舉例遍歷算

23、法的應(yīng)用舉例1、輸出一棵二叉樹的所有葉子結(jié)點(diǎn)輸出一棵二叉樹的所有葉子結(jié)點(diǎn)2 2、建立二叉樹的存儲(chǔ)結(jié)構(gòu)、建立二叉樹的存儲(chǔ)結(jié)構(gòu)3 3、二叉樹的構(gòu)造（由遍歷序列確、二叉樹的構(gòu)造（由遍歷序列確定二叉樹）定二叉樹）假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ),試設(shè)計(jì)一個(gè)算試設(shè)計(jì)一個(gè)算法法,輸出一棵給定二叉樹的所有葉子結(jié)點(diǎn)。輸出一棵給定二叉樹的所有葉子結(jié)點(diǎn)。 解：輸出一棵二叉樹的所有葉子結(jié)點(diǎn)的遞歸模型解：輸出一棵二叉樹的所有葉子結(jié)點(diǎn)的遞歸模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：輸出：輸出*b結(jié)點(diǎn)的結(jié)點(diǎn)的data域域 若若*b為葉子結(jié)點(diǎn)為

24、葉子結(jié)點(diǎn) f(b)：f(b-lchild);f(b-rchild) 其他情況其他情況 void DispLeaf(BTNode *b)/p166 例例7.8 /輸出二叉樹中的葉子結(jié)點(diǎn)輸出二叉樹中的葉子結(jié)點(diǎn) if (b!=NULL) if (b-lchild=NULL & b-rchild=NULL) printf(“%c ”,b-data);/訪問葉子結(jié)點(diǎn)訪問葉子結(jié)點(diǎn) else DispLeaf(b-lchild);/輸出左子樹中的葉子結(jié)點(diǎn)輸出左子樹中的葉子結(jié)點(diǎn) DispLeaf(b-rchild);/輸出右子樹中的葉子結(jié)點(diǎn)輸出右子樹中的葉子結(jié)點(diǎn) A B C E F D G A B C

25、 D E F G (a) (b) b2 2、建立二叉樹的存儲(chǔ)、建立二叉樹的存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)不同的定義方法相應(yīng)有不同的不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法存儲(chǔ)結(jié)構(gòu)的建立算法 以字符串的形式以字符串的形式 根根 左子樹左子樹 右子樹右子樹定義一棵二叉樹定義一棵二叉樹例如:ABCD以空白字符“ ”表示A(B( ,C( , ),D( , )空樹空樹只含一個(gè)根結(jié)點(diǎn)只含一個(gè)根結(jié)點(diǎn)的二叉樹的二叉樹A以字符串“A ”表示以下列字符串表示void CreateBiTree(BiTree &T) /按先序次序輸入二叉樹中結(jié)點(diǎn)的值按先序次序輸入二叉樹中結(jié)點(diǎn)的值( (字符型字符型) )， / / 構(gòu)造二叉

26、鏈表表示的二叉樹構(gòu)造二叉鏈表表示的二叉樹T T。 scanf(&ch); / / 輸入結(jié)點(diǎn)的值輸入結(jié)點(diǎn)的值 if(ch= ) T=NULL; / / 結(jié)點(diǎn)的值為空結(jié)點(diǎn)的值為空 else / 結(jié)點(diǎn)的值不為空結(jié)點(diǎn)的值不為空 T=(BiTree)malloc(sizeof(BTNode); / / 生成根結(jié)點(diǎn)生成根結(jié)點(diǎn) if(!T) exit(OVERFLOW); T-data=ch; / / 將值賦給將值賦給T T所指結(jié)點(diǎn)所指結(jié)點(diǎn) CreateBiTree(T-lchild); / / 遞歸構(gòu)造左子樹遞歸構(gòu)造左子樹 CreateBiTree(T-rchild); / / 遞歸構(gòu)造右子樹遞歸

27、構(gòu)造右子樹 typedef struct node / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data;/數(shù)據(jù)元素?cái)?shù)據(jù)元素 struct node *lchild, *rchild; / 左右孩子指針左右孩子指針 BTNode; *BiTreeA B C D A BCD算法執(zhí)行過程舉例如下：ATBCDscanf(&ch); if(ch= ) T=NULL; else T=(BiTree)malloc(sizeof(BTNode); / 生成根結(jié)點(diǎn)生成根結(jié)點(diǎn) if(!T) exit(OVERFLOW); T-data=ch; CreateBiTree(T-lchild); / 遞歸構(gòu)造左

28、子樹遞歸構(gòu)造左子樹 CreateBiTree(T-rchild); / 遞歸構(gòu)造右子樹遞歸構(gòu)造右子樹void CreateBiTree(BiTree &T)typedef struct node / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data;/數(shù)據(jù)元素?cái)?shù)據(jù)元素 struct node *lchild, *rchild; / 左右孩子指針左右孩子指針 BTNode; *BiTree 僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹，由遍歷序列確定二叉樹由遍歷序列確定二叉樹 如果同時(shí)已知二叉樹的中序序列“cbdaegf”，則會(huì)如何？ 二叉樹的先序序列二叉樹的中序序列左子

29、樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根根由二叉樹的先序和中序序列確定二叉樹由二叉樹的先序和中序序列確定二叉樹a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列6.5線索二叉樹線索二叉樹 何謂線索二叉樹？何謂線索二叉樹？ 線索鏈表的遍歷算法線索鏈表的遍歷算法 如何建立線索鏈表？如何建立線索鏈表？一、一、何謂線索二叉樹？何謂線索二叉樹？遍歷二叉樹的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性序列。ABCDEFGHK例如:先序先序序列: A B C D E F G H K中序中序序列: B D C A H G K F E后序后

30、序序列: D C B H K G F E A指向該線性序列中的“前驅(qū)”和 “后繼” 的指針指針，稱作“線索線索”與其相應(yīng)的二叉樹，稱作 “線索二叉樹線索二叉樹”包含 “線索” 的存儲(chǔ)結(jié)構(gòu)，稱作 “線索鏈線索鏈表表”A B C D E F G H K D C B E 意義：保存遍歷二叉樹后得到的線性序列，避免重復(fù)遍歷。意義：保存遍歷二叉樹后得到的線性序列，避免重復(fù)遍歷。對對線索鏈表線索鏈表中結(jié)點(diǎn)的約定：中結(jié)點(diǎn)的約定： 在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域增加兩個(gè)標(biāo)志域，規(guī)定如下：如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表線索鏈表”。左標(biāo)志左標(biāo)志ltag : 0 表示表示l

31、child指向左孩子結(jié)點(diǎn)指向左孩子結(jié)點(diǎn) 1 表示表示lchild指向前驅(qū)結(jié)點(diǎn)指向前驅(qū)結(jié)點(diǎn)右標(biāo)志右標(biāo)志rtag : 0 表示表示rchild指向右孩子結(jié)點(diǎn)指向右孩子結(jié)點(diǎn) 1 表示表示rchild指向后繼結(jié)點(diǎn)指向后繼結(jié)點(diǎn)這樣這樣,每個(gè)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如下：每個(gè)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如下：LChildLtagDataRtagRChild 為了實(shí)現(xiàn)線索化二叉樹為了實(shí)現(xiàn)線索化二叉樹,將前面二叉樹結(jié)點(diǎn)的類型將前面二叉樹結(jié)點(diǎn)的類型定義如下：定義如下： typedef struct node ElemType data;/*結(jié)點(diǎn)數(shù)據(jù)域結(jié)點(diǎn)數(shù)據(jù)域*/ int ltag,rtag; /*增加的線索標(biāo)記增加的線索標(biāo)記*/ s

32、truct node *lchild;/*左孩子或線索指針左孩子或線索指針*/ struct node *rchild;/*右孩子或線索指針右孩子或線索指針*/ TBTNode;/*線索樹結(jié)點(diǎn)類型定義線索樹結(jié)點(diǎn)類型定義*/ lchildltagdatartagrchild二、線索鏈表的遍歷算法二、線索鏈表的遍歷算法（p184）:由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。例如例如: 對中序線索化鏈表的遍歷算法對中序線索化鏈表的遍歷算法 中序遍歷的第一個(gè)結(jié)點(diǎn)中序遍歷的第一個(gè)結(jié)點(diǎn) ？左子樹上處于“最左下最左下”（沒有左子樹）的結(jié)點(diǎn)。 在中序線索化鏈表中結(jié)點(diǎn)的后

33、繼在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？若若無右子樹，則為則為后繼線索后繼線索所指結(jié)點(diǎn)；否則為否則為對其右子樹右子樹進(jìn)行中序遍歷遍歷時(shí)訪問的第一個(gè)結(jié)點(diǎn)。第一個(gè)結(jié)點(diǎn)。 0 1 0 A 0 0 B 1 0 C 0 1 E 1 1 F 1 1 D 0 1 G 1 0 1 0 A 0 0 B 1 0 C 0 1 E 1 1 F 1 1 D 0 1 G 1 Thrt Thrt 0 1 0 A 0 0 B 1 0 C 0 1 E 1 1 F 1 1 D 0 1 G 1 Thrt (a) 中序線索樹 (b) 先序線索樹 (c) 后序線索樹 lchildltagdatartagrchild A B C D E F

34、G 二叉樹二叉樹void ThInOrder(TBTNode *tb)/ 中序遍歷線索二叉樹中序遍歷線索二叉樹tb (頭結(jié)點(diǎn)頭結(jié)點(diǎn))的非遞歸算法的非遞歸算法 TBTNode *p=tb-lchild;/*p指向根結(jié)點(diǎn)指向根結(jié)點(diǎn)*/ while (p!=tb)/非非空樹或遍歷未結(jié)束時(shí)空樹或遍歷未結(jié)束時(shí) while (p-ltag=0) p=p-lchild;/*找開始結(jié)點(diǎn)找開始結(jié)點(diǎn)*/ printf(%c,p-data);/*訪問開始結(jié)點(diǎn)訪問開始結(jié)點(diǎn)*/ while (p-rtag=1 & p-rchild!=tb) / p-rchild是線索是線索(后繼后繼)，且不是遍歷的最后一個(gè)結(jié)點(diǎn)

35、，且不是遍歷的最后一個(gè)結(jié)點(diǎn) p=p-rchild; / p指向其后繼 printf(%c,p-data); / / 若若p-rchildp-rchild不是線索不是線索( (是右孩子是右孩子) )，p p指向右孩子，返回循環(huán)，找這指向右孩子，返回循環(huán)，找這棵子樹中序遍歷的第棵子樹中序遍歷的第1 1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) p=p-rchild; 建立線索二叉樹建立線索二叉樹,或者說或者說,對二叉樹線索化對二叉樹線索化,實(shí)質(zhì)上就實(shí)質(zhì)上就是遍歷一棵二叉樹是遍歷一棵二叉樹,在遍歷的過程中在遍歷的過程中,檢查檢查當(dāng)前結(jié)點(diǎn)的左、當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空右指針域是否為空。如果為空如果為空,將它們改為指向前驅(qū)結(jié)將

36、它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。點(diǎn)或后繼結(jié)點(diǎn)的線索。另外另外,在對一棵二叉樹添加線索在對一棵二叉樹添加線索時(shí)時(shí),我們我們創(chuàng)建一個(gè)頭結(jié)點(diǎn)創(chuàng)建一個(gè)頭結(jié)點(diǎn),并建立頭結(jié)點(diǎn)與二叉樹的根結(jié)并建立頭結(jié)點(diǎn)與二叉樹的根結(jié)點(diǎn)的線索點(diǎn)的線索。對二叉樹線索化后。對二叉樹線索化后,還須建立還須建立最后一個(gè)結(jié)點(diǎn)最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線索。與頭結(jié)點(diǎn)之間的線索。 下面以中序線索二叉樹為例下面以中序線索二叉樹為例,討論建立線索二叉樹的討論建立線索二叉樹的算法。算法。 三、如何建立線索鏈表？三、如何建立線索鏈表？CreaThread(b)算法是將以二叉鏈存儲(chǔ)的算法是將以二叉鏈存儲(chǔ)的二叉樹二叉樹b進(jìn)行進(jìn)行中序線索化中序線

37、索化,并返回線索化后頭結(jié)點(diǎn)的指針并返回線索化后頭結(jié)點(diǎn)的指針root。Thread(p)算法用于對于以算法用于對于以*p為根結(jié)點(diǎn)為根結(jié)點(diǎn)的二叉樹中序線的二叉樹中序線索化。在整個(gè)算法中索化。在整個(gè)算法中p總是總是指向當(dāng)前指向當(dāng)前被線索化的被線索化的結(jié)點(diǎn)結(jié)點(diǎn),而而pre作為作為全局變量全局變量,指向指向剛剛訪問過的結(jié)點(diǎn)剛剛訪問過的結(jié)點(diǎn),*pre是是*p的前驅(qū)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),*p是是*pre的后繼結(jié)點(diǎn)。的后繼結(jié)點(diǎn)。 CreaThread(b)算法思路是：算法思路是：先創(chuàng)建頭結(jié)點(diǎn)先創(chuàng)建頭結(jié)點(diǎn)*root,其其lchild域?yàn)榫€索域?yàn)榫€索,rchild域?yàn)殒溨羔?。將域?yàn)殒溨羔槨child指針指指針指向向

38、*b,如果如果b二叉樹為空二叉樹為空,則將其則將其lchild指向自身。否則將指向自身。否則將*root的的lchild指向指向*b結(jié)點(diǎn)結(jié)點(diǎn),p指向指向*b結(jié)點(diǎn)結(jié)點(diǎn),pre指向指向*root結(jié)結(jié)點(diǎn)。點(diǎn)。再調(diào)用再調(diào)用Thread(b)對整個(gè)二叉樹線索化對整個(gè)二叉樹線索化。最后加入最后加入指向頭結(jié)點(diǎn)的線索指向頭結(jié)點(diǎn)的線索,并并將頭結(jié)點(diǎn)的將頭結(jié)點(diǎn)的rchild指針域線索化指針域線索化為指向最后一個(gè)結(jié)點(diǎn)為指向最后一個(gè)結(jié)點(diǎn)(由于線索化直到由于線索化直到p等于等于NULL為為止止,所以最后一個(gè)結(jié)點(diǎn)為所以最后一個(gè)結(jié)點(diǎn)為*pre)。TBTNode *CreaThread(TBTNode *b) /中序線索化二

39、叉樹中序線索化二叉樹b TBTNode *root; root=(TBTNode *)malloc(sizeof(TBTNode); /創(chuàng)建頭結(jié)點(diǎn)創(chuàng)建頭結(jié)點(diǎn) root-ltag=0;root-rtag=1; root-rchild=b; if (b=NULL) root-lchild=root;/空二叉樹空二叉樹 else root-lchild=b;/;/頭結(jié)點(diǎn)的左孩子指針指向根結(jié)點(diǎn)頭結(jié)點(diǎn)的左孩子指針指向根結(jié)點(diǎn)pre=root; / pre(/ pre(前驅(qū)前驅(qū)) )的初值指向頭結(jié)點(diǎn)，全局變量的初值指向頭結(jié)點(diǎn)，全局變量 Thread(b); / / 中序線索化，中序線索化，prepre指向中

40、序遍歷的最后一個(gè)結(jié)點(diǎn)指向中序遍歷的最后一個(gè)結(jié)點(diǎn)pre-rchild=root; /最后處理最后處理, ,加入指向頭結(jié)點(diǎn)的線索加入指向頭結(jié)點(diǎn)的線索pre-rtag=1;root-rchild=pre; /頭結(jié)點(diǎn)右線索化頭結(jié)點(diǎn)右線索化 return root; Thread(p)算法思路是：類似于中序遍歷的遞歸算算法思路是：類似于中序遍歷的遞歸算法法,在在p指針不為指針不為NULL時(shí)時(shí),先對先對*p結(jié)點(diǎn)的左子樹線索結(jié)點(diǎn)的左子樹線索化；化；若若*p結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn)結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn),則將其則將其lchild指針線索化為指針線索化為指向其前驅(qū)結(jié)點(diǎn)指向其前驅(qū)結(jié)點(diǎn)*pre,否則表示否則表示lchild指

41、向其左孩子結(jié)指向其左孩子結(jié)點(diǎn)點(diǎn),將其將其ltag置為置為1；若若*pre結(jié)點(diǎn)的結(jié)點(diǎn)的rchild指針為指針為NULL,將其將其rchild指針線索化為指向其后繼結(jié)點(diǎn)指針線索化為指向其后繼結(jié)點(diǎn)*p,否則否則rchild表示指向其右孩子結(jié)點(diǎn)表示指向其右孩子結(jié)點(diǎn),將其將其rtag置為置為1,再將再將pre指向指向*p；最后對最后對*p結(jié)點(diǎn)的右子樹線索化。結(jié)點(diǎn)的右子樹線索化。TBTNode *pre; /全局變量始終指向剛剛訪問過的結(jié)點(diǎn)全局變量始終指向剛剛訪問過的結(jié)點(diǎn)void Thread(TBTNode *&p) /對以結(jié)點(diǎn)對以結(jié)點(diǎn)p為根為根的子樹中序線索化的子樹中序線索化/ 通過中序遍歷進(jìn)

42、行中序線索化，線索化之后通過中序遍歷進(jìn)行中序線索化，線索化之后pre指向最后一個(gè)結(jié)點(diǎn)。指向最后一個(gè)結(jié)點(diǎn)。 if (p!=NULL) Thread(p-lchild); /左子樹線索化左子樹線索化if (p-lchild=NULL) /前驅(qū)線索前驅(qū)線索 p-lchild=pre; p-ltag=1; /建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線索建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線索else p-ltag=0;if (pre-rchild=NULL) /后繼線索后繼線索 pre-rchild=p;pre-rtag=1;/建立前驅(qū)結(jié)點(diǎn)的后繼線索建立前驅(qū)結(jié)點(diǎn)的后繼線索else pre-rtag=0; pre=p; / / 保持保持pre

43、pre指向指向p p的前驅(qū)的前驅(qū)Thread(p-rchild); /遞歸調(diào)用右子樹線索化遞歸調(diào)用右子樹線索化 6.6 樹和森林樹和森林 的表示方法的表示方法樹的三種存儲(chǔ)結(jié)構(gòu)樹的三種存儲(chǔ)結(jié)構(gòu)一、一、雙親表示法雙親表示法二、二、孩子鏈表表示法孩子鏈表表示法三、三、樹的二叉鏈表樹的二叉鏈表( (孩子孩子- -兄弟）兄弟） 存儲(chǔ)表示法存儲(chǔ)表示法ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5r=0n=7data parent一、雙親表示法一、雙親表示法: typedef struct PTNode Elem data; int parent; / 雙親位置域雙

44、親位置域 PTNode; typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):樹結(jié)構(gòu)樹結(jié)構(gòu):#define MAX_TREE_SIZE 100 typedef struct PTNode Elem data; int parent; / 雙親位置域 PTNode; data parent#define MAX_TREE_SIZE 100結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述語言的類型描述: :typedef struct PTNode nodes MAX_TREE_SIZE; int r

45、, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;樹結(jié)構(gòu)樹結(jié)構(gòu):ABCDEFG0 A1 B 2 C 3 D 4 E 5 F 6 G r=0n=7 1 2 34 56二、孩子鏈表表示法二、孩子鏈表表示法:parent 1 0 0 0 2 2 4datafirstchildtypedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu)孩子結(jié)點(diǎn)結(jié)構(gòu): child nextC語言的類型描述語言的類型描述: :雙親結(jié)點(diǎn)結(jié)構(gòu)雙親結(jié)點(diǎn)結(jié)構(gòu) data firstchildtypedef struct Elem data; Child

46、Ptr firstchild; / 孩子鏈的頭指針 CTBox;樹結(jié)構(gòu)樹結(jié)構(gòu):typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 CTree;ABCDEFG AB C E D F Groot AB C E D F G 三、樹的二叉鏈表三、樹的二叉鏈表 (孩子孩子-兄弟）存儲(chǔ)表示法兄弟）存儲(chǔ)表示法 firstchild data nextsibling結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNo

47、de, *CSTree;CSTree roottypedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C語言的類型描述語言的類型描述: :結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu): firstchild data nextsibling樹、森林與二叉樹的相互轉(zhuǎn)換樹、森林與二叉樹的相互轉(zhuǎn)換1. 樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹由于二叉樹可以用二叉鏈表表示，為了使一般樹也能用二叉鏈由于二叉樹可以用二叉鏈表表示，為了使一般樹也能用二叉鏈表表示，必須找出樹與二叉樹之間的關(guān)系。表表示，必須找出樹與二叉樹之間的

48、關(guān)系。 這樣，給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。這樣，給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。(1) 樹中所有相鄰兄弟之間加一條連線。 (2) 對樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線， 刪去其與其它孩子結(jié)點(diǎn)之間的連線。 (3) 以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度， 使之結(jié)構(gòu)層次分明。 I A B C DE F G H(b) A B CD E G H FI(a)樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹ABEFCDGHI(d)ABCDEFGHI(c)注意：注意：樹轉(zhuǎn)換為二叉樹后，根無右子樹。樹轉(zhuǎn)換為二叉樹后，根無右子樹。樹與二叉樹的對應(yīng) 樹的二叉鏈表樹的二叉鏈表

49、(孩子孩子-兄弟）兄弟）存儲(chǔ)表示法存儲(chǔ)表示法二叉樹二叉鏈表二叉樹二叉鏈表存儲(chǔ)表示法存儲(chǔ)表示法 2. 森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹 （1） 將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。 （2） 第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。 森林轉(zhuǎn)換為二叉樹的過程 森林轉(zhuǎn)換后的二叉樹，其根結(jié)點(diǎn)有右孩子由森林轉(zhuǎn)換成二叉樹由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若 F = ，則 B = ；否則， 由 ROOT( T1 ) 對應(yīng)得到B的根的根 root； 由 (t11, t12, , t1m1 )

50、對應(yīng)得到 LB； 由 (T2, T3, Tm ) 對應(yīng)得到 RB。設(shè)設(shè)森林森林 F = ( T1, T2, , Tm ); T1 = (root，t11, t12, , t1m1);二叉樹二叉樹 B =(root, LB, RB );由二叉樹轉(zhuǎn)換為森林由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：若 B = ， 則 F = ；否則，由 root 對應(yīng)得到 ROOT( T1 )；由LB 對應(yīng)得到 T1中的子森林（中的子森林（ t11, t12, ，t1m)；由RB 對應(yīng)得到 (T2, T3, , Tn)。 3. 3. 二叉樹還原為樹或森林二叉樹還原為樹或森林（1 1） 若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右

51、孩子、若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、 右孩子的右孩子右孩子的右孩子都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來。都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來。 （2 2） 刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。 （3 3） 整理由（整理由（1 1）、（）、（2 2）兩步所得到的樹或森林。）兩步所得到的樹或森林。 二叉樹到森林的轉(zhuǎn)換示例二叉樹到森林的轉(zhuǎn)換示例 設(shè)設(shè)二叉樹二叉樹 B =(root, LB, RB );森林森林 F = ( T1, T2, , Tm ); 由此，樹的各種操作均可對應(yīng)二叉樹的操作來完成。 應(yīng)當(dāng)注意的是，應(yīng)當(dāng)注意的是，和樹對應(yīng)的二

52、叉樹，其左、右子樹的概念已改變?yōu)椋?左是孩子，右是兄弟。左是孩子，右是兄弟。6.7 哈夫曼樹與應(yīng)用哈夫曼樹與應(yīng)用 最優(yōu)樹的定義最優(yōu)樹的定義 如何構(gòu)造最優(yōu)樹如何構(gòu)造最優(yōu)樹 哈夫曼樹與應(yīng)用哈夫曼樹與應(yīng)用 一、最優(yōu)樹的定義一、最優(yōu)樹的定義樹的路徑長度樹的路徑長度定義為： 樹中每個(gè)結(jié)點(diǎn)的路徑長度之和。 結(jié)點(diǎn)的路徑長度結(jié)點(diǎn)的路徑長度定義為： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上 分支的數(shù)目。 樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度定義為： 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度結(jié)點(diǎn)的帶權(quán)路徑長度之和 WPL(T) = wklk (對所有葉子結(jié)點(diǎn))。 在所有含 n 個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的 m 叉樹中，必存在一棵其帶權(quán)路徑帶權(quán)路

53、徑長度取最小值長度取最小值的樹，稱為“最優(yōu)樹最優(yōu)樹”。例如：例如：27 9 75492WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 54給定權(quán)值給定權(quán)值w=1,3,5,7來構(gòu)造一棵哈夫曼樹來構(gòu)造一棵哈夫曼樹 。 9 4 1 7 5 3 16 9 4 1 7 5 3 (c) (d) 1 3 5 7 4 5 7 1 3 (a) (b) (1) 根據(jù)給定的根據(jù)給定的 n 個(gè)權(quán)值個(gè)權(quán)值 w1, w2, , wn， 構(gòu)造構(gòu)造 n 棵二叉樹的集棵二叉樹的集合合F = T1, T2, , Tn，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為，其中每棵二叉樹中均

54、只含一個(gè)帶權(quán)值為 wi 的根結(jié)點(diǎn)，其左、右子樹為空樹；的根結(jié)點(diǎn)，其左、右子樹為空樹； (2) 在在 F 中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；(3) 從從F中刪去這兩棵樹，同時(shí)加入剛生成的新樹；中刪去這兩棵樹，同時(shí)加入剛生成的新樹；(4) 重復(fù)重復(fù) (2) 和和 (3) 兩步，直至兩步，直至 F 中只含一棵樹為止。中只含一棵樹為止。二、二、如何構(gòu)造最優(yōu)二叉樹（哈夫曼樹）如何