數(shù)據(jù)結(jié)構(gòu)詳細(xì)教案——樹與二叉樹

1、第 0 頁數(shù)據(jù)結(jié)構(gòu)教案第六章 樹與二叉樹第 21 頁數(shù)據(jù)結(jié)構(gòu)教案 第6章 樹與二叉樹目 錄6.1 樹的定義和基本術(shù)語16.2 二叉樹26.2.1 二叉樹的定義26.2.2 二叉樹的性質(zhì)46.2.3 二叉樹的存儲結(jié)構(gòu)56.3 樹和森林66.4 二叉樹的先|中|后序遍歷算法76.5 先|后|中序遍歷的應(yīng)用擴展96.5.1 基于先序遍歷的二叉樹(二叉鏈)的創(chuàng)建96.5.2 統(tǒng)計二叉樹中葉子結(jié)點的數(shù)目96.5.3 求二叉樹的高度106.5.4 釋放二叉樹的所有結(jié)點空間116.5.5 刪除并釋放二叉樹中以元素值為x的結(jié)點作為根的各子樹126.5.6 求位于二叉樹先序序列中第k個位置的結(jié)點的值126.5.

2、7 線索二叉樹136.5.8 樹和森林的遍歷146.6 二叉樹的層次遍歷166.7 判斷一棵二叉樹是否為完全二叉樹166.8 哈夫曼樹及其應(yīng)用186.8.1 最優(yōu)二叉樹(哈夫曼樹)186.8.2 哈夫曼編碼196.9 遍歷二叉樹的非遞歸算法196.9.1 先序非遞歸算法196.9.2 中序非遞歸算法206.9.3 后序非遞歸算法21第6章 二叉樹和樹6.1 樹的定義和基本術(shù)語1、 樹的遞歸定義1）結(jié)點數(shù)n=0時，是空樹2）結(jié)點數(shù)n>0時有且僅有一個根結(jié)點、m個互不相交的有限結(jié)點集m棵子樹2、 基本術(shù)語結(jié)點：葉子(終端結(jié)點)、根、內(nèi)部結(jié)點（非終端結(jié)點、分支結(jié)點）；樹的規(guī)模：結(jié)點的度、樹的度

3、、結(jié)點的層次、樹的高度(深度)結(jié)點間的關(guān)系：雙親(1)孩子(m)，祖先子孫，兄弟，堂兄弟兄弟間是否存在次序：無序樹、有序樹 去掉根結(jié)點非空樹森林引入一個根結(jié)點3、 樹的抽象數(shù)據(jù)類型定義樹特有的操作：查找：雙親、最左的孩子、右兄弟結(jié)點的度不定，給出這兩種操作可以查找到一個結(jié)點的全部孩子插入、刪除：孩子遍歷：存在一對多的關(guān)系，給出一種有規(guī)律的方法遍歷(有且僅訪問一次)樹中的結(jié)點ADT Tree數(shù)據(jù)對象：D=ai | aiElemSet, i=1,2,n, n0數(shù)據(jù)關(guān)系：若D為空集，則稱為空樹；若D僅含一個數(shù)據(jù)元素，則R為空集，否則R=H，H是如下二元關(guān)系：(1) 在D中存在唯一的稱為根的數(shù)據(jù)元素r

4、oot，它在關(guān)系H下無前驅(qū)；(2) 若D-root，則存在D-root的一個劃分D1, D2, , Dm (m>0) （Di 表示構(gòu)成第i棵子樹的結(jié)點集），對任意jk (1j, km) 有DjDk=，且對任意的i (1im)，唯一存在數(shù)據(jù)元素xiDi, 有<root, xi>H（H表示結(jié)點之間的父子關(guān)系）；(3) 對應(yīng)于D-root的劃分，H-<root, x1>, <root, xm>有唯一的一個劃分H1, H2, , Hm(m>0)（Hi表示第i棵子樹中的父子關(guān)系），對任意jk(1j,km)有HjHk=，且對任意i(1im)，Hi是Di上的二

5、元關(guān)系，(Di, Hi)是一棵符合本定義的樹，稱為根root的子樹。基本操作：InitTree(&T)操作結(jié)果：構(gòu)造空樹TDestroyTree(&T)初始條件：樹T已存在操作結(jié)果：銷毀樹TClearTree(&T)初始條件：樹T已存在操作結(jié)果：將樹T清為空樹TreeEmpty(T)初始條件：樹T已存在操作結(jié)果：若T為空樹，則返回TRUE，否則返回FALSETreeDepth(T)初始條件：樹T已存在操作結(jié)果：返回樹T的深度Root(T)初始條件：樹T已存在操作結(jié)果：返回T的根Value(T, cur_e)初始條件：樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：返回cu

6、r_e的值A(chǔ)ssign(T, &cur_e, value)初始條件：樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：結(jié)點cur_e賦值為valueParent(T, cur_e)初始條件：樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：若cur_e是T的非根結(jié)點，則返回它的雙親，否則函數(shù)值為“空”LeftChild(T, cur_e)初始條件：樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：若cur_e是T的非葉子結(jié)點，則返回它的最左孩子，否則返回“空”RightSibling(T, cur_e)初始條件：樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，

