ch6 樹和二叉樹

1、1第第6章章 樹和二叉樹樹和二叉樹（ Tree & Binary Tree ）6.1 樹的基本概念樹的基本概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其應用赫夫曼樹及其應用特點：特點：非線性結構，一個直接前驅，但可能有多個非線性結構，一個直接前驅，但可能有多個直接后繼直接后繼（1：n）26.1 樹的基本概念1. 樹的定義和表示樹的定義和表示2. 樹的若干術語樹的若干術語3. 樹的邏輯結構樹的邏輯結構4. 樹的存儲結構樹的存儲結構5. 樹的運算樹的運算31. 樹的定義樹的定義注注1：過去許多書籍中都定義樹為過去許多書籍中都

2、定義樹為n1，曾經(jīng)有，曾經(jīng)有“空樹不是空樹不是 樹樹”的說法，但現(xiàn)在樹的定義已修改。的說法，但現(xiàn)在樹的定義已修改。注注2：樹的定義具有樹的定義具有遞歸性遞歸性，即樹中還有樹。，即樹中還有樹。由由0個或多個個或多個(n0)結點組成的有限集合結點組成的有限集合T T，有且僅，有且僅有有一個結點稱為根一個結點稱為根（root），），當當n1時，其余的結點分時，其余的結點分為為m(m0)個個互不相交互不相交的有限集合的有限集合T1,T2，Tm。每。每個集合本身又是棵樹，被稱作這個根的個集合本身又是棵樹，被稱作這個根的子樹子樹 。6.1 樹的基本概念4樹的表示法有幾種：樹的表示法有幾種：圖形表示法圖形表

3、示法嵌套集合表示法嵌套集合表示法廣義表表示法廣義表表示法目錄表示法目錄表示法左孩子右兄弟表示法左孩子右兄弟表示法這些表示法的示意圖這些表示法的示意圖參見教材參見教材P120樹的抽象數(shù)據(jù)類型定義樹的抽象數(shù)據(jù)類型定義參參見教材見教材P118-1196.1 樹的基本概念5圖形表示法：圖形表示法：教師教師學生學生其他人員其他人員20082008級級20092009級級 20102010級級20112011級級河南大學河南大學數(shù)學學院數(shù)學學院計算機學院計算機學院物理學院物理學院葉子葉子根根子樹子樹6廣義表表示法廣義表表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H

4、 ( M ), I, J ) ) 根作為根作為由子樹森林組成的由子樹森林組成的表的名字寫在表的左邊表的名字寫在表的左邊datalink 1 link 2.link n麻煩問題：應當開設多少個鏈域麻煩問題：應當開設多少個鏈域?ABCGEIDHFJMLK6.1 樹的基本概念1. 樹的定義樹的定義7左孩子右兄弟表示法左孩子右兄弟表示法數(shù)據(jù)數(shù)據(jù)左孩子左孩子 右兄弟右兄弟ABCGEIDHFJMLK6.1 樹的基本概念1. 樹的定義樹的定義8數(shù)據(jù)對象數(shù)據(jù)對象 D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為空樹；為空集，則稱為空樹； 否則否則: (1) 在在D中

5、存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root, (2) 當當n1時，其余結點可分為時，其余結點可分為m (m0)個互不相交個互不相交 的有限集的有限集T1, T2, , Tm, 其中每一棵子集本身又其中每一棵子集本身又 是一棵符合本定義的樹，稱為根是一棵符合本定義的樹，稱為根root的子樹。的子樹。 數(shù)據(jù)關系數(shù)據(jù)關系 R： 樹的抽象數(shù)據(jù)類型定義樹的抽象數(shù)據(jù)類型定義（見教材（見教材P118-119）6.1 樹的基本概念1. 樹的定義樹的定義9 基本操作：基本操作：查查 找找 類類 插插 入入 類類刪刪 除除 類類6.1 樹的基本概念10Root(T) / 求樹的根結點求樹的根結

6、點 查找類：查找類：Value(T, cur_e) / 求當前結點的元素值求當前結點的元素值 Parent(T, cur_e) / 求當前結點的雙親結點求當前結點的雙親結點LeftChild(T, cur_e) / 求當前結點的最左孩子求當前結點的最左孩子 RightSibling(T, cur_e) / 求當前結點的右兄弟求當前結點的右兄弟TreeEmpty(T) / 判定樹是否為空樹判定樹是否為空樹 TreeDepth(T) / 求樹的深度求樹的深度TraverseTree( T, Visit() ) / 遍歷遍歷6.1 樹的基本概念11InitTree(&T) / 初始化置空樹初始化置空

7、樹 插入類：插入類：CreateTree(&T, definition) / 按定義構造樹按定義構造樹Assign(T, cur_e, value) / 給當前結點賦值給當前結點賦值InsertChild(&T, &p, i, c) / 將以將以c為根的樹插入為結點為根的樹插入為結點p的第的第i棵子樹棵子樹6.1 樹的基本概念12 ClearTree(&T) / 將樹清空將樹清空 刪除類：刪除類：DestroyTree(&T) / 銷毀樹的結構銷毀樹的結構DeleteChild(&T, &p, i) / 刪除結點刪除結點p的第的第i棵子樹棵子樹6.1 樹的基本概念132. 若干術語若干術語即上

