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

1、數(shù)據(jù)結(jié)構(gòu)教案第6章樹與二叉樹數(shù)據(jù)結(jié)構(gòu)教案第六章樹與二叉樹目錄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.7 線索

2、二叉樹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數(shù)據(jù)結(jié)構(gòu)教案第6章樹與二叉樹第6章二叉樹和樹6.1樹的定義和基本術(shù)語1、樹的遞歸定義1)結(jié)點數(shù)n=0時，是空樹2)結(jié)點數(shù)n>0時有且僅有一個根結(jié)點、m個互不相交的有PM結(jié)點集m棵子樹2、基本術(shù)語結(jié)點：葉子(終端結(jié)點卜根、內(nèi)部結(jié)點(非終端結(jié)點、分支結(jié)

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

4、 R為空集，否則 R=H , H是如下二元 關(guān)系：(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root,它在關(guān)系H下無前驅(qū)；(2)若 D-root w ，則存在 D-root的一個劃分 Di, D2,，Dm(m>0) (Di表示構(gòu)成第i棵子樹的結(jié)點集)，對任意jwk (1Wj, k<m)有DjCDk=中，且對任意的i (1 w i w m),唯一存在數(shù)據(jù)元素 xi Di,有<root, xi> C H ( H表示結(jié)點之間的父子關(guān)系)；(3)對應(yīng)于 D- root的劃分，H- <root, xi>,<root, xm>有唯一的一 個劃分Hi, H2,，H

5、m(m>0) (Hi表示第i棵子樹中的父子關(guān)系)，對任 意 jwk(1 wj,k wm)有 HjAHkR，且對任意 i(1wiwm), Hi 是 Di 上的 二元關(guān)系，(Di, H i)是一棵符合本定義的樹，稱為根 root的子樹。 基本操作：InitTree(&T)操作結(jié)果：卞造空樹 TDestroyTree(&T)初始條件：樹T已存在操作結(jié)果：銷毀樹 TClearTree(&T)初始條件：樹T已存在操作結(jié)果：將樹T清為空樹TreeEmpty(T)初始條件：樹T已存在操作結(jié)果:若 T為空樹，則返回TRUE,否則返回FALSETreeDepth(T)初始條件：樹T

6、已存在操作結(jié)果：返回樹 T的深度Root(T)初始條件：樹T已存在操作結(jié)果：返回 T的根Value(T, cur_e)宴初始條件：樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：返回cur_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é)點 。I /操作結(jié)果：若cur_e是T的非根結(jié)點，則返回它的雙親，否則函數(shù)值為LeftChild(T, cur_e)匕 >初始條件：樹 T已存在，cur_e是T中某個結(jié)點 g-操作

7、結(jié)果：若cur_e是T的非葉子結(jié)點，則返回它的最左孩子，否則返回“空”RightSibling(T, cur_e)Z /初始條件：樹T已存在，cur_e是T中某個結(jié)點操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則返回“空”InsertChild(&T, p, i, c)初始條件：樹 T已存在，p指向T中某個結(jié)點，1WiWp所指結(jié)點的度 +1,非空樹c與T不相交操作結(jié)果：插入c為T中p所指結(jié)點的第i棵子樹。DeleteChild(&T, p, i)初始條件：樹T已存在，p指向T中某個結(jié)點，1WiWp所指結(jié)點的度操作結(jié)果：刪除T中p所指結(jié)點的第i棵子樹?？赥raverseT

8、ree(T, visit( ) )f 勾初始條件：樹 T已存在，visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：按某種次序?qū)?T的每個結(jié)點調(diào)用函數(shù) visit()一次且至多一次。一旦visit()失敗，則操作失敗 ADT Tree6.2 二叉樹一般樹的度不定，直接考慮其操作比較困難，故首先考慮度為二的樹。這里引入二叉樹。6.2.1 二叉樹的定義1、二叉樹的特殊性 0W度w 2子樹有左右之分(子樹的個數(shù) =1或2時)注意：0W度w 2的有序樹w二叉樹當(dāng)某個結(jié)點只有一棵子樹時，不存在序的概念2、二叉樹的抽象數(shù)據(jù)類型定義二叉樹相對樹的特殊性：最左的孩子、右兄弟 左孩子、右孩子遍歷的規(guī)律性：L(左子樹)、D

9、(根卜R(右子樹)的排列上限定為L在R前訪問(有對稱關(guān)系的，只須考慮其中的一種ADT BinaryTree 數(shù)據(jù)對象：D=a i | a C ElemSet, i=1,2,n, n> 0數(shù)據(jù)關(guān)系：若D為空集，則稱為空樹；若D僅含一個數(shù)據(jù)元素，則 R為空集，否則 R=H , H是如下二元 關(guān)系：(1)在D中存在唯一的稱為根的數(shù)據(jù)元素 root,它在關(guān)系H下無前驅(qū)； (2)若D-root w，則存在 D- root的一個劃分 Dl, Dr (左、右子 樹的結(jié)點集)，且DlADr=；(3)若DlW中,則Dl中存在唯一元素 Xl,有<root, xl> C H (H表示結(jié) 點之間的父

10、子關(guān)系)，且存在Dl上的關(guān)系HlUH;若DrW，則Dr 中存在唯一元素 Xr,有<root, xr>CH,且存在Dr上的關(guān)系Hr二H； (3) (D l, H l)是一棵符合本定義的二叉樹，稱為根的左子樹；(Dr, H r)是一棵符合本定義的二叉樹，稱為根的右子樹。基本操作：InitBiTree(&T)汜 二 .操作結(jié)果：構(gòu)造空二叉樹T且DestroyBiTree(&T)三/1匕初始條件：二叉樹 T已存在操作結(jié)果：銷毀二叉樹 T。甲：ClearBiTree(&T)初始條件：二叉樹 T已存在操作結(jié)果：將二叉樹T清為空樹BiTreeEmpty(T)力乂初始條件：

11、二叉樹 T已存在操作結(jié)果:若 T為空二叉樹，則返回 TRUE,否則返回FALSE BiTreeDepth(T)二 口初始條件：二叉樹 T已存在 操作結(jié)果：返回二叉樹T的深度Root(T)初始條件：二叉樹 T已存在操作結(jié)果：返回 T的根Value(T, cur_e)初始條件：二叉樹 T已存在，cur_e是T中某個結(jié)點操作結(jié)果：返回cur_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

12、是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有右孩子，則返回它的右孩子，否則返回“空”LeftSibling(T, cur_e)初始條件：二叉樹 T已存在，cur_e是T中某個結(jié)點操作結(jié)果：返回 cur_e的左兄弟，若cur_e是T的左孩子或無左兄弟，則返回“空”RightSibling(T, cur_e)初始條件：二點對

13、T已存在，cur_e是T中某個結(jié)點操作結(jié)果：返回 cur_e的右兄弟，若cur_e是T的右孩子或無右兄弟， 則返回“空”InsertChild(&T, p, LR, c)/ .初始條件：二叉樹 T已存在，p指向T中某個結(jié)點，LR為?；? ,非空二叉樹c與T不相交”|，/ 1一操作結(jié)果：插入 c為T中p所指結(jié)點的左或右子樹。p所指結(jié)點的原有 左或右子樹則成為 c的右子樹DeleteChild(&T, p, LR)三 一.初始條件：二叉樹 T已存在，p指向T中某個結(jié)點,m LR為。或1操作結(jié)果：根據(jù) LR為0或1,刪除T中p所指結(jié)點的左或右子樹。g)PreOrderTraverse

14、( 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()失敗，則操作失敗| )PostOrderTraverse( T, visit()初始條件：二叉樹 T已存在，visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：后序遍歷 T,對每個結(jié)點調(diào)用函數(shù) visit()

15、一次且僅一次。一旦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的二叉樹至多有2k-1個結(jié)點(由性質(zhì)1,將各層最多的結(jié)點數(shù)累加，再 結(jié)合等比數(shù)列的求和得出)思考：深度為k的二叉樹至少有多少個結(jié)點？( k個)深度為k的b叉樹至多/至少有多

16、少個結(jié)點？ (bk-1)/ (b-1), k)3、性質(zhì)3: n0=n2+1 (ni表示二叉樹中度為i的結(jié)點個數(shù))從兩個角度考慮：二叉樹中結(jié)點的構(gòu)成（根據(jù)度）n = n0+ ni + n2二叉樹中充當(dāng)其余結(jié)點的孩子的結(jié)點數(shù)n-1（去掉根）=n1+2x通滿二叉樹：達到性質(zhì)1,2中所述的最大值情況完全二叉樹：去掉最下一層的結(jié)點，其余結(jié)點形成一棵滿二叉樹；葉子集中在最下2層（或Jog2 n 11層），最下一層的結(jié)點總是盡可能地占滿左邊的位置 4、性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度為5、性質(zhì)5:結(jié)點間的編號關(guān)系考慮二叉樹的順序映像問題，尋求一種將二叉樹映像為向量的方法：對完全二叉樹從上至下，從左至右

17、，從根開始依次編號（1.n）。孩子編號雙擊編p求雙親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|p + (k2).2二-(k>2) k1-求第i個孩子p k+ i- (k-1) (<n+1)p結(jié)點結(jié)點的左兄弟求左兄弟p ( (p-1)%kw 1)p-1(>0)求石兄弟p+1(<n+1)p(p-1)%k w0)6.2.3 二叉樹的存儲結(jié)

18、構(gòu)1、二叉樹的順序存儲結(jié)構(gòu)據(jù)1）方法Z 口二叉樹一補虛結(jié)點形成完全二叉樹一自上而下、自左至右存儲2） 類型定義#define MAX_TREE_SIZE 100/* 二叉樹的最大結(jié)點數(shù)*/typedef ElemType SqBiTreeMAX_TREE_SIZE; /* 0 號單元存儲卞艮結(jié)點*/必須引入特殊符號表示虛結(jié)點的值上述類型定義的缺陷：未指明實際二叉樹占用的長度，可改進為：typedef structElemTypeelemMAX_TREE_SIZE+1;/* 1 號單元存儲根結(jié)點 */intlength;SqBiTree;3）不足：空間的利用率不高如：若深度為5且僅含有5個結(jié)點的

19、二叉樹，必須要占用2425-1空間。2、二叉樹的鏈式存儲結(jié)構(gòu)1)引入輔助空間表示結(jié)點間的相對關(guān)系雙親孩子(2)(如右圖)lchilddatarchild二叉鏈表parentlchilddatarchild三叉鏈表若需要找指定結(jié)點的雙親， 則用三叉鏈表可在 0(1)時間內(nèi)獲得某 結(jié)點的雙親；而用二叉鏈表則需從根開始，采用一定的巡查方法進行搜索。2) 二叉鏈表的類型定義typedef struct BiTNodeElemType struct BiTNodedata;*lchild, *rchild;/*左右孩子指針*/BiTNode, *BiTree;用3) 二叉鏈表的鏈域若有n個結(jié)點，則共有2