7、否則返回“空”InsertChild(&T, p, i, c)初始條件：樹T已存在，p指向T中某個結(jié)點，1ip所指結(jié)點的度+1，非空樹c與T不相交操作結(jié)果：插入c為T中p所指結(jié)點的第i棵子樹。DeleteChild(&T, p, i)初始條件：樹T已存在,p指向T中某個結(jié)點，1ip所指結(jié)點的度操作結(jié)果：刪除T中p所指結(jié)點的第i棵子樹。TraverseTree(T, visit( ) )初始條件：樹T已存在，visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)visit( )一次且至多一次。一旦visit( )失敗，則操作失敗ADT Tree6.2 二叉樹一

8、般樹的度不定，直接考慮其操作比較困難，故首先考慮度為二的樹。這里引入二叉樹。6.2.1 二叉樹的定義1、 二叉樹的特殊性·0度2·子樹有左右之分（子樹的個數(shù) = 1 或2時）注意：0度2的有序樹二叉樹當(dāng)某個結(jié)點只有一棵子樹時，不存在序的概念2、 二叉樹的抽象數(shù)據(jù)類型定義二叉樹相對樹的特殊性：最左的孩子、右兄弟左孩子、右孩子遍歷的規(guī)律性：L(左子樹)、D(根)、R(右子樹)的排列上限定為L在R前訪問(有對稱關(guān)系的，只須考慮其中的一種)ADT BinaryTree數(shù)據(jù)對象：D=ai | aiElemSet, i=1,2,n, n0數(shù)據(jù)關(guān)系：若D為空集，則稱為空樹；若D僅含一個數(shù)