8、層的那個結點即上層的那個結點(直接前驅直接前驅)即下層結點的子樹的根即下層結點的子樹的根(直接后繼直接后繼)同一雙親下的同層結點（孩子之間互稱兄弟）同一雙親下的同層結點（孩子之間互稱兄弟）即雙親位于同一層的結點（但并非同一雙親）即雙親位于同一層的結點（但并非同一雙親）即從根到該結點所經(jīng)分支的所有結點即從根到該結點所經(jīng)分支的所有結點即該結點下層子樹中的任一結點即該結點下層子樹中的任一結點ABCGEIDHFJMLK 根根 葉子葉子 森林森林有序樹有序樹有向樹有向樹無序樹無序樹即根結點即根結點(沒有前驅沒有前驅)即終端結點即終端結點(沒有后繼沒有后繼)指指m棵不相交的樹的集棵不相交的樹的集合合(例如

9、刪除例如刪除A后的子樹個數(shù)后的子樹個數(shù))雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孫子孫子樹從左至右有序，不能互換（左為第一）。子樹從左至右有序，不能互換（左為第一）。有確定的根，樹根和子樹根之間為有向關系。有確定的根，樹根和子樹根之間為有向關系。結點各子樹可互換位置。結點各子樹可互換位置。142. 若干術語（續(xù)）若干術語（續(xù)）即樹的數(shù)據(jù)元素即樹的數(shù)據(jù)元素結點掛接的子樹數(shù)結點掛接的子樹數(shù)（有幾個直接后繼就是幾度，（有幾個直接后繼就是幾度，亦稱亦稱“次數(shù)次數(shù)”）結點結點結點的度結點的度結點的層次結點的層次終端結點終端結點分支結點分支結點樹的度樹的度樹的深度樹的深度(或高度或高度)ABCGEI

10、DHFJMLK從根到該結點的層數(shù)（根結點算第一層）從根到該結點的層數(shù)（根結點算第一層）即度為即度為0的結點，即葉子的結點，即葉子即度不為即度不為0的結點（也稱為內部結點）的結點（也稱為內部結點）所有結點度中的最大值（所有結點度中的最大值（Max各結點的度各結點的度）指所有結點中最大的層數(shù)（指所有結點中最大的層數(shù)（Max各結點的層次各結點的層次）問：問：右上圖中的結點數(shù)右上圖中的結點數(shù) ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4153. 樹的邏輯結構樹的邏輯結構 ( (特點特點) )： 一對多（一對多（1:n1:n），有多個直接后繼（如家譜），有多個直接后繼（如家譜樹、目錄樹等等

11、），但只有一個根結點，樹、目錄樹等等），但只有一個根結點，且且子樹之間互不相交子樹之間互不相交。 4. 樹的存儲結構樹的存儲結構 討論討論1：樹是非線性結構，該怎樣存儲？樹是非線性結構，該怎樣存儲？仍然有順序存儲、鏈式存儲等方式。仍然有順序存儲、鏈式存儲等方式。 16討論討論3：樹的樹的鏈式存儲鏈式存儲方案應該怎樣制定？方案應該怎樣制定？可規(guī)定為：可規(guī)定為：從上至下、從左至右從上至下、從左至右將樹的結點依次存入內存。將樹的結點依次存入內存。重大缺陷：重大缺陷：復原困難（不能唯一復原就沒有實用價值）。復原困難（不能唯一復原就沒有實用價值）。討論討論2：樹的樹的順序存儲順序存儲方案應該怎樣制定？方

12、案應該怎樣制定？可用多重鏈表：可用多重鏈表：一個前趨指針，一個前趨指針，n n個后繼指針。個后繼指針。細節(jié)問題：細節(jié)問題：樹中結點的結構類型樣式該如何設計？樹中結點的結構類型樣式該如何設計？ 即應該設計成即應該設計成“等長等長”還是還是“不等長不等長”？缺點：缺點：等長結構太浪費（每個結點的度不一定相同）；等長結構太浪費（每個結點的度不一定相同）； 不等長結構太復雜（要定義好多種結構類型）。不等長結構太復雜（要定義好多種結構類型）。解決思路：解決思路：先研究最簡單、最有規(guī)律的樹，然后設法把先研究最簡單、最有規(guī)律的樹，然后設法把一般的樹轉化為簡單樹。一般的樹轉化為簡單樹。175. 樹的運算樹的運

13、算 要明確：要明確：1. 普通樹（即多叉樹）若不轉化為二叉樹，則運普通樹（即多叉樹）若不轉化為二叉樹，則運算很難實現(xiàn)。算很難實現(xiàn)。2. 二叉樹的運算仍然是插入、刪除、修改、查找、二叉樹的運算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在排序等，但這些操作必須建立在對樹結點能夠對樹結點能夠“遍歷遍歷”的基礎上！的基礎上?。ū闅v遍歷指每個結點都被訪問且僅訪問一次，指每個結點都被訪問且僅訪問一次，不遺漏不重復）。不遺漏不重復）。本章重點：二叉樹的表示和實現(xiàn)本章重點：二叉樹的表示和實現(xiàn)186.2 二叉樹二叉樹為何要重點研究每結點最多只有兩個為何要重點研究每結點最多只有兩個 “叉叉” 的樹？

14、的樹？ 二叉樹的結構最簡單，規(guī)律性最強；二叉樹的結構最簡單，規(guī)律性最強； 可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性。可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性。1. 二叉樹的定義二叉樹的定義2. 二叉樹的性質二叉樹的性質3. 二叉樹的存儲結構二叉樹的存儲結構（二叉樹的運算（二叉樹的運算見見6.3節(jié)節(jié)）191. 二叉樹的定義二叉樹的定義定義：定義：是是n（n0）個結點的有限集合，由一個根結點以及兩棵個結點的有限集合，由一個根結點以及兩棵互不相交的、分別稱為互不相交的、分別稱為左子樹和右子樹左子樹和右子樹的二叉樹組成的二叉樹組成 。邏輯結構：邏輯結構： 一對二（一對二（1：2