20、n個鏈域；其中n-1不為空，指向孩子。4) 二叉樹(鏈式存儲)的創(chuàng)建輸入序列與二叉樹的映射關(guān)系gf G(1)完全二叉樹的順序映射通過補虛結(jié)點，將一般的二叉樹轉(zhuǎn)變成完全二叉樹，再對該完全二叉樹的結(jié)點按 自上而下、自左至右進行輸入。(2)二叉樹的先序遍歷通過補虛結(jié)點，使二叉樹中各實際結(jié)點均具有左右孩子，再對該二叉樹按先序遍 歷進行輸入。(3)二叉樹的兩種遍歷序列：先序 +中序，后序+中序6.3 樹和森林1、樹的存儲結(jié)構(gòu)1) 雙親表示法針對每一結(jié)點，附設(shè)指示其雙親位置的數(shù)據(jù)域。采用#define MAX_TREE_SIZE 100typedef struct PTNodeElemTypedata;i

21、ntparent;PTNode;typedef structPTNodenodesMAX_TREE_SIZE;intn;PTree;順序表(非順序映像)。/*樹的最大結(jié)點數(shù)*/*結(jié)點數(shù)*/2)孩子表示法各結(jié)點的孩子數(shù)是不定的，用順序表表示必須給出樹的度的最大值，以及每一結(jié)點的 實際度數(shù)，空間浪費大。故以 鏈表存儲每一結(jié)點的所有孩子的位置信息。typedef struct CTNodeintchild;struct CTNode*next;/*孩子結(jié)點*/*孩子結(jié)點的位置編號*/*下一個孩子結(jié)點*/21*ChildPtr;typedef structTElemTypedata;ChildPtrf