9、據(jù)元素，則R為空集，否則R=H，H是如下二元關(guān)系：(1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；(2) 若D-root，則存在D-root的一個劃分DL, DR（左、右子樹的結(jié)點集），且DLDR=；(3) 若DL，則DL中存在唯一元素xL, 有<root, xL>H（H表示結(jié)點之間的父子關(guān)系），且存在DL上的關(guān)系HLH；若DR，則DR中存在唯一元素xR, 有<root, xR>H，且存在DR上的關(guān)系HRH；(3) (DL, HL)是一棵符合本定義的二叉樹，稱為根的左子樹；(DR, HR)是一棵符合本定義的二叉樹，稱為根的右子樹?；静僮鳎篒nit

10、BiTree(&T)操作結(jié)果：構(gòu)造空二叉樹TDestroyBiTree(&T)初始條件：二叉樹T已存在操作結(jié)果：銷毀二叉樹TClearBiTree(&T)初始條件：二叉樹T已存在操作結(jié)果：將二叉樹T清為空樹BiTreeEmpty(T)初始條件：二叉樹T已存在操作結(jié)果：若T為空二叉樹，則返回TRUE，否則返回FALSEBiTreeDepth(T)初始條件：二叉樹T已存在操作結(jié)果：返回二叉樹T的深度Root(T)初始條件：二叉樹T已存在操作結(jié)果：返回T的根Value(T, cur_e)初始條件：二叉樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：返回cur_e的值A(chǔ)ssign

11、(T, &cur_e, value)初始條件：二叉樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：結(jié)點cur_e賦值為valueParent(T, cur_e)初始條件：二叉樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：若cur_e是T的非根結(jié)點，則返回它的雙親，否則函數(shù)值為“空”LeftChild(T, cur_e)初始條件：二叉樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：若cur_e是T的非葉子結(jié)點，則返回它的左孩子，否則返回“空”RightChild(T, cur_e)初始條件：二叉樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：若cur_e有右孩子，則返回它的右孩子，否則返回“空

12、”LeftSibling(T, cur_e)初始條件：二叉樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：返回cur_e的左兄弟，若cur_e是T的左孩子或無左兄弟，則返回“空”RightSibling(T, cur_e)初始條件：二叉樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：返回cur_e的右兄弟，若cur_e是T的右孩子或無右兄弟，則返回“空”InsertChild(&T, p, LR, c)初始條件：二叉樹T已存在，p指向T中某個結(jié)點，LR為0或1，非空二叉樹c與T不相交操作結(jié)果：插入c為T中p所指結(jié)點的左或右子樹。p所指結(jié)點的原有左或右子樹則成為c的右子樹DeleteChil

13、d(&T, p, LR)初始條件：二叉樹T已存在，p指向T中某個結(jié)點，LR為0或1操作結(jié)果：根據(jù)LR為0或1，刪除T中p所指結(jié)點的左或右子樹。PreOrderTraverse( T, visit( )初始條件：二叉樹T已存在，visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：先序遍歷T，對每個結(jié)點調(diào)用函數(shù)visit()一次且僅一次。一旦visit()失敗，則操作失敗InOrderTraverse( T, visit( )初始條件：二叉樹T已存在，visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：中序遍歷T，對每個結(jié)點調(diào)用函數(shù)visit( )一次且僅一次。一旦visit( )失敗，則操作失敗PostOr

14、derTraverse( T, visit( )初始條件：二叉樹T已存在，visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：后序遍歷T，對每個結(jié)點調(diào)用函數(shù)visit( )一次且僅一次。一旦visit( )失敗，則操作失敗LevelOrderTraverse( T, visit( )初始條件：二叉樹T已存在，visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：層序遍歷T，對每個結(jié)點調(diào)用函數(shù)visit( )一次且僅一次。一旦visit( )失敗，則操作失敗ADT BinaryTree6.2.2 二叉樹的性質(zhì)1、 性質(zhì)1：第i層至多有2i-1個結(jié)點（由每個結(jié)點最多只有2個孩子推出）2、 性質(zhì)2：深度為k的二叉樹至多有

15、2k-1個結(jié)點（由性質(zhì)1，將各層最多的結(jié)點數(shù)累加，再結(jié)合等比數(shù)列的求和得出）思考：深度為k的二叉樹至少有多少個結(jié)點？( k個 ) 深度為k的b叉樹至多/至少有多少個結(jié)點？( (bk-1)/(b-1)，k)3、 性質(zhì)3：n0=n2+1 (ni表示二叉樹中度為i的結(jié)點個數(shù))從兩個角度考慮：二叉樹中結(jié)點的構(gòu)成（根據(jù)度）n = n0 + n1 + n2二叉樹中充當(dāng)其余結(jié)點的孩子的結(jié)點數(shù)n-1(去掉根) = n1+2×n2滿二叉樹：達到性質(zhì)1,2中所述的最大值情況完全二叉樹：去掉最下一層的結(jié)點，其余結(jié)點形成一棵滿二叉樹；葉子集中在最下2層(或1層)，最下一層的結(jié)點總是盡可能地占滿左邊的位置4、

16、 性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為5、 性質(zhì)5：結(jié)點間的編號關(guān)系考慮二叉樹的順序映像問題，尋求一種將二叉樹映像為向量的方法：對完全二叉樹從上至下，從左至右，從根開始依次編號(1.n)。孩子編號雙親編號求雙親ii/2(>0)求孩子左：2*i(<n+1), 右：2*i+1(<n+1)i右孩子編號左孩子編號求左兄弟i(奇數(shù)，i>1)i-1(>0)求右兄弟i+1(<n+1)i(偶數(shù)，i<n)思考：滿k叉樹中結(jié)點間的編號關(guān)系？孩子編號雙親編號求雙親p (k2)求第i個孩子p·k+ i-(k-1) (<n+1)p結(jié)點結(jié)點的左兄弟求左兄弟p

17、( (p-1)%k1)p-1(>0)求右兄弟p+1(<n+1)p(p-1)%k0)6.2.3 二叉樹的存儲結(jié)構(gòu)1、 二叉樹的順序存儲結(jié)構(gòu)1) 方法二叉樹補虛結(jié)點形成完全二叉樹自上而下、自左至右存儲2) 類型定義#define MAX_TREE_SIZE 100/* 二叉樹的最大結(jié)點數(shù) */typedef ElemTypeSqBiTreeMAX_TREE_SIZE; /* 0號單元存儲根結(jié)點*/必須引入特殊符號表示虛結(jié)點的值上述類型定義的缺陷：未指明實際二叉樹占用的長度，可改進為：typedef structElemTypeelemMAX_TREE_SIZE+1; /* 1號單元存儲

18、根結(jié)點*/int length;SqBiTree;3) 不足：空間的利用率不高如：若深度為5且僅含有5個結(jié)點的二叉樹，必須要占用2425-1空間。rchildlchildparentdata2、 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)1) 引入輔助空間表示結(jié)點間的相對關(guān)系雙親(1)孩子(2) (如右圖) lchilddatarchildparentlchilddatarchild二叉鏈表三叉鏈表若需要找指定結(jié)點的雙親，則用三叉鏈表可在O(1)時間內(nèi)獲得某結(jié)點的雙親；而用二叉鏈表則需從根開始，采用一定的巡查方法進行搜索。2) 二叉鏈表的類型定義typedef struct BiTNodeElemTypedata;

19、struct BiTNode*lchild, *rchild;/* 左右孩子指針 */BiTNode, *BiTree;3) 二叉鏈表的鏈域若有n個結(jié)點，則共有2n個鏈域；其中n-1不為空，指向孩子。4) 二叉樹(鏈?zhǔn)酱鎯?的創(chuàng)建輸入序列與二叉樹的映射關(guān)系(1) 完全二叉樹的順序映射通過補虛結(jié)點，將一般的二叉樹轉(zhuǎn)變成完全二叉樹，再對該完全二叉樹的結(jié)點按自上而下、自左至右進行輸入。(2) 二叉樹的先序遍歷通過補虛結(jié)點，使二叉樹中各實際結(jié)點均具有左右孩子，再對該二叉樹按先序遍歷進行輸入。(3) 二叉樹的兩種遍歷序列：先序+中序，后序+中序6.3 樹和森林1、 樹的存儲結(jié)構(gòu)1) 雙親表示法針對每一結(jié)