15、） 基本特征基本特征: : 每個結點最多只有兩棵子樹（不存在度大于每個結點最多只有兩棵子樹（不存在度大于2 2的結點）；的結點）； 左子樹和右子樹次序不能顛倒（有序樹）。左子樹和右子樹次序不能顛倒（有序樹）?；拘螒B(tài)：基本形態(tài)： 5種種/2種種20二叉樹的抽象數(shù)據(jù)類型定義二叉樹的抽象數(shù)據(jù)類型定義（見教材（見教材P121-122）ADT BinaryTree數(shù)據(jù)對象數(shù)據(jù)對象D:數(shù)據(jù)關系數(shù)據(jù)關系R:基本操作基本操作 P：ADT BinaryTree若若D=，則，則R= ；若若D，則，則R= H；存在二元關系：；存在二元關系： root 唯一唯一 /關于根的說明關于根的說明 DlDr= /關于子樹不

16、相交的說明關于子樹不相交的說明 /關于數(shù)據(jù)元素的說明關于數(shù)據(jù)元素的說明 /關于左子樹和右子樹的說明關于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。/至少有至少有20個個212. 二叉樹的性質二叉樹的性質(3+2)(3+2)討論討論1 1：第：第i i層的結點數(shù)至多是多少？層的結點數(shù)至多是多少？ （利用二進制性質可輕松求出）（利用二進制性質可輕松求出） 性質性質1: 1: 在二叉樹的第在二叉樹的第i層上至多有層上至多有個結點（個結點（i=1）。）。性質性質2: 2: 深度為深度為k的二叉樹至多有的二叉樹至多有個結點（個結點（k=1）。）。2i-1個個提問

17、：第提問：第i i層上至少有層上至少有 個結點？個結點？1 1討論討論2 2：深度為：深度為k k的二叉樹，至多有多少個結點？的二叉樹，至多有多少個結點？ （利用二進制性質可輕松求出）（利用二進制性質可輕松求出）2k-1提問：深度為提問：深度為k k時至少有時至少有 個結點？個結點？k k22討論討論3 3：二叉樹的葉子數(shù)和度為：二叉樹的葉子數(shù)和度為2 2的結點數(shù)之間有關系嗎？的結點數(shù)之間有關系嗎？性質性質3: 3: 對于任何一棵二叉樹，若對于任何一棵二叉樹，若2 2度的結點數(shù)有度的結點數(shù)有n n2 2個，個，則葉子數(shù)（則葉子數(shù)（n n0 0）必定為必定為n n2 21 1 （即（即n0=n2

18、+1）二叉樹中全部結點數(shù)二叉樹中全部結點數(shù)nn0+n1+n2( (葉子數(shù)葉子數(shù)1 1度結點數(shù)度結點數(shù)2 2度結點數(shù)度結點數(shù)) )二叉樹中全部結點數(shù)二叉樹中全部結點數(shù)nB+1 ( ( 總分支數(shù)根結點總分支數(shù)根結點 ) ) （除根結點外，每個結點必有一個直接前趨，即一個分支）（除根結點外，每個結點必有一個直接前趨，即一個分支）總分支數(shù)總分支數(shù)B= n1+2n2 (1(1度結點必有度結點必有1 1個直接后繼，個直接后繼，2 2度結點必有度結點必有2 2個個) )n0+n1+n2= n1+2n2 +1, 即即n0=n2+1實際意義：實際意義：葉子數(shù)葉子數(shù)2 2度結點數(shù)度結點數(shù)1 1ABCGEIDHFJ

19、23對于兩種特殊形式的二叉樹（對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹），），還特別具備以下還特別具備以下2 2個性質：個性質：性質性質4: 4: 具有具有n n個結點的完全二叉樹的深度必為個結點的完全二叉樹的深度必為loglog2 2nn1 1性質性質5: 5: 對完全二叉樹，若從上至下、從左至右編號，對完全二叉樹，若從上至下、從左至右編號，則編號為則編號為i 的結點，其左孩子編號必為的結點，其左孩子編號必為2i，其右孩子編號，其右孩子編號必為必為2i1；其雙親的編號必為；其雙親的編號必為i/2（i1 時為根時為根, ,除外除外）。）。 證明：證明：根據(jù)性質根據(jù)性質

20、2 2，深度為，深度為k k的二叉樹最多只有的二叉樹最多只有2 2k k-1-1個結點，且完全二叉樹個結點，且完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它的總結點數(shù)的定義是與同深度的滿二叉樹前面編號相同，即它的總結點數(shù)n n位于位于k k層和層和k-1k-1層滿二叉樹容量之間，即層滿二叉樹容量之間，即 2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n n 2 2k k三邊同時取對數(shù)，于是有：三邊同時取對數(shù)，于是有：k-1logk-1log2 2nk ndata); /訪問訪問D DLR(root-lchild); /遞歸遍歷左子樹遞歸遍歷左子樹 DLR(r

21、oot-rchild); /遞歸遍歷右子樹遞歸遍歷右子樹 return(0); 二叉樹結點數(shù)據(jù)類型定義：二叉樹結點數(shù)據(jù)類型定義：typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;則三種遍歷算法可寫出則三種遍歷算法可寫出: :2. 二叉樹二叉樹遍歷算法的遞歸實現(xiàn)遍歷算法的遞歸實現(xiàn) 43中序遍歷算法中序遍歷算法 LDR (BiTNode *root) if (root !=NULL) LDR(root-lchild); printf (“%d”,root-data); L

22、DR(root-rchild); return(0); 后序遍歷算法后序遍歷算法 LRD (BiTNode *root) if (root !=NULL) LRD(root-lchild); LRD(root-rchild); printf (“%d”,root-data); return(0); 2. 二叉樹二叉樹遍歷算法的遞歸實現(xiàn)遍歷算法的遞歸實現(xiàn) 44對遍歷的分析：對遍歷的分析：1. 從前面的三種遍歷算法可以知道：從前面的三種遍歷算法可以知道：如果將如果將print語句抹去，語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種從遞歸的角度看，這三種算法是完全相同的，或者說這三種