22、irstchild;/*孩子鏈表的頭指針*/CTBox; typedef structCTBoxnodesMAX_TREE_SIZE;intn, r;/*結(jié)點數(shù)和根的位置*/CTree;3） 孩子兄弟法 二叉鏈表表示。針對每一結(jié)點，引入其 第一個孩子 和下一個右兄弟 的位置域。typedef struct CSNodeElemType data;struct CSNode *firstchild, *nextsibling; /* 第一個孩子、下一個兄弟指針 */ CSNode, *CSTree;2、森林與二叉樹的轉(zhuǎn)換森林用孩子兄弟法表示，形成二叉鏈表，可以將它理解為一個二叉樹的二叉鏈表；二叉

23、樹用二叉鏈表表示，可以將該二叉鏈表理解為孩子兄弟鏈表，從而獲得森林。6.4二叉樹的先|中|后序遍歷算法1、遍歷對于二叉樹中的結(jié)點，有且僅訪問一次遍歷的規(guī)律性：L（左子樹）、D（根卜R（右子樹）的排列上m限定L在R前訪問（有對稱關(guān)系的，只須考慮其中的一種 先（根）序遍歷DLR中（根）序遍歷LDR,后（根）序遍歷LRD2、二叉樹遍歷的遞歸實現(xiàn)二叉樹的遞歸定義性質(zhì)，決定了它的很多算法都可用遞歸實現(xiàn)， 遍歷就是其中之一。對于二叉樹的遍歷，可以不去具體考慮各子問題（左子樹、根、右 子樹）的遍歷結(jié)果是什么，而去考慮如何由各子問題的求解結(jié)果構(gòu)成原 問題（二叉樹）的遍歷結(jié)果一一 遞歸規(guī)律的確定。必須注意的是，

