第六章 樹和二叉樹

1、6.1 樹的類型定義樹的類型定義6.2 二叉樹的類型二叉樹的類型定義定義6.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(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é)點間有明顯的層次結(jié)構(gòu)關(guān)系結(jié)點間有明顯的層次結(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時，其余結(jié)點可分為時，其余結(jié)點可分為m (m0)個互不相個互不相交的有限集交的有限集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 括號表示法括號表示法 A(B(E,F),C(G(J),D(H,I(K,L,M) 樹根T1T2T3（廣義表表示法）（廣義表表示法）主要分為三大類：主要分為三大類： 第一類第一類, ,尋找滿足某種特定關(guān)系的結(jié)點尋找滿足某種特定關(guān)系的結(jié)點, ,如尋如尋找當(dāng)前結(jié)點的雙親結(jié)點等；找當(dāng)前結(jié)點的雙親結(jié)點等； 第二類第二類, ,插入或刪除某個結(jié)點插入或刪除某個結(jié)點, ,如在樹的當(dāng)前如在樹的當(dāng)前結(jié)點上插入一個新結(jié)點或刪除當(dāng)前結(jié)點的第結(jié)點上插入一個新結(jié)點或刪除當(dāng)前結(jié)點的第i i個個孩子結(jié)點等；孩子結(jié)點等； 第三類第三類, ,遍歷樹中每個結(jié)點遍歷樹中每個結(jié)點。樹的基本操

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

5、遍歷時頂點后根遍歷時頂點的訪問次序：的訪問次序：E F B C I J K H G D A 層次遍歷時頂點層次遍歷時頂點的訪問次序：的訪問次序：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)特點的結(jié)構(gòu)特點線性結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素第一個數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點根結(jié)點 ( (無前驅(qū)無前驅(qū)) )最后一個數(shù)據(jù)元素最后一個數(shù)據(jù)元素 (無后繼無后繼)多個葉子結(jié)點多個

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

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

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

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

10、葉子結(jié)點、n2 個度為個度為 2 的結(jié)點，則必存在關(guān)系式：的結(jié)點，則必存在關(guān)系式：n0 = n2+1。證明：證明：設(shè)設(shè) 二叉樹上結(jié)點總數(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個結(jié)點的二叉樹。完全二叉樹完全二叉樹：樹中所含的 n 個結(jié)點和滿二叉樹中編號為編號為 1 至至 n 的結(jié)點的結(jié)點一一對應(yīng)。1

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

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

13、關(guān)系。二叉樹二叉樹順序順序存儲結(jié)構(gòu)存儲結(jié)構(gòu) bt16若父結(jié)點在數(shù)組中若父結(jié)點在數(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ù)的存儲單元存放二叉樹的數(shù)據(jù)用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點在數(shù)組中的相對位置蘊含著結(jié)元素。結(jié)點在數(shù)組中的相對位置蘊含著結(jié)點之間的關(guān)系。點之間的關(guān)系。0000FE000DC0BA15141312111098765432100一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費。一般二叉樹必須按

14、完全二叉樹的形式存儲，將造成存儲的浪費。typedef TElemType SqBiTreeMAX_TREE_SIZE+1; / 0號單元未用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號單元存儲根結(jié)點二、二叉樹的鏈?zhǔn)酱鎯Ρ硎径?、二叉樹的鏈?zhǔn)酱鎯Ρ硎?. 1. 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表3 3雙親鏈表雙親鏈表4線索鏈表線索鏈表ADEBCF rootlchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)

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

16、t; /雙親指針雙親指針 TriTNode, *TriTree;0123456B2C0A -1D2E3F4 data parent結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):3 3雙親鏈表雙親鏈表LRTagLRRRL typedef struct BPTNode / 結(jié)點結(jié)構(gòu)結(jié)點結(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é)點數(shù)目結(jié)點數(shù)目 int root; / 根結(jié)點的

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

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