23、遍歷算法的遍歷算法的訪問路徑是相同的，只是訪問結點的時機不同訪問路徑是相同的，只是訪問結點的時機不同。從虛線的出發(fā)點到終點的路徑從虛線的出發(fā)點到終點的路徑上，每個結點經(jīng)過上，每個結點經(jīng)過3次次。AFEDCBG第第1次經(jīng)過時訪問先序遍歷次經(jīng)過時訪問先序遍歷第第2次經(jīng)過時訪問中序遍歷次經(jīng)過時訪問中序遍歷第第3次經(jīng)過時訪問后序遍歷次經(jīng)過時訪問后序遍歷2. 二叉樹遍歷的時間效率和空間效率二叉樹遍歷的時間效率和空間效率時間效率時間效率: : /每個結點只訪問一次每個結點只訪問一次空間效率空間效率: : /棧占用的最大輔助空間棧占用的最大輔助空間（精確值：樹深為（精確值：樹深為k k的遞歸遍歷需要的遞歸遍

24、歷需要k+1k+1個輔助單元?。﹤€輔助單元?。?5算法思路：算法思路：若不用遞歸，則要實現(xiàn)二叉樹遍歷的若不用遞歸，則要實現(xiàn)二叉樹遍歷的“嵌套嵌套”規(guī)則，規(guī)則， 必用堆棧。必用堆棧。參見教材參見教材P130-131程序。程序。Status InOrderTraverse ( Bitree T, Status (* Visit) (TElemType e) ) InitStack( S ); Push( S, T ); / 根指針進棧根指針進棧 while ( !StackEmpty(S) ) while( GetTop(S, p) & p) Push( S, p-lchild ); / 向左走到