24、當(dāng)二 叉樹小到一定程度，即空樹時，應(yīng)直接給出解答一一遞歸結(jié)束條件及處理。三種遍歷的區(qū)別（右圖）：所經(jīng)過的搜索路線是相同的；只是訪問結(jié)點的時機不同。每一結(jié)點在整個搜索路線中會經(jīng)過3次（第一次進入到該結(jié)點、由左子樹回溯到該結(jié)點、由右子樹回溯到該結(jié)點），如在第一次遇到時就訪問該結(jié)點，那么稱之為先序；第二次經(jīng)過時訪問為 中序；第三次經(jīng)過時訪問則為 后序。1) 先序遍歷Status PreOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) ) if ( T != NULL )if ( Visit(T - >data)if ( PreOrd

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

26、isit ) 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 - >lchild, Visit )if ( Visit(T - >data) )zjif ( InOrderTraverse( T - >rchild, Visit ) )oreturn OK;三return E

27、RROR;3三else return OK;916.5先|后1中序遍歷的應(yīng)用擴展利用二叉樹的遍歷算法，適當(dāng)修改訪問結(jié)點操作的內(nèi)容，可以得到求解許多問題的算法。二叉樹的創(chuàng)建（基于先序遍歷）二叉樹的線索化查找指定結(jié)點：在訪問結(jié)點時，判斷當(dāng)前訪問的結(jié)點是否是指定的結(jié)點，若是則返回該結(jié)點位置，否則繼續(xù)遍歷；查找位于某種遍歷次序中的第k位的結(jié)點：遍歷前，引入一計數(shù)器，用來統(tǒng)計已訪問過的結(jié)點數(shù)，初值為 0;在訪問結(jié)點時，將該計數(shù)器增1,并看是否達到k,；求葉子結(jié)點的數(shù)目：遍歷前，引入葉子結(jié)點計數(shù)器，初值為0;訪問結(jié)點時，將該計數(shù)器增1;遍歷結(jié)束，則計數(shù)器中的值即為所求解；判斷二叉樹中是否僅包含有度為2和0