20、點，附設(shè)指示其雙親位置的數(shù)據(jù)域。采用順序表（非順序映像）。#define MAX_TREE_SIZE 100/* 樹的最大結(jié)點數(shù) */typedef struct PTNodeElemTypedata;intparent;PTNode;typedef structPTNodenodesMAX_TREE_SIZE;intn;/* 結(jié)點數(shù)*/PTree;2) 孩子表示法各結(jié)點的孩子數(shù)是不定的，用順序表表示必須給出樹的度的最大值，以及每一結(jié)點的實際度數(shù)，空間浪費大。故以鏈表存儲每一結(jié)點的所有孩子的位置信息。typedef struct CTNode/* 孩子結(jié)點*/intchild;/* 孩子結(jié)點的

21、位置編號*/struct CTNode*next;/* 下一個孩子結(jié)點*/*ChildPtr;typedef structTElemTypedata;ChildPtrfirstchild;/* 孩子鏈表的頭指針*/CTBox;typedef structCTBoxnodesMAX_TREE_SIZE;intn, r;/* 結(jié)點數(shù)和根的位置*/CTree;3) 孩子兄弟法二叉鏈表表示。針對每一結(jié)點，引入其第一個孩子和下一個右兄弟的位置域。typedef struct CSNodeElemTypedata;struct CSNode*firstchild, *nextsibling;/* 第一個孩

22、子、下一個兄弟指針 */CSNode, *CSTree;2、 森林與二叉樹的轉(zhuǎn)換森林用孩子兄弟法表示，形成二叉鏈表，可以將它理解為一個二叉樹的二叉鏈表；二叉樹用二叉鏈表表示，可以將該二叉鏈表理解為孩子兄弟鏈表，從而獲得森林。6.4 二叉樹的先|中|后序遍歷算法1、 遍歷·對于二叉樹中的結(jié)點，有且僅訪問一次·遍歷的規(guī)律性：L(左子樹)、D(根)、R(右子樹)的排列上限定L在R前訪問(有對稱關(guān)系的，只須考慮其中的一種)·先(根)序遍歷DLR·中(根)序遍歷LDR·后(根)序遍歷LRD-*cab遍歷路徑先序訪問中序訪問后序訪問2、 二叉樹遍歷的遞歸實

23、現(xiàn)二叉樹的遞歸定義性質(zhì)，決定了它的很多算法都可用遞歸實現(xiàn)，遍歷就是其中之一。對于二叉樹的遍歷，可以不去具體考慮各子問題(左子樹、根、右子樹)的遍歷結(jié)果是什么，而去考慮如何由各子問題的求解結(jié)果構(gòu)成原問題(二叉樹)的遍歷結(jié)果遞歸規(guī)律的確定。必須注意的是，當(dāng)二叉樹小到一定程度，即空樹時，應(yīng)直接給出解答遞歸結(jié)束條件及處理。三種遍歷的區(qū)別(右圖)：所經(jīng)過的搜索路線是相同的；只是訪問結(jié)點的時機不同。每一結(jié)點在整個搜索路線中會經(jīng)過3次（第一次進入到該結(jié)點、由左子樹回溯到該結(jié)點、由右子樹回溯到該結(jié)點），如在第一次遇到時就訪問該結(jié)點，那么稱之為先序；第二次經(jīng)過時訪問為中序；第三次經(jīng)過時訪問則為后序。1) 先序遍

24、歷Status PreOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) )if ( T != NULL )if ( Visit(T->data) )if ( PreOrderTraverse( T->lchild, Visit ) )if ( PreOrderTraverse( T->rchild, Visit ) )return OK;return ERROR; else return OK;2) 后序遍歷Status PostOrderTraverse( BiTree T, Status ( *Visit )

25、(ElemType e) )if ( T != NULL )if ( PostOrderTraverse( T->lchild, Visit ) )if ( PostOrderTraverse( T->rchild, Visit ) )if ( Visit(T->data) )return OK;return ERROR; else return OK;3) 中序遍歷Status InOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) )if ( T != NULL )if ( InOrderTraverse( T-

26、>lchild, Visit ) )if ( Visit(T->data) )if ( InOrderTraverse( T->rchild, Visit ) )return OK;return ERROR; else return OK;6.5 先|后|中序遍歷的應(yīng)用擴展利用二叉樹的遍歷算法，適當(dāng)修改訪問結(jié)點操作的內(nèi)容，可以得到求解許多問題的算法。² 二叉樹的創(chuàng)建（基于先序遍歷）² 二叉樹的線索化² 查找指定結(jié)點：在訪問結(jié)點時，判斷當(dāng)前訪問的結(jié)點是否是指定的結(jié)點，若是則返回該結(jié)點位置，否則繼續(xù)遍歷；² 查找位于某種遍歷次序中的第k位的