25、盡頭向左走到盡頭 Pop( S, p ); / 空指針退?？罩羔樛藯?if ( !StackEmpty(S) ) / 訪問結點訪問結點, ,向右一步向右一步 Pop( S, p ); if (!Visit ( p-data ) ) return ERROR; Push ( S, p-rchild ); / 將右兒子入棧，則下次循環(huán)時打印右兒子將右兒子入棧，則下次循環(huán)時打印右兒子 / if /while return OK; / InOrderTraverse 3. 二叉樹二叉樹遍歷算法的非遞歸實現(xiàn)遍歷算法的非遞歸實現(xiàn) 46Status InorderTraverse ( BiTree T, S

26、tatus( *Visit) (TElemType e) InitStack( S ); p=T; while ( p | !StackEmpty(S) ) / 棧不空或樹不空棧不空或樹不空 if ( p ) Push(S,p); p= p-lchild; / 根指針進棧根指針進棧, ,遍歷左子樹遍歷左子樹 else / 根指針退棧根指針退棧, ,訪問根結點訪問根結點, ,遍歷右子樹遍歷右子樹 Pop( S,p); if ( !Visit( p-data) ) return ERROR; p = p-rchild; / else / while return OK; / InorderTrav

27、erse 47例例5 判斷二叉樹是否為完全二叉樹判斷二叉樹是否為完全二叉樹4. 二叉樹二叉樹遍歷算法的應用舉例遍歷算法的應用舉例例例1 統(tǒng)計二叉樹中葉子結點的個數(shù)統(tǒng)計二叉樹中葉子結點的個數(shù)例例3 求二叉樹的深度求二叉樹的深度例例4 按層次輸出二叉樹中的所有結點按層次輸出二叉樹中的所有結點例例2 創(chuàng)建一棵二叉樹創(chuàng)建一棵二叉樹48思路：思路：輸出葉子結點比較簡單，用任何一種遍歷算法，凡輸出葉子結點比較簡單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。 DLR (BiTNode *root) /采用先序遍歷的遞歸算法采用先序遍

28、歷的遞歸算法 if ( root!=NULL ) /非空二叉樹條件，還可寫成非空二叉樹條件，還可寫成if (root) if (!root-lchild & !root-rchild) /是葉子結點則統(tǒng)計并打印是葉子結點則統(tǒng)計并打印 sum+; printf (%dn, root-data); DLR (root-lchild); /遞歸遍歷左子樹，直到葉子處；遞歸遍歷左子樹，直到葉子處； DLR (root-rchild); /遞歸遍歷右子樹，直到葉子處；遞歸遍歷右子樹，直到葉子處； return(0); 例例1 統(tǒng)計二叉樹中葉子結點的個數(shù)統(tǒng)計二叉樹中葉子結點的個數(shù)49注：注：要實現(xiàn)遍歷運算

29、必須先把二叉樹存入機內。要實現(xiàn)遍歷運算必須先把二叉樹存入機內。思路：思路：利用利用前序前序遍歷來建樹遍歷來建樹（結點值陸續(xù)從鍵盤輸入，用（結點值陸續(xù)從鍵盤輸入，用DLR為宜）為宜）BiTNode createBTpre( ) BiTNode T; char ch; scanf (“%c”, &ch); if (ch=) T=NULL; else T=( Bintree ) malloc (sizeof (BinTNode); T-data=ch; T-lchild=createBTpre(); T-rchild=createBTpre(); return T;例例2 創(chuàng)建一棵二叉樹創(chuàng)建一棵二叉

30、樹50算法思路：算法思路：只查各結點后繼鏈表指針，若左只查各結點后繼鏈表指針，若左( (右右) )孩子孩子 的左的左( (右右) )指針非空，則層次數(shù)加指針非空，則層次數(shù)加1 1；否則；否則 函數(shù)返回。函數(shù)返回。當當T= NULLT= NULL時時, ,深度為深度為0;0;否則否則, T, T的深度的深度= MAX= MAX左子樹深度左子樹深度, ,右子樹深度右子樹深度+1;+1; 例例3 求二叉樹的深度求二叉樹的深度51算法思路：算法思路：既然要求從上到下，從左到右，則既然要求從上到下，從左到右，則利用利用 隊列隊列存放各子樹結點的指針是個好辦法，存放各子樹結點的指針是個好辦法， 而不必拘泥

31、于遞歸算法。而不必拘泥于遞歸算法。技巧：技巧：當根結點入隊后，令其左、右孩子結點入隊，當根結點入隊后，令其左、右孩子結點入隊， 而根結點以外的結點出隊時又令它的左右孩子而根結點以外的結點出隊時又令它的左右孩子 結點入隊，結點入隊，由此便可產生按層次輸出的效果。由此便可產生按層次輸出的效果。 A B CD E例例4 按層次輸出二叉樹中的所有結點按層次輸出二叉樹中的所有結點52算法思路：算法思路：完全二叉樹的特點是：沒有左子樹空而右完全二叉樹的特點是：沒有左子樹空而右 子樹單獨存在的情況子樹單獨存在的情況( (前前k-1k-1層都是滿的，層都是滿的， 且第且第k k層左邊也滿）層左邊也滿）。技巧技

32、巧: : 按層序遍歷方式，先把所有結點按層序遍歷方式，先把所有結點（不管當前結（不管當前結 點是否有左右孩子）點是否有左右孩子）都入隊列都入隊列. .若為完全二叉樹若為完全二叉樹, , 則層序遍歷時得到的肯定是一個則層序遍歷時得到的肯定是一個連續(xù)的不包含連續(xù)的不包含 空指針的序列空指針的序列. .如果序列中出現(xiàn)了空指針，則說如果序列中出現(xiàn)了空指針，則說 明不是完全二叉樹。明不是完全二叉樹。例例5 判斷二叉樹是否為完全二叉樹判斷二叉樹是否為完全二叉樹53問：問：用二叉鏈表法用二叉鏈表法（l_child, r_child）存儲包含存儲包含n個結點的個結點的 二叉樹，結點的指針區(qū)域中會有多少個空指針

33、？二叉樹，結點的指針區(qū)域中會有多少個空指針？分析：分析：用二叉鏈表存儲包含用二叉鏈表存儲包含n n個結點的二叉樹，結點必有個結點的二叉樹，結點必有2n 個鏈域個鏈域（見二叉鏈表數(shù)據(jù)類型說明）（見二叉鏈表數(shù)據(jù)類型說明）。思考：思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放 有用的信息或線索？有用的信息或線索？我們可以用它來存放當前結點的直接前驅和后繼等線索，我們可以用它來存放當前結點的直接前驅和后繼等線索， 以加快查找速度。以加快查找速度。所以，所以， 空指針數(shù)目空指針數(shù)目2n(n-1)=n+1個個。n+1 除根結點外，二叉樹中每一個結點除根結

34、點外，二叉樹中每一個結點有且僅有一個雙親有且僅有一個雙親（直接（直接前驅），所以只會有前驅），所以只會有n1個結點的鏈域存放指針，指向非空子個結點的鏈域存放指針，指向非空子女結點（即直接后繼）。女結點（即直接后繼）。54二.線索二叉樹線索二叉樹（Threaded Binary Tree）普通二叉樹只能找到結點的左右孩子信息，普通二叉樹只能找到結點的左右孩子信息，而該結點而該結點的直接前驅和直接后繼只能在遍歷過程中獲得。的直接前驅和直接后繼只能在遍歷過程中獲得。若將若將遍歷后遍歷后對應的有關前驅和后繼對應的有關前驅和后繼預存預存起來，則從起來，則從第第一個結點一個結點開始就能很快開始就能很快“順

35、藤摸瓜順藤摸瓜”而遍歷整個樹了。而遍歷整個樹了。兩種解決方法：兩種解決方法：增加兩個域：增加兩個域：fwd和和bwd；存放前驅指針存放前驅指針存放后繼指針存放后繼指針如何預存這類信息？如何預存這類信息？例如中序遍歷結果：例如中序遍歷結果：B D C E A F H G，實際上，實際上已將二叉已將二叉樹轉為樹轉為線性排列線性排列，顯然具有唯一前驅和唯一后繼。，顯然具有唯一前驅和唯一后繼。利用空鏈域（利用空鏈域（n+1個空鏈域）個空鏈域）55規(guī)定：規(guī)定：1）若結點有左子樹，則）若結點有左子樹，則lchild指向其左孩子；指向其左孩子； 否則，否則， lchild指向其直接前驅指向其直接前驅(即線索

36、即線索)；2）若結點有右子樹，則）若結點有右子樹，則rchild指向其右孩子；指向其右孩子； 否則，否則， rchild指向其直接后繼指向其直接后繼(即線索即線索) 。為區(qū)別兩種不同情況，特增加兩個標志域（各為區(qū)別兩種不同情況，特增加兩個標志域（各1bit)lchilddatarchild約定約定:當當Tag域為域為0時時,表示表示正常正常情況情況;當當Tag域為域為1時時,表示表示線索線索情況情況.右孩子或后繼右孩子或后繼左孩子或前驅左孩子或前驅LTagRTag1. 線索二叉樹的定義線索二叉樹的定義56附：有關線索二叉樹的幾個術語：附：有關線索二叉樹的幾個術語： 線索鏈表：線索鏈表：用用含含

37、Tag的結點樣式所構成的二叉鏈表的結點樣式所構成的二叉鏈表 線線 索：索：指向結點前驅和后繼的指針指向結點前驅和后繼的指針線索二叉樹：線索二叉樹：加上線索的二叉樹加上線索的二叉樹 線線 索索 化：化：對二叉樹以對二叉樹以某種次序遍歷某種次序遍歷使其變?yōu)榫€索二使其變?yōu)榫€索二叉樹的過程叉樹的過程討論：討論：增加了前驅和后繼等線索有什么好處？增加了前驅和后繼等線索有什么好處？能方便找出當前結點的前驅和后繼，不用能方便找出當前結點的前驅和后繼，不用堆棧也能遍歷整個樹。堆棧也能遍歷整個樹。1. 線索二叉樹的定義線索二叉樹的定義57data AGEIDJHCFBltag0011110101rtag0001

38、010111AGEIDJHCFB例：例：某某先序遍歷先序遍歷結果如下表所示，請畫出對應的結果如下表所示，請畫出對應的二叉樹。二叉樹。 （多帶了兩個標志！）（多帶了兩個標志?。?82. 線索二叉樹的生成線索二叉樹的生成線索化過程就是線索化過程就是在遍歷過程中修改空指針在遍歷過程中修改空指針的過程：的過程：將空的將空的lchild改為結點的直接前驅；改為結點的直接前驅；將空的將空的rchild改為結點的直接后繼。改為結點的直接后繼。非空指針呢？仍然指向孩子結點（稱為非空指針呢？仍然指向孩子結點（稱為“正常情況正常情況”）59ABCGEIDHFroot懸空？懸空？懸空？懸空？解：解：該二叉樹中序遍歷

39、結果為該二叉樹中序遍歷結果為: : H, D, I, B, E, A, F, C, G所以添加線索應當按如下路徑進行：所以添加線索應當按如下路徑進行：為避免懸空為避免懸空態(tài)，應增設態(tài)，應增設一個頭結點一個頭結點例例1 1：畫出以下二叉樹對應的畫出以下二叉樹對應的中序中序線索二叉樹。線索二叉樹。6000A00C00B11E11F11G00D11I11H注：注：此圖中序遍歷結果為此圖中序遍歷結果為: : H, D, I, B, E, A, F, C, G0-root0對應的中序線索二叉樹存儲結構如圖所示：對應的中序線索二叉樹存儲結構如圖所示：61例例2：給定如圖所示二叉樹給定如圖所示二叉樹T T，

40、請畫出與其對應的，請畫出與其對應的中序線索二叉樹。中序線索二叉樹。 2825405560330854解解: :因為中序遍歷序列是：因為中序遍歷序列是：55 40 25 60 28 08 33 54對應線索樹應當按此規(guī)律連線，即對應線索樹應當按此規(guī)律連線，即在原二叉樹中添加虛線。在原二叉樹中添加虛線。NILNILNILNIL62線索二叉樹的生成算法線索二叉樹的生成算法（算法算法6.6, 見教材見教材P134）目的：目的：在依某種順序遍歷二叉樹時修改空指針，添加前驅或后繼。在依某種順序遍歷二叉樹時修改空指針，添加前驅或后繼。注解：注解：為方便添加結點的前驅或后繼，需要設置兩個指針：為方便添加結點的

41、前驅或后繼，需要設置兩個指針： p指針指針當前結點之指針；當前結點之指針； pre指針指針前驅結點之指針。前驅結點之指針。技巧：技巧：當結點當結點p的左的左/右域為空右域為空時，只改寫它的左域（裝入前驅時，只改寫它的左域（裝入前驅pre），而其右域（后繼）留給下一結點來填寫。，而其右域（后繼）留給下一結點來填寫。 或者說，當前結點的指針或者說，當前結點的指針p應當送到前驅結點的空右域中。應當送到前驅結點的空右域中。若若p-lchildNULL, ,則則p-p-LtagLtag=1;=1;p-p-l lchildchildpre; ; /p/p的前驅結點指針的前驅結點指針pre存入左空域存入左空

42、域若若pre-rchildNULL, 則則pre-pre-RtagRtag1;pre-rchild=p; /p存入其前驅結點存入其前驅結點pre的右的右空域空域63Status InorderThreading(BiThrTree & Thrt, BiThrTree T) /中序遍歷二叉樹中序遍歷二叉樹T,并將其中序線索化并將其中序線索化, Thrt 指向頭結點指向頭結點. if ( ! (Thrt = (BiThrTree) malloc ( sizeof (BiThrnode) ) ) exit ( OVERFLOW ) ; Thrt -LTag = Link; Thrt -RTag =

43、Thead; / 建頭結點建頭結點 Thrt -rchild = Thrt ; /右指針回指右指針回指 if ( !T ) Thrt -lchild = Thrt ; / 若二叉樹空若二叉樹空,則左指針回指則左指針回指 else Thrt -lchild = T; pre = Thrt; /將頭結點與樹相連將頭結點與樹相連 InThreading(T); / 中序遍歷進行中序線索化中序遍歷進行中序線索化 pre -rchild = Thrt; pre -RTag = Thread; /最后一個結點線索化最后一個結點線索化 Thrt -rchild = pre; return OK; / InO

44、rderThreading64void InThreading (BiThrTree p) if (p) InThreading( p-lchild ); / 左子樹線索化左子樹線索化 if ( !p-lchild ) p-LTag=Thread; p-lchild=pre; / 前驅線索前驅線索 if ( !pre-rchild ) pre-RTag=Thread; pre-rchild=p; /后繼線索后繼線索 pre = p; / 保持保持pre指向指向p的前驅的前驅 InThreading(p-rchild); /右子樹線索化右子樹線索化 / InThreading653. 線索二叉樹

45、的遍歷線索二叉樹的遍歷理論上，只要找到序列中的理論上，只要找到序列中的第一個結點第一個結點，然后，然后依次訪依次訪問結點的后繼問結點的后繼直到后繼為空時結束。直到后繼為空時結束。在線索化二叉樹中，并不是每個結點都能直接找到其在線索化二叉樹中，并不是每個結點都能直接找到其后繼的，后繼的，當標志為當標志為0時，時，R_child= =右孩子地址指針，并非后繼！右孩子地址指針，并非后繼！需要通過一定運算才能找到它的后繼。需要通過一定運算才能找到它的后繼。以以中序線索二叉樹中序線索二叉樹為例：為例：對葉子結點（對葉子結點（RTag=1），直接后繼指針就在其），直接后繼指針就在其rchild域內；域內；

46、對其他結點（對其他結點（RTag=0），直接后繼是其），直接后繼是其右子樹最左下的結點右子樹最左下的結點；（因為中序遍歷規(guī)則是（因為中序遍歷規(guī)則是LDR，）66 Status InorderTraverse_Thr(BiThrTree T) P=T-lchild; /p指向根結點；指向根結點； while( p!=T) / 空樹或遍歷結束時，空樹或遍歷結束時，p=T while (p-LTag=link) p=p-lchild; /先找到中序遍歷起點先找到中序遍歷起點 if (!visit(p-data) return ERROR; /訪問最左結點訪問最左結點 while(p-RTag=Thr

47、ead & p-rchild!=T) /p-rchild=T即為最后一個結點即為最后一個結點 p=p-rchild; Visit(p-data); /若有后繼標志，則直接提取若有后繼標志，則直接提取p-rchild中線索并訪問后繼結點；中線索并訪問后繼結點； p=p-rchild; /當前結點右域不空當前結點右域不空或或已經(jīng)找好了后繼已經(jīng)找好了后繼，則一律從結點，則一律從結點的右子樹開始重復的右子樹開始重復 的全部過程。的全部過程。 return OK; / InOrderTraverse_Thr線索二叉樹的線索二叉樹的中序中序遍歷算法遍歷算法（算法算法6.5, 參見教材參見教材P134）67

48、算法流程：算法流程：return OK;p=T-lchild;p!=Tp-LTag=0p=p-lchild;vist(p-data);p-LTag=1&p-rchild!=Tp=p-rchild;visit(p-data);p=p-rchild;YNYNYN演演示示程程序序686.4 樹和森林樹和森林一一. 樹和森林與二叉樹的轉換樹和森林與二叉樹的轉換二二. 樹和森林的存儲方式樹和森林的存儲方式三三. 樹和森林的遍歷樹和森林的遍歷69一一. .樹和森林與二叉樹的轉換樹和森林與二叉樹的轉換轉換步驟：轉換步驟：step1: 將樹中同一結點的兄弟相連將樹中同一結點的兄弟相連; ;step2: 保留結

49、點的最左孩子連線，刪除其它孩保留結點的最左孩子連線，刪除其它孩子連線；子連線；step3: 將同一孩子的連線繞左孩子旋轉將同一孩子的連線繞左孩子旋轉4545度角。度角。加線加線抹線抹線旋轉旋轉討論討論1：樹如何轉為二叉樹？樹如何轉為二叉樹？70方法：方法：加加線線抹線抹線旋轉旋轉 abeidfhgc樹轉二叉樹舉例：樹轉二叉樹舉例：abeidfhgc兄弟相連兄弟相連長兄為父長兄為父孩子靠左孩子靠左71討論討論2：二叉樹怎樣還原為樹？二叉樹怎樣還原為樹？abeidfhgc要點：把所有右孩子變?yōu)樾值?！要點：把所有右孩子變?yōu)樾值埽?abeidfhgc72法一：法一： 各森林先各自轉為二叉樹；各森林先各

50、自轉為二叉樹； 依次連到前一個二叉樹的右子樹上。依次連到前一個二叉樹的右子樹上。討論討論3：森林如何轉為二叉樹？森林如何轉為二叉樹？法二：法二：森林直接變兄弟，再轉為二叉樹森林直接變兄弟，再轉為二叉樹（參見教材（參見教材P138圖圖6.17，兩種方法都有轉換示意圖），兩種方法都有轉換示意圖）即即F=T1, T2, ,Tm B=root, LB, RB73ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林轉二叉樹舉例：森林轉二叉樹舉例：（法二）（法二）兄弟相連兄弟相連 長兄為父長兄為父孩子靠左孩子靠左 頭根為根頭根為根 74討論討論4 4：二叉樹如何還原為森林？：二叉樹如何還原為森林

51、？要點：要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值馨炎钣疫叺淖訕渥優(yōu)樯?，其余右子樹變?yōu)樾值?ABCDEFGHJIABCDEFGHJIEFABCDGHJI即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, , ,T,Tm m 75二二. .樹和森林的存儲方式樹和森林的存儲方式樹有三種常用存儲方式：樹有三種常用存儲方式：雙親表示法雙親表示法 孩子表示法孩子表示法 孩子兄弟表示法孩子兄弟表示法 (1)(1)用雙親表示法來存儲用雙親表示法來存儲思路：思路：用一組用一組連續(xù)空間連續(xù)空間來存儲樹的結點，同時在每個來存儲樹的結點，同時在每個結點中結