28、的結(jié)點：訪問結(jié)點時，判斷該結(jié)點孩子的有無情況，求指定結(jié)點的層次：孩子結(jié)點的層次比其雙親結(jié)點層次多一；求二叉樹的高度：二叉樹的高度=max（左子樹的高度,右子樹的高度）+16.5.1 基于先序遍歷的二叉樹（二叉鏈）的創(chuàng)建”1 /【本例特征】如何基于二叉樹的先序、中序、后序遍歷的遞歸算法進行問題求解? 【思路】先序遍歷 PreOrderTraverse創(chuàng)建 CreateBiTree輸入二叉鏈表示的二叉樹的頭指針T帶虛結(jié)點的先序序列ch輸入的表現(xiàn)方式參數(shù)由輸入設(shè)備輸入 scanf（ &ch ）輸出對結(jié)點的訪問結(jié)果二叉鏈表示的二叉樹的頭指針T輸出的表現(xiàn)方式由輸出設(shè)備輸出變參空樹（遞歸結(jié)束）的條

29、件及處理（直接求解）T = NULLch = END_DATA ("虛結(jié)點的值)空T = NULL根結(jié)點的訪問（子問題直接求解）Visit( T - >data )T = ( BiTree)malloc( sizeof( BiTNode )T- >data = ch左子樹（使用遞歸調(diào)用的解）PreOrderTraverse( T - >lchild )CreateBiTree( T - >lchild )右子樹（使用遞歸調(diào)用的解）PreOrderTraverse( T - >rchild )CreateBiTree( T - >rchild )【算

30、法】見數(shù)據(jù)結(jié)構(gòu)（C語言版）» P131算法6.4。6.5.2 統(tǒng)計二叉樹中葉子結(jié)點的數(shù)目【本例特征】如何通過全局變量、變參、返回值三種渠道返回處理結(jié)果？【思路】在遍歷二叉樹時，對一些特殊的結(jié)點（無左右孩子）進行計數(shù)?？梢孕薷谋闅v算法的 結(jié)點訪問操作為對特殊結(jié)點的判定和計數(shù)過程，需要注意的是計數(shù)器的處理方式。可以有以下幾種計 數(shù)處理： 用遍歷函數(shù)的返回值傳出求得的葉子結(jié)點的數(shù)目； 為遍歷函數(shù)增加一個引用參數(shù)，用來傳出指定二叉樹的葉子結(jié)點數(shù)目。 引入全局的計數(shù)器，初始為 0；此處，遍歷次序的選擇對本算法沒有太大影響。【算法1全局的計數(shù)器】/ n為葉子結(jié)點的計數(shù)器int n=0;void

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

32、eaf ( T -> lchild );m J/訪問結(jié)點，葉子結(jié)點的判定和計數(shù)&儕'if ( T-> lchild=NULL && T -> rchild=NULL )n+;2n += leaf(T -> rchild);£G中return (n);【算法3通過引用參數(shù)返回】/引用參數(shù)n為T的葉子結(jié)點數(shù)void leaf(BiTree T, int &n)/利用二叉樹的后序遍歷n = 0;結(jié)if ( T != NULL )leaf (T-> lchild, n1);leaf (T-> rchild, n2);

33、亡又/訪問結(jié)點，葉子結(jié)點的判定和計數(shù)if ( T-> lchild=NULL && T -> rchild=NULL )n+;n += n1+ n2;6.5.3 求二叉樹的高度【思路】 二叉樹為空時，高度為 0; 若T不為空，則其高度應(yīng)為其左右子樹高度的最大值再加1。可以有以下幾種處理高度值的方法： 用遍歷函數(shù)值返回指定二叉樹的高度； 遍歷函數(shù)增加一個引用參數(shù)，用來傳出指定二叉樹的高度。 【算法1】/函數(shù)值為T的高度int high(BiTree T) if ( T = NULL ) return ( 0 );else return( max ( high (T -

34、> Ichild ), high (T -> rchild) ) +1 ); 【算法2】/引用參數(shù)h為T的高度void high(BiTree T, int &h),工/利用二叉樹的后序遍歷if ( T = NULL )h=0;else 7 fThigh(T-> lchild,h1);/?high(T-> rchild,h2);/ >h = max(h1, h2)+1;1白6.5.4 釋放二叉樹的所有結(jié)點空間【思路】二叉樹為空時，不必釋放；若T不為空，則先釋放其左右子樹的所有結(jié)點的空間，再釋放根結(jié)點的空間一一后序 若在釋放子樹的空間前，先釋放根結(jié)點的空間，

35、則需要將子樹的根結(jié)點的指針暫存到其他 變量；否則，無法找到子樹?！舅惴?】/此處T應(yīng)為引用參數(shù)，因為經(jīng)過本函數(shù)處理后，T的值發(fā)生了變化void deleteBiTree(BiTree &T)if ( T != NULL )deleteBiTree(T -> lchild );deleteBiTree(T -> rchild );0/訪問結(jié)點-> 釋放結(jié)點的空間free(T);不勾T = NULL;好 【算法2】 void deleteBiTree(BiTree &T) if ( T != NULL)/先序遍歷，暫存孩子結(jié)點指針T1 = T-> lchil

36、d; T2 = T ->rchild;/訪問結(jié)點-> 釋放結(jié)點的空間free(T);T = NULL;deleteBiTree(T1);deleteBiTree(T2);6.5.5 刪除并釋放二叉樹中以元素值為X的結(jié)點作為根的各子樹【本例特征】如何選擇二叉樹的先序、中序、后序遍歷來解決問題，它們對問題求解有何影響？【思路】整個過程分為兩個方面：遍歷中查找元素值為x的結(jié)點查到該結(jié)點時，調(diào)用 6.5.3的算法釋放子樹空間。需要考慮的問題是：如何將全部的結(jié)點找到并釋放？外層查找采用的遍歷次序?qū)Ρ舅惴ㄓ?何影響？從以下3個算法中可以看出，利用先序遍歷是最合適的；中序和后序，存在一定的多 余