19、序遍歷左子樹，按先序遍歷右子樹。遍歷左子樹，按先序遍歷右子樹。中根遍歷中根遍歷(L D R):(L D R): 按中序遍歷左子樹，訪按中序遍歷左子樹，訪問根結(jié)點，按中序遍歷右子樹。問根結(jié)點，按中序遍歷右子樹。后根遍歷后根遍歷(L R D):(L R D): 按后序遍歷左子樹，按按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。后序遍歷右子樹，訪問根結(jié)點。 二叉樹為空時，執(zhí)行空二叉樹為空時，執(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)/采用二叉鏈表存儲結(jié)構(gòu)，先序遍歷二叉樹采用二叉鏈表存儲結(jié)構(gòu)，先序遍歷二叉樹b b / / 初始條件：二叉樹初始條件：二叉樹b b存在，存在， / / 操作結(jié)果：先序遞歸遍操作結(jié)果：先序遞歸遍歷歷b b，打印每，打印每個結(jié)個結(jié)點一點一次且僅一次次且僅一次 if (T) / b不空不空 print(“%c”,b-data); /先訪問根結(jié)點先訪問根結(jié)點 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é)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) TElemType data;/數(shù)據(jù)元素數(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é)點并進(jìn)棧的所有左結(jié)點并進(jìn)棧 top+; Sttop=p; p=p-lchild; if (top-1) p=Sttop;top-; /出棧出棧*p結(jié)點結(jié)點 printf(%c ,p-data); /訪問之訪問之 p=p-rchild; /掃描掃描*p的右孩子結(jié)點的右孩子結(jié)點 /end of while(top-1 | p!=NULL) 找找*b的最左下結(jié)點的最左下結(jié)點b五五、遍歷算法的應(yīng)用舉例遍歷算

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

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

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

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

27、構(gòu)造右子樹 typedef struct node / 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) TElemType data;/數(shù)據(jù)元素數(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é)點生成根結(jié)點 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é)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) TElemType data;/數(shù)據(jù)元素數(shù)據(jù)元素 struct node *lchild, *rchild; / 左右孩子指針左右孩子指針 BTNode; *BiTree 僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹，由遍歷序列確定二叉樹由遍歷序列確定二叉樹 如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？ 二叉樹的先序序列二叉樹的中序序列左子

29、樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根根由二叉樹的先序和中序序列確定二叉樹由二叉樹的先序和中序序列確定二叉樹a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列6.5線索二叉樹線索二叉樹 何謂線索二叉樹？何謂線索二叉樹？ 線索鏈表的遍歷算法線索鏈表的遍歷算法 如何建立線索鏈表？如何建立線索鏈表？一、一、何謂線索二叉樹？何謂線索二叉樹？遍歷二叉樹的結(jié)果是， 求得結(jié)點的一個線性序列。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)的二叉樹，稱作 “線索二叉樹線索二叉樹”包含 “線索” 的存儲結(jié)構(gòu)，稱作 “線索鏈線索鏈表表”A B C D E F G H K D C B E 意義：保存遍歷二叉樹后得到的線性序列，避免重復(fù)遍歷。意義：保存遍歷二叉樹后得到的線性序列，避免重復(fù)遍歷。對對線索鏈表線索鏈表中結(jié)點的約定：中結(jié)點的約定： 在二叉鏈表的結(jié)點中增加兩個標(biāo)志域增加兩個標(biāo)志域，規(guī)定如下：如此定義的二叉樹的存儲結(jié)構(gòu)稱作如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表線索鏈表”。左標(biāo)志左標(biāo)志ltag : 0 表示表示l

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

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

33、繼在中序線索化鏈表中結(jié)點的后繼 ？若若無右子樹，則為則為后繼線索后繼線索所指結(jié)點；否則為否則為對其右子樹右子樹進(jìn)行中序遍歷遍歷時訪問的第一個結(jié)點。第一個結(jié)點。 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é)點頭結(jié)點)的非遞歸算法的非遞歸算法 TBTNode *p=tb-lchild;/*p指向根結(jié)點指向根結(jié)點*/ while (p!=tb)/非非空樹或遍歷未結(jié)束時空樹或遍歷未結(jié)束時 while (p-ltag=0) p=p-lchild;/*找開始結(jié)點找開始結(jié)點*/ printf(%c,p-data);/*訪問開始結(jié)點訪問開始結(jié)點*/ while (p-rtag=1 & p-rchild!=tb) / p-rchild是線索是線索(后繼后繼)，且不是遍歷的最后一個結(jié)點

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

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

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

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

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

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

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

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