52、點中附設一個指示器附設一個指示器，指示其雙親結點在鏈表中的，指示其雙親結點在鏈表中的位置。位置。parentsdata結點結構結點結構dataparents1樹結構樹結構 23n76缺點：求結點的孩子時需要遍歷整個結構。缺點：求結點的孩子時需要遍歷整個結構。01234567812233ABCDEFGHI-1001例例1: 雙親表示法雙親表示法77思路：思路：將每個結點的孩子排列起來，形成一個帶表頭將每個結點的孩子排列起來，形成一個帶表頭（裝父結點）的線性表（裝父結點）的線性表（n n個結點要設立個結點要設立n n個鏈表）；個鏈表）；再將再將n n個表頭用數(shù)組存放起來，這樣就形成一個混合個表頭用

53、數(shù)組存放起來，這樣就形成一個混合結構。結構。例如例如：abecdfhgdefghgfedcbah12345678(2)(2)用孩子表示法來存儲用孩子表示法來存儲bc78思路：思路：用二叉鏈表來表示樹，但鏈表中的兩個用二叉鏈表來表示樹，但鏈表中的兩個指針域含義不同。指針域含義不同。左指針指向該結點的第一個孩子；左指針指向該結點的第一個孩子；右指針指向該結點的下一個兄弟結點。右指針指向該結點的下一個兄弟結點。nextsiblingdatafirstchild(3)(3)用孩子兄弟表示法來存儲用孩子兄弟表示法來存儲指向左孩子指向左孩子指向右兄弟指向右兄弟79abecdfhgbacedfgh問：問：樹