37、操作。【算法1】void deleteXTree(BiTree &T, ElemType x)/基于先序的查找if ( T != NULL )，=/訪問結(jié)點-> 判斷是否為指定結(jié)點-> 釋放樹空間if ( T->data= x ) deleteBiTree(T);三 t7 telse/此處else不能省略deleteXTree(T -> lchild, x);*deleteXTree(T -> rchild, x); 志I不Pte【算法2】void deleteXTree(BiTree&T, ElemType x)3l/基于中序的查找if ( T

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

39、余deleteXTree(T-> rchild, x);/ 若 T-> data= x,則此步驟多余/訪問結(jié)點-> 判斷是否為指定結(jié)點-> 釋放樹空間if ( T -> data = x ) deleteBiTree(T);I6.5.6 求位于二叉樹先序序列中第k個位置的結(jié)點的值【本例特征】多個返回結(jié)果如何處理？【思路】待查找的結(jié)點的存在性：當(dāng)二叉樹為空樹，或者k非法時，待查找的結(jié)點是不存在的函數(shù)應(yīng)返回待查找的結(jié)點是否存在的狀態(tài)指示：TRUE-存在，F(xiàn)ALSE-不存在當(dāng)待查找的結(jié)點存在時，需進一步返回該結(jié)點的值問題1:該算法需要返回多個值，如何處理？答：一種做法是

40、用返回值返回存在性，用變參返回值。問題2:該算法可以基于二叉樹的先序遍歷的遞歸算法來構(gòu)造，如何知道當(dāng)前訪問的結(jié)點是先序序列中的第幾個結(jié)點？答：引入計數(shù)器，對于該計數(shù)器可以采用全局變量來存儲，也可以通過變參來處理?！舅惴ā縎tatus PreorderKnode(BiTree T, int k, ElemType &e, int &count)輸入：T為二叉鏈表示的二叉樹，k為待查找的結(jié)點在先序序列中的位序(14由，假設(shè)/為二叉樹T中的結(jié)點個數(shù)/輸出：返回值 一TRUE:待查找的結(jié)點存在；FALSE:待查找的結(jié)點不存在/e-當(dāng)待查找的結(jié)點存在時，該結(jié)點的值通過e帶回/中間變量：c

41、ount記錄當(dāng)前已經(jīng)訪問過的結(jié)點個數(shù)3if ( T=NULL) return FALSE;三 / Lj >count+;/訪問結(jié)點對已訪問的結(jié)點進行計數(shù)if (count=k )/判斷該結(jié)點是否是待查找的結(jié)點卷心e = T-> data;/return TRUE; /查到，則設(shè)置 e,并返回 TRUEelse if (count > k)dreturn FALSE; /計數(shù)器count已經(jīng)超出k(當(dāng)k<0時)，則直接返回 FALSE else if (PreorderKnode(T->lchild, k, e, count)=FALSE) / 在左子樹中查找ret

42、urn PreorderKnode(T->rchild, k, e, count); / 若未找到，則在右子樹中查找return TRUE;J1結(jié)【調(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é)點在某種遍歷次序下的直接前驅(qū)和直接后繼信息4)擴展二叉鏈的結(jié)點：lchildltagdatartagrchildltag : 0一結(jié)點的左孩子；1一結(jié)點的直接前驅(qū)rtag :

43、 0一結(jié)點的右孩子；1 一結(jié)點的直接后繼5)名詞：線索鏈表、線索、線索二叉樹、線索化6）類型定義typedef enum Link, Thread PointerTag; Link=0:指針，Thread=1:線索typedef struct BiThrNodeElemTypedata;struct BiThrNode *lchild, *rchild;PointerTagltag, rtag;BiThrNode, *BiThrTree;為二叉樹的線索鏈表增加一個頭結(jié)點，/左右孩子指針/左右標志令其lchild域指向二叉樹的根結(jié)點,rchild域指向中（前/后）序遍歷時訪問的最后一個結(jié)點；中序