43、pre指向指向p p的前驅(qū)的前驅(qū)Thread(p-rchild); /遞歸調(diào)用右子樹線索化遞歸調(diào)用右子樹線索化 6.6 樹和森林樹和森林 的表示方法的表示方法樹的三種存儲結(jié)構(gòu)樹的三種存儲結(jié)構(gòu)一、一、雙親表示法雙親表示法二、二、孩子鏈表表示法孩子鏈表表示法三、三、樹的二叉鏈表樹的二叉鏈表( (孩子孩子- -兄弟）兄弟） 存儲表示法存儲表示法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é)點的位置和結(jié)點個數(shù) PTree;結(jié)點結(jié)構(gòu)結(jié)點結(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é)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C語言的類型描述語言的類型描述: :typedef struct PTNode nodes MAX_TREE_SIZE; int r

45、, n; / 根結(jié)點的位置和結(jié)點個數(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é)點結(jié)構(gòu)孩子結(jié)點結(jié)構(gòu): child nextC語言的類型描述語言的類型描述: :雙親結(jié)點結(jié)構(gòu)雙親結(jié)點結(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é)點數(shù)和根結(jié)點的位置 CTree;ABCDEFG AB C E D F Groot AB C E D F G 三、樹的二叉鏈表三、樹的二叉鏈表 (孩子孩子-兄弟）存儲表示法兄弟）存儲表示法 firstchild data nextsibling結(jié)點結(jié)構(gòu)結(jié)點結(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é)點結(jié)構(gòu)結(jié)點結(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) 對樹中的每個結(jié)點，只保留其與第一個孩子結(jié)點之間的連線， 刪去其與其它孩子結(jié)點之間的連線。 (3) 以樹的根結(jié)點為軸心，將整棵樹順時針旋轉(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、(孩子孩子-兄弟）兄弟）存儲表示法存儲表示法二叉樹二叉鏈表二叉樹二叉鏈表存儲表示法存儲表示法 2. 森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹 （1） 將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。 （2） 第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。 森林轉(zhuǎn)換為二叉樹的過程 森林轉(zhuǎn)換后的二叉樹，其根結(jié)點有右孩子由森林轉(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é)點是其雙親的左孩子，則把該結(jié)點的右

51、孩子、若某結(jié)點是其雙親的左孩子，則把該結(jié)點的右孩子、 右孩子的右孩子右孩子的右孩子都與該結(jié)點的雙親結(jié)點用線連起來。都與該結(jié)點的雙親結(jié)點用線連起來。 （2 2） 刪掉原二叉樹中所有雙親結(jié)點與右孩子結(jié)點的連線。刪掉原二叉樹中所有雙親結(jié)點與右孩子結(jié)點的連線。 （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)樹的定義樹的路徑長度樹的路徑長度定義為： 樹中每個結(jié)點的路徑長度之和。 結(jié)點的路徑長度結(jié)點的路徑長度定義為： 從根結(jié)點到該結(jié)點的路徑上 分支的數(shù)目。 樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度定義為： 樹中所有葉子結(jié)點的帶權(quán)路徑長度結(jié)點的帶權(quán)路徑長度之和 WPL(T) = wklk (對所有葉子結(jié)點)。 在所有含 n 個葉子結(jié)點、并帶相同權(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 個權(quán)值個權(quán)值 w1, w2, , wn， 構(gòu)造構(gòu)造 n 棵二叉樹的集棵二叉樹的集合合F = T1, T2, , Tn，其中每棵二叉樹中均只含一個帶權(quán)值為，其中每棵二叉樹中均

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