27、結(jié)點：遍歷前，引入一計數(shù)器，用來統(tǒng)計已訪問過的結(jié)點數(shù)，初值為0；在訪問結(jié)點時，將該計數(shù)器增1，并看是否達到k，；² 求葉子結(jié)點的數(shù)目：遍歷前，引入葉子結(jié)點計數(shù)器，初值為0；訪問結(jié)點時，將該計數(shù)器增1；遍歷結(jié)束，則計數(shù)器中的值即為所求解；² 判斷二叉樹中是否僅包含有度為2和0的結(jié)點：訪問結(jié)點時，判斷該結(jié)點孩子的有無情況，² 求指定結(jié)點的層次：孩子結(jié)點的層次比其雙親結(jié)點層次多一；² 求二叉樹的高度：二叉樹的高度 = max(左子樹的高度, 右子樹的高度) +16.5.1 基于先序遍歷的二叉樹(二叉鏈)的創(chuàng)建【本例特征】如何基于二叉樹的先序、中序、后序遍歷的遞

28、歸算法進行問題求解？【思路】先 序 遍 歷PreOrderTraverse創(chuàng) 建CreateBiTree輸入二叉鏈表示的二叉樹的頭指針T帶虛結(jié)點的先序序列ch輸入的表現(xiàn)方式參數(shù)由輸入設(shè)備輸入scanf( &ch )輸出對結(jié)點的訪問結(jié)果二叉鏈表示的二叉樹的頭指針T輸出的表現(xiàn)方式由輸出設(shè)備輸出變參空樹（遞歸結(jié)束）的條件及處理(直接求解)T = NULLch = END_DATA（表示虛結(jié)點的值）空T = NULL根結(jié)點的訪問(子問題直接求解)Visit( T->data )T = ( BiTree)malloc( sizeof( BiTNode )T->data = ch 左子

29、樹(使用遞歸調(diào)用的解)PreOrderTraverse( T->lchild )CreateBiTree( T->lchild )右子樹(使用遞歸調(diào)用的解)PreOrderTraverse( T->rchild )CreateBiTree( T->rchild )【算法】見數(shù)據(jù)結(jié)構(gòu)(C語言版)P131算法6.4。6.5.2 統(tǒng)計二叉樹中葉子結(jié)點的數(shù)目【本例特征】如何通過全局變量、變參、返回值三種渠道返回處理結(jié)果？【思路】在遍歷二叉樹時，對一些特殊的結(jié)點(無左右孩子)進行計數(shù)。可以修改遍歷算法的結(jié)點訪問操作為對特殊結(jié)點的判定和計數(shù)過程，需要注意的是計數(shù)器的處理方式?？梢杂?/p>

30、以下幾種計數(shù)處理：·用遍歷函數(shù)的返回值傳出求得的葉子結(jié)點的數(shù)目；·為遍歷函數(shù)增加一個引用參數(shù)，用來傳出指定二叉樹的葉子結(jié)點數(shù)目。·引入全局的計數(shù)器，初始為0；此處，遍歷次序的選擇對本算法沒有太大影響。【算法1 全局的計數(shù)器】/ n為葉子結(jié)點的計數(shù)器intn=0;voidleaf(BiTree T)/ 利用二叉樹的先序遍歷if (T != NULL )/ 訪問結(jié)點->葉子的判定和計數(shù)if( T->lchild=NULL && T->rchild=NULL )n+;leaf(T->lchild);leaf(T->rchil

31、d);/ 調(diào)用結(jié)束，即可由n獲得二叉樹T的葉子結(jié)點數(shù)目，需注意下次調(diào)用前須n=0;【算法2 以函數(shù)返回值返回】/ 函數(shù)值為T的葉子結(jié)點數(shù)intleaf(BiTree T)/ 利用二叉樹的中序遍歷, n為局部變量n = 0;if ( T != NULL )n = leaf ( T->lchild );/ 訪問結(jié)點->葉子結(jié)點的判定和計數(shù)if ( T->lchild=NULL && T->rchild=NULL )n+;n += leaf(T->rchild);return (n);【算法3 通過引用參數(shù)返回】/ 引用參數(shù)n為T的葉子結(jié)點數(shù)voidle

32、af(BiTree T, int &n)/ 利用二叉樹的后序遍歷n = 0;if ( T != NULL )leaf (T->lchild, n1);leaf (T->rchild, n2);/ 訪問結(jié)點->葉子結(jié)點的判定和計數(shù)if ( T->lchild=NULL && T->rchild=NULL )n+;n += n1+ n2;6.5.3 求二叉樹的高度【思路】·二叉樹為空時，高度為0；·若T不為空，則其高度應(yīng)為其左右子樹高度的最大值再加1?？梢杂幸韵聨追N處理高度值的方法：·用遍歷函數(shù)值返回指定二叉樹的高

33、度；·遍歷函數(shù)增加一個引用參數(shù)，用來傳出指定二叉樹的高度?！舅惴?】/ 函數(shù)值為T的高度inthigh(BiTree T)if ( T = NULL )return ( 0 );elsereturn( max ( high (T->lchild ), high (T->rchild) ) +1 ) ;【算法2】/ 引用參數(shù)h為T的高度voidhigh(BiTree T, int &h)/ 利用二叉樹的后序遍歷if ( T = NULL )h=0;else high(T->lchild, h1);high(T->rchild, h2);h = max(h

34、1, h2)+1;6.5.4 釋放二叉樹的所有結(jié)點空間【思路】·二叉樹為空時，不必釋放；·若T不為空，則先釋放其左右子樹的所有結(jié)點的空間，再釋放根結(jié)點的空間后序。若在釋放子樹的空間前，先釋放根結(jié)點的空間，則需要將子樹的根結(jié)點的指針暫存到其他變量；否則，無法找到子樹?！舅惴?】/ 此處T應(yīng)為引用參數(shù)，因為經(jīng)過本函數(shù)處理后，T的值發(fā)生了變化voiddeleteBiTree(BiTree &T)if ( T != NULL )deleteBiTree(T->lchild );deleteBiTree(T->rchild );/ 訪問結(jié)點->釋放結(jié)點的空間

35、free(T);T = NULL; 【算法2】voiddeleteBiTree(BiTree &T)if ( T != NULL)/ 先序遍歷，暫存孩子結(jié)點指針T1 = T->lchild; T2 = T->rchild;/ 訪問結(jié)點->釋放結(jié)點的空間free(T);T = NULL;deleteBiTree(T1);deleteBiTree(T2);6.5.5 刪除并釋放二叉樹中以元素值為x的結(jié)點作為根的各子樹【本例特征】如何選擇二叉樹的先序、中序、后序遍歷來解決問題，它們對問題求解有何影響？【思路】整個過程分為兩個方面：·遍歷中查找元素值為x的結(jié)點

36、83;查到該結(jié)點時，調(diào)用6.5.3的算法釋放子樹空間。需要考慮的問題是：如何將全部的結(jié)點找到并釋放？外層查找采用的遍歷次序?qū)Ρ舅惴ㄓ泻斡绊?？從以?個算法中可以看出，利用先序遍歷是最合適的；中序和后序，存在一定的多余操作。【算法1】voiddeleteXTree(BiTree &T, ElemType x)/ 基于先序的查找if ( T != NULL )/ 訪問結(jié)點->判斷是否為指定結(jié)點->釋放樹空間if ( T->data= x ) deleteBiTree(T);else/ 此處else不能省略deleteXTree(T->lchild, x);delet