44、序列中的第一個結(jié)點的lchild域和最后一個結(jié)點的rchild域指向頭結(jié)點。2、在線索樹上進行遍歷（P133）3、中序線索化二叉樹（二叉樹的中序遍歷算法的應(yīng)用）InOrderThreading（BiThrTree &thrt, BiThrTree T）過程：分配頭結(jié)點、頭結(jié)點域的賦值、調(diào)用InThreading（）線索化、填充頭結(jié)點的rchild域引入全局指針pre保留中序遍歷時剛剛訪問過的結(jié)點，這樣便于處理pre指向的結(jié)點與當(dāng)前要訪問的結(jié)點中的鏈，使這兩個結(jié)點滿足前驅(qū)-后繼的關(guān)系。InThreading（）用來遞歸地進行二叉鏈的中序線索化，故 pre的初始化不應(yīng)在InThreadin

45、g（） 中進行，而可以放在 InOrderThreading（）中進行。中序遍歷 InOrderTraverse中序線索化二叉樹InThreading輸入二叉鏈表示的二叉樹的頭指針T線索二叉鏈表示的二叉樹的頭指針p輸入的表現(xiàn)方式參數(shù)參數(shù)一.輸出對結(jié)點的訪問結(jié)果修改p指向的結(jié)點的鏈域輸出的表現(xiàn)方式由輸出設(shè)備輸出參數(shù)空樹（遞歸結(jié)束）的 條件及處理（直接求解）T = NULLp = NULL* *空空左子樹（使用遞歸調(diào)用的解）InOrderTraverse( T - >lchild )InThreading( p - >lchild )根結(jié)點的訪問（子問題直接求解）Visit( T -

46、>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 - >rchild )6.5.8樹和森林的遍歷樹：先序、后序，不提中序。用孩子-兄弟法表示后，可以對該二叉鏈表進行先序遍歷和中序遍歷，獲得相應(yīng)樹的先序