54、樹二叉樹的二叉樹的“連線連線抹線抹線旋轉旋轉” 如如何由計算機自動實現(xiàn)？何由計算機自動實現(xiàn)？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法來存儲即可。表示法來存儲即可。 例如例如：801. 樹的遍歷樹的遍歷:按層次遍歷按層次遍歷:先根先根(次序次序)遍歷遍歷:后根后根(次序次序)遍歷遍歷:若樹不空，則先訪問根結點，然后依次先根遍歷各若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹?？米訕洹Ｈ魳洳豢眨瑒t先依次后根遍歷各棵子樹，然后訪問根若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。結點。若樹不空，則自上而下自左至右訪問樹中每個結點。若樹不空，則自上而下自左至右訪問樹中每個結點。三三. .

55、樹和森林的遍歷樹和森林的遍歷81 A B C DE F G H I J K層次遍歷時頂點的訪問次序：層次遍歷時頂點的訪問次序： 先根遍歷時頂點的訪問次序：先根遍歷時頂點的訪問次序：A B E F C D G H I J K后根遍歷時頂點的訪問次序：后根遍歷時頂點的訪問次序：E F B C I J K H G D AA B C D E F G H I J K82層次遍歷時頂點的訪問次序：層次遍歷時頂點的訪問次序： A B C DE F G H I J K先根遍歷時頂點的訪問次序：先根遍歷時頂點的訪問次序：A B E F C D G H I J K后根遍歷時頂點的訪問次序：后根遍歷時頂點的訪問次序