37、eXTree(T->rchild, x);【算法2】voiddeleteXTree(BiTree &T, ElemType x)/ 基于中序的查找if ( T != NULL )deleteXTree(T->lchild, x);/ 若T->data= x，則此步驟多余/ 訪問結(jié)點->判斷是否為指定結(jié)點->釋放樹空間if ( T->data= x) deleteBiTree(T);elsedeleteXTree(T->rchild, x);【算法3】voiddeleteXTree(BiTree &T, ElemType x)/ 基于后序

38、的查找if ( T != NULL )deleteXTree(T->lchild, x);/ 若T->data= x，則此步驟多余deleteXTree(T->rchild, x);/ 若T->data= x，則此步驟多余/ 訪問結(jié)點->判斷是否為指定結(jié)點->釋放樹空間if ( T->data = x ) deleteBiTree(T);6.5.6 求位于二叉樹先序序列中第k個位置的結(jié)點的值【本例特征】多個返回結(jié)果如何處理？【思路】·待查找的結(jié)點的存在性：當(dāng)二叉樹為空樹，或者k非法時，待查找的結(jié)點是不存在的è 函數(shù)應(yīng)返回待查找的結(jié)點

39、是否存在的狀態(tài)指示：TRUE-存在，F(xiàn)ALSE-不存在·當(dāng)待查找的結(jié)點存在時，需進一步返回該結(jié)點的值問題1：該算法需要返回多個值，如何處理？答：一種做法是用返回值返回存在性，用變參返回值。問題2：該算法可以基于二叉樹的先序遍歷的遞歸算法來構(gòu)造，如何知道當(dāng)前訪問的結(jié)點是先序序列中的第幾個結(jié)點？答：引入計數(shù)器，對于該計數(shù)器可以采用全局變量來存儲，也可以通過變參來處理?！舅惴ā縎tatus PreorderKnode(BiTree T, int k, ElemType &e, int &count)/ 輸入：T為二叉鏈表示的二叉樹，k為待查找的結(jié)點在先序序列中的位序(1kn

40、，假設(shè)n/ 為二叉樹T中的結(jié)點個數(shù)/ 輸出：返回值TRUE：待查找的結(jié)點存在；FALSE：待查找的結(jié)點不存在/ e當(dāng)待查找的結(jié)點存在時，該結(jié)點的值通過e帶回/ 中間變量：count記錄當(dāng)前已經(jīng)訪問過的結(jié)點個數(shù)if ( T=NULL) return FALSE;count+;/ 訪問結(jié)點à對已訪問的結(jié)點進行計數(shù)if (count=k )/ à判斷該結(jié)點是否是待查找的結(jié)點e = T->data;return TRUE;/ 查到，則設(shè)置e，并返回TRUEelse if (count > k) return FALSE; / 計數(shù)器count已經(jīng)超出k(當(dāng)k<0時

41、)，則直接返回FALSEelseif (PreorderKnode(T->lchild, k, e, count)=FALSE) / 在左子樹中查找return PreorderKnode(T->rchild, k, e, count); / 若未找到，則在右子樹中查找return TRUE;【調(diào)用示意】int c=0; if ( PreorderKnode(T, k, e, c)=TRUE ) 6.5.7 線索二叉樹1、 線索二叉樹的基本概念1） 二叉樹的遍歷結(jié)果為一個線性序列；2） 有n個結(jié)點的二叉樹的二叉鏈表中，有n+1個空鏈域；3） 擴展二叉鏈，利用空鏈域存放結(jié)點在某種遍歷

42、次序下的直接前驅(qū)和直接后繼信息4） 擴展二叉鏈的結(jié)點：lchildltagdatartagrchildltag : 0結(jié)點的左孩子； 1結(jié)點的直接前驅(qū)rtag : 0結(jié)點的右孩子； 1結(jié)點的直接后繼5） 名詞：線索鏈表、線索、線索二叉樹、線索化6） 類型定義typedef enum Link, Thread PointerTag; / Link=0:指針，Thread=1: 線索typedef struct BiThrNodeElemTypedata;struct BiThrNode*lchild, *rchild;/ 左右孩子指針PointerTagltag, rtag;/ 左右標(biāo)志BiTh

43、rNode, *BiThrTree;為二叉樹的線索鏈表增加一個頭結(jié)點，令其lchild域指向二叉樹的根結(jié)點，rchild域指向中(前/后)序遍歷時訪問的最后一個結(jié)點；中序序列中的第一個結(jié)點的lchild域和最后一個結(jié)點的rchild域指向頭結(jié)點。2、 在線索樹上進行遍歷（P133）3、 中序線索化二叉樹（二叉樹的中序遍歷算法的應(yīng)用）InOrderThreading(BiThrTree &thrt, BiThrTree T)過程：分配頭結(jié)點、頭結(jié)點域的賦值、調(diào)用InThreading( )線索化、填充頭結(jié)點的rchild域引入全局指針pre保留中序遍歷時剛剛訪問過的結(jié)點，這樣便于處理pr

44、e指向的結(jié)點與當(dāng)前要訪問的結(jié)點中的鏈，使這兩個結(jié)點滿足前驅(qū)-后繼的關(guān)系。InThreading( )用來遞歸地進行二叉鏈的中序線索化，故pre的初始化不應(yīng)在InThreading( )中進行，而可以放在InOrderThreading( )中進行。中 序 遍 歷InOrderTraverse中序線索化二叉樹InThreading輸入二叉鏈表示的二叉樹的頭指針T線索二叉鏈表示的二叉樹的頭指針p輸入的表現(xiàn)方式參數(shù)參數(shù)輸出對結(jié)點的訪問結(jié)果修改p指向的結(jié)點的鏈域輸出的表現(xiàn)方式由輸出設(shè)備輸出參數(shù)空樹（遞歸結(jié)束）的條件及處理(直接求解)T = NULLp = NULL空空左子樹(使用遞歸調(diào)用的解)InOr

45、derTraverse( T->lchild )InThreading( p->lchild )根結(jié)點的訪問(子問題直接求解)Visit( T->data )if ( p->lchild= NULL ) p->ltag = Thread; p->lchild = pre; if ( pre->rchild= NULL ) pre->rtag = Thread; pre->rchild = p; pre = p;右子樹(使用遞歸調(diào)用的解)PreOrderTraverse( T->rchild )InThreading( p->rc

46、hild )6.5.8 樹和森林的遍歷樹：先序、后序，不提中序。用孩子-兄弟法表示后，可以對該二叉鏈表進行先序遍歷和中序遍歷，獲得相應(yīng)樹的先序和后序遍歷結(jié)果。樹的一些問題可以借鑒二叉樹的一些處理方法來解決。1、 統(tǒng)計樹(森林)中葉子結(jié)點的個數(shù)孩子-兄弟法：每個結(jié)點包含一個指向第一個孩子和一個指向下一個右兄弟的指針域葉子結(jié)點的特征：結(jié)點的firstchild為空統(tǒng)計葉子結(jié)點的個數(shù)在遍歷的過程中統(tǒng)計firstchild域為空的結(jié)點的個數(shù)?！舅惴ā? n為葉子結(jié)點的計數(shù)器intn=0;voidCSleaf(CSTree T)/ 利用樹的先序遍歷if ( T != NULL )/ 訪問結(jié)點->葉

47、子結(jié)點的判定和計數(shù)if ( T->firstchild = NULL )n+;CSleaf(T->firstchild);CSleaf(T->nextsibling);/ 調(diào)用結(jié)束，即可由n獲得樹T的葉子結(jié)點數(shù)目，需注意下次調(diào)用前須n = 0;2、 求樹的高度孩子-兄弟法表示的樹： 樹的高度 = max(相應(yīng)左子樹的高度+1，右子樹的高度) 【算法】/ 引用參數(shù)h為T的高度voidCShigh(CSTree T, int &h)/ 利用二叉鏈表的后序遍歷if ( T = NULL )h = 0;else CShigh(T->firstchild, h1);CSh

48、igh(T->nextsibling, h2);h = max(h1+1, h2);3、 求樹的度【算法】/ degree表示表示樹的度voidCSDegree(CSTree T, int &degree)/ 利用二叉樹的先序遍歷/ d表示T指向的結(jié)點的度if ( T = NULL )degree = 0;else if ( T->firstchild = NULL ) d = 0;elsed = 1; p = T->firstchild;while ( p->nextsibling != NULL )p = p->nextsibling; d+;CSDe

49、gree (T->firstchild, d1);CSDegree (T->nextsibling, d2 );degree = max (d1, d2, d );6.6 二叉樹的層次遍歷【思路】先訪問的結(jié)點，其孩子結(jié)點必然也先訪問。引入隊列存儲已被訪問的、但其左右孩子尚未訪問的結(jié)點的指針。若使用鏈隊列，其元素可定義為：typedef struct QNodeBitreedata;/ 指向二叉樹結(jié)點的指針struct QNode *next; QNode, *QueuePtr;【算法】StatusLevelTraverse (BiTree T, Status ( *Visit )

50、(ElemType e) )/ 初始化隊列，隊列的元素為二叉樹的結(jié)點指針I(yè)nitQueue(Q);if ( T != NULL )/ 訪問根if ( !Visit( T->data ) ) return ERROR;/ EnQueue( )為入隊函數(shù)，T為待入隊的元素EnQueue(Q, T);/ 從隊列中取已被訪問的、但其左右孩子尚未訪問的結(jié)點指針，訪問其孩子while( !QueueEmpty(Q) )/ 隊不為空，則尚有未訪問其孩子的結(jié)點/ DeQueue( )為出隊函數(shù)，它將原隊頭元素作為返回值返回p = DeQueue (Q);/ 訪問左孩子if ( p->lchild

51、!= NULL ) if ( !Visit( p->lchild ->data ) return ERROR; EnQueue(Q, p->lchild );/ 訪問右孩子if( p->rchild != NULL ) if ( !Visit( p->rchild ->data ) return ERROR; EnQueue(Q, p->rchild );return OK;【算法應(yīng)用】利用層次遍歷，可以求解：·找出距指定結(jié)點最近或最遠的葉子子孫；·找出指定層的所有(葉子、2度、1度)結(jié)點；·判斷二叉樹是否為完全二叉樹、滿

52、二叉樹；·一般樹的層次遍歷（樹用孩子-兄弟法表示）6.7 判斷一棵二叉樹是否為完全二叉樹【思路】由完全二叉樹的定義，對完全二叉樹按層次遍歷應(yīng)滿足：1） 若某結(jié)點沒有左孩子，則它一定無右孩子；2） 若某結(jié)點缺孩子，則其后繼必?zé)o孩子。利用層次遍歷，需要附加一個標(biāo)志量bFlag反映是否已掃描過的結(jié)點均有左右孩子。在第一次遇到缺孩子的結(jié)點時，可將bFlag置為FALSE；此時存在以下兩種情況：·若它滿足1），需要繼續(xù)掃描后繼結(jié)點，以判斷是否滿足2）；·若不滿足1），則說明不是完全二叉樹?！舅惴ā縯ypedefcharBOOL;#defineTRUE1#defineFALS

53、E0BOOLJudgeCBT(BiTree T)/ 初始化隊列和標(biāo)志量bFlagInitQueue (Q);bFlag = TRUE;if ( T != NULL )EnQueue(Q, T);while ( !QueueEmpty(Q) )/ 隊不為空，則尚有未訪問其孩子的結(jié)點p = DeQueue(Q);if ( bFlag = FALSE ) / 前驅(qū)結(jié)點缺左孩子，則若該結(jié)點有孩子，則此樹非完全二叉樹if ( p->lchild!=NULL | p->rchild!=NULL )return FALSE;else if ( p->lchild = NULL ) / 第一

54、次遇到結(jié)點缺左孩子bFlag = FALSE;/ 若有右孩子，不滿足1），則非完全二叉樹if ( p->rchild != NULL ) return FALSE;else if ( p->lchild != NULL ) / 若有左孩子，則入隊EnQueue(Q, p->lchild ); if ( p->rchild = NULL ) / 第一次遇到結(jié)點有左孩子，缺右孩子bFlag = FALSE;elseEnQueue(Q, p->rchild ); return TRUE;/ T為空，也是完全二叉樹【思考】上述算法在每一種完全二叉樹不成立時，即返回FALSE；請修改算法，使得用統(tǒng)一的return返回判斷結(jié)果。（提示：引入另一標(biāo)志量，保存當(dāng)前的掃描是否符合完全二叉樹的判斷條件）6.8 哈夫曼樹及其應(yīng)用6.8.1 最優(yōu)二叉樹(哈夫曼樹)1、 基本概念結(jié)點間的路徑長度、樹的路徑長