47、和后序遍歷結(jié)果。樹的一些問題可以借鑒二叉樹的一些處理方法來解決。1、統(tǒng)計樹（森林）中葉子結(jié)點的個數(shù)孩子-兄弟法：每個結(jié)點包含一個指向第一個孩子和一個指向下一個右兄弟的指針域葉子結(jié)點的特征：結(jié)點的 firstchild為空統(tǒng)計葉子結(jié)點的個數(shù)一在遍歷的過程中統(tǒng)計firstchild域為空的結(jié)點的個數(shù)?！舅惴ā? n為葉子結(jié)點的計數(shù)器int n=0;void CSleaf(CSTree T)/利用樹的先序遍歷if ( T != NULL )CtTyJ/訪問結(jié)點，葉子結(jié)點的判定和計數(shù)if ( T -> firstchild = NULL )n+;CSleaf(T ->firstchild)

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

49、; 二胃3、求樹的度【算法】結(jié)/ degree表示表示樹的度void CSDegree(CSTree T, int &degree)/利用二叉樹的先序遍歷/ d表示T指向的結(jié)點的度if ( T = NULL ) degree = 0;elseif ( T -> firstchild = NULL ) d = 0;elsed = 1; p = T -> firstchild;while ( p -> nextsibling != NULL )p = p-> nextsibling; d+;CSDegree (T-> firstchild, d1);CSDeg

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

51、元素為二叉樹的結(jié)點指針I(yè)nitQueue(Q);7<.if ( T != NULL )1口/訪問根自if ( !Visit( T -> data ) ) return ERROR;總 F-l/ EnQueue()為入隊函數(shù)，T為待入隊的元素EnQueue(Q, T);3 丈士/從隊列中取已被訪問的、但其左右孩子尚未訪問的結(jié)點指針，訪問其孩子 while( !QueueEmpty(Q) )/隊不為空，則尚有未訪問其孩子的結(jié)點/ DeQueue()為出隊函數(shù)，它將原隊頭元素作為返回值返回p = DeQueue (Q);： ' / i/訪問左孩子if ( p-> lchil

52、d != NULL ) n 不-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é)點； 判斷二叉樹是否為完全

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

54、udgeCBT(BiTree T)Jew/初始化隊列和標志量 bFlagInitQueue (Q); bFlag = TRUE;工田if ( T != NULL )/ZEnQueue(Q, T);while ( !QueueEmpty(Q) )/隊不為空，則尚有未訪問其孩子的結(jié)點p = DeQueue(Q);p / ffif ( bFlag = FALSE ) /前驅(qū)結(jié)點缺左孩子，則若該結(jié)點有孩子，則此樹非完全二叉樹if ( p->lchild!=NULL | p -> rchild!=NULL ) return FALSE;else if ( p -> lchild = NULL ) 巨./第一次遇到結(jié)點缺左孩子bFlag = FALSE;17/若有右孩子，不滿足 1),則非完全二叉樹if ( p -> rchild != NULL )return FALSE;%else if ( p -> lchild != NULL ) .