56、：E F B C I J K H G D AA B C D E F G H I J K83 B C DE F G H I J K1. .森林中第一棵樹的根結點；森林中第一棵樹的根結點；2. .森林中第一棵樹的子樹森林中第一棵樹的子樹 森林；森林；3. .森林中其它樹構成的森林。森林中其它樹構成的森林。可以分解成三部分：可以分解成三部分：2. 森林的遍歷森林的遍歷84若森林不空，則若森林不空，則訪問森林中第一棵樹的根結點訪問森林中第一棵樹的根結點;先序遍歷先序遍歷森林中第一棵樹的子樹森林森林中第一棵樹的子樹森林;先序遍歷先序遍歷森林中森林中(除第一棵樹之外除第一棵樹之外)其余樹構成的森林。其余樹

57、構成的森林。先序遍歷先序遍歷2. 森林的遍歷森林的遍歷即：依次從左至右對森林中的每一棵即：依次從左至右對森林中的每一棵樹樹進行進行先根遍歷先根遍歷。85 中序遍歷中序遍歷若森林不空，則若森林不空，則中序遍歷中序遍歷森林中第一棵樹的子樹森林森林中第一棵樹的子樹森林;訪問森林中第一棵樹的根結點訪問森林中第一棵樹的根結點;中序遍歷中序遍歷森林中森林中(除第一棵樹之外除第一棵樹之外)其余樹構成的森林。其余樹構成的森林。即：依次從左至右對森林中的每一棵即：依次從左至右對森林中的每一棵樹樹進行進行后根遍歷后根遍歷。2. 森林的遍歷森林的遍歷86 樹的遍歷和二叉樹遍歷樹的遍歷和二叉樹遍歷的對應關系的對應關系

58、 ？先根遍歷先根遍歷后根遍歷后根遍歷樹樹二叉樹二叉樹森林森林先序遍歷先序遍歷先序遍歷先序遍歷中序遍歷中序遍歷中序遍歷中序遍歷876.5 Huffman樹及其應用樹及其應用一、最優(yōu)二叉樹（一、最優(yōu)二叉樹（赫夫曼赫夫曼樹）樹）二、二、Huffman樹的構造樹的構造三、三、Huffman編碼編碼88路路 徑徑：路徑長度路徑長度：樹的路徑長度樹的路徑長度：帶權路徑長度帶權路徑長度：樹的帶權路徑長度樹的帶權路徑長度：赫赫 夫夫 曼曼 樹：樹：一一. .最優(yōu)二叉樹（最優(yōu)二叉樹（赫夫曼赫夫曼樹）樹）由一結點到另一結點間的分支所構成。由一結點到另一結點間的分支所構成。路徑上的分支數(shù)目。路徑上的分支數(shù)目。從樹根

59、到從樹根到每一結點每一結點的路徑長度之和。的路徑長度之和。結點到根的路徑長度與結點上權的乘積。結點到根的路徑長度與結點上權的乘積。debacf g樹中所有樹中所有葉子結點葉子結點的帶權路徑長度之和。的帶權路徑長度之和。帶權路徑長度最小的樹。帶權路徑長度最小的樹。ae的路徑長度的路徑長度樹長度樹長度2106.5 Huffman樹及其應用樹及其應用89Huffman樹簡介：樹簡介：樹的帶權路徑長度如何計算？樹的帶權路徑長度如何計算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)WPL=36WPL=46WPL= 3

60、5哈夫曼樹則是：哈夫曼樹則是：WPL WPL 最小的樹。最小的樹。Huffman樹樹Weighted Path Length90構造赫夫曼樹的基本思想：構造赫夫曼樹的基本思想：二二. .Huffman樹的構造樹的構造構造構造Huffman樹的步驟（即樹的步驟（即Huffman算法）：算法）：91二二. .Huffman樹的構造樹的構造構造構造Huffman樹的步驟（即樹的步驟（即Huffman算法）：算法）：92設有設有4個字符個字符d,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2,4， 怎樣編碼才能使它們組成的報文在網(wǎng)絡中傳得最快？怎樣編碼才能使它們組成的報文在網(wǎng)絡中傳得最快？法