【正文】 數(shù)，因此， k = ?log2n? + 1 ? 性質(zhì) 4 ： 具有 n 個結(jié)點的完全二叉樹的 深度 為 ?log2n? +1 則根據(jù)性質(zhì) 2得 2k11 n ≤ 2k 1 2k1≤ n 2k 38 ?性質(zhì) 5 ： 若對含 n 個結(jié)點的完全二叉樹從上到下且從左至右進(jìn)行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點： (1) 若 i=1，則該結(jié)點是二叉樹的根，無雙親 , 否則，編號為 ?i/2? 的結(jié)點為其 雙親 結(jié)點 。 (2) 若 2in，則該結(jié)點無左孩子， 否則，編號為 2i 的結(jié)點為其 左孩子 結(jié)點； (3) 若 2i+1n，則該結(jié)點無右孩子結(jié)點， 否則，編號為 2i+1 的結(jié)點為其 右孩子 結(jié)點 。 39 二叉樹的存儲結(jié)構(gòu) 二、 二叉樹的鏈?zhǔn)酱鎯Ρ硎? 一、 二叉樹的順序存儲表示 40 二叉樹的順序存儲結(jié)構(gòu)中結(jié)點的存放次序是：對該樹中每個結(jié)點進(jìn)行編號 ,其編號從小到大的順序就是結(jié)點存放在連續(xù)存儲單元的先后次序。若把二叉樹存儲到一維數(shù)組中 ,則該編號就是下標(biāo)值加 1(注意 ,C/C++語言中數(shù)組的起始下標(biāo)為 0)。樹中各結(jié)點的編號與等高度的完全二叉樹中對應(yīng)位置上結(jié)點的編號相同。 根據(jù)二叉樹的性質(zhì) 2，有 k個結(jié)點的二叉樹，需要長度為 2k1 的一維數(shù)組 一、 二叉樹的順序存儲表示 41 完全二叉樹 一般二叉樹 的順序表示 的順序表示 二叉樹的順序表示 1 1 2 3 4 5 6 7 8 9 10 14 1 2 3 4 6 7 8 9 12 14 2 4 8 9 10 5 6 7 3 1 2 3 7 6 4 8 9 12 5 10 11 13 42 實現(xiàn)： 按滿二叉樹中結(jié)點的編號，依次存放二叉 樹中的數(shù)據(jù)元素。 特點： 結(jié)點間關(guān)系蘊含在其存儲位置中； 浪費空間，適于存滿二叉樹和完全二叉樹。 極端情形 : 只有右單支的二叉樹 1 3 7 15 31 1 3 7 15 31 43 二、二叉樹的鏈?zhǔn)酱鎯Ρ硎? 1. 二叉鏈表 2．三叉鏈表 3．線索鏈表 44 typedef struct BiTNode { // 結(jié)點結(jié)構(gòu) TElemType data。 struct BiTNode *lchild, *rchild。 // 左右孩子指針 } BiTNode, *BiTree。 C 語言的類型描述如下 : 1. 二叉鏈表 lchild data rchild 結(jié)點結(jié)構(gòu) : 45 A D E B C F ? ? ? ? ? ? ? root A B D C F E 在有 n個結(jié)點的二叉鏈表中，有 ？ 個空指針域 n+1 46 typedef struct TriTNode { // 結(jié)點結(jié)構(gòu) TElemType data。 struct TriTNode *lchild, *rchild, *parent。 // 左右孩子指針、 雙親指針 } TriTNode, *TriTree。 parent lchild data rchild 結(jié)點結(jié)構(gòu) : C 語言的類型描述如下 : 2． 三叉鏈表 47 A D E B C F ? ? ? ? ? ? ? root ? A B D C F E 48 練習(xí)：畫出下面二叉樹的三叉鏈表。 a b c d e f g h 49 二叉樹的遍歷 50 一、問題的提出 二、先左后右的遍歷算法 三、算法的遞歸描述 四、中序遍歷算法的非遞歸描述 五、遍歷算法的應(yīng)用舉例 51 遍歷 ： 順著某一條搜索路徑 巡訪 二叉樹中的結(jié)點，使得每個結(jié)點 均被訪問一次 ，而且 僅被訪問一次 。 即找一個完整而有規(guī)律的走法，得到樹中所有結(jié)點的一個線性排列。 一、問題的提出 “訪問 ”的含義可以很廣， 如：輸出結(jié)點的信息等。 52 “遍歷 ”是任何類型均有的操作， 對線性結(jié)構(gòu)而言，只有一條搜索路 徑 (因為每個結(jié)點均只有一個后繼 )， 故不需要另加討論。而二叉樹是非 線性結(jié)構(gòu)， 每個結(jié)點有兩個后繼 ， 則存在 如何遍歷 即按什么樣的 搜索 路徑 遍歷的問題。 53 對 “ 二叉樹 ” 而言 ， 可以有三條搜索路徑： ? 設(shè) 訪問根結(jié)點 記作 D ? 遍歷根的左子樹 記作 L 遍歷根的右子樹 記作 R ? 則可能的遍歷次序有 前序 DLR 鏡像 DRL 中序 LDR 鏡像 RDL 后序 LRD 鏡像 RLD D L R LDR、 LRD、 DLR RDL、 RLD、 DRL 54 若二叉樹為空樹，則空操作；否則， （ 1）訪問根結(jié)點； （ 2）先序遍歷左子樹； （ 3）先序遍歷右子樹。 先 （根） 序的遍歷算法： 55 A D B C D L R A D L R D L R B D C D L R 先序遍歷序列： A B D C 先序遍歷 : 56 若二叉樹為空樹，則空操作；否則， （ 1）中序遍歷左子樹； （ 2）訪問根結(jié)點； （ 3）中序遍歷右子樹。 中 （根） 序的遍歷算法： 57 A D B C L D R B L D R L D R A D C L D R 中序遍歷序列： B D A C 中序遍歷 : 58 若二叉樹為空樹，則空操作；否則， （ 1）后序遍歷左子樹； （ 2）后序遍歷右子樹； （ 3）訪問根結(jié)點。 后 （根） 序的遍歷算法： 59 A D B C L R D L R D L R D A D C L R D 后序遍歷序列： D B C A 后序遍歷 : B 60 A B C D E F G H K 分 析 ： 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 61 三、算法的遞歸描述 void PreOrder (BiTree T, void( *visit)(TElemTypeamp。 e)) { // 先序遍歷二叉樹 if (T) { Visit(Tdata) 。 // 訪問結(jié)點 PreOrder(Tlchild, Visit)。 // 遍歷左子樹 PreOrder(Trchild, Visit)。// 遍歷右子樹 } } 62 例 假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲 ,試設(shè)計一個算法 ,輸出一棵給定二叉樹的所有葉子結(jié)點 。 解：輸出一棵二叉樹的所有葉子結(jié)點的遞歸模型 f()如下： f(b)：不做任何事件 若 b=NULL f(b)：輸出 *b結(jié)點的 data域 若 *b為葉子結(jié)點 f(b)： f(blchild)。f(brchild) 其他情況 63 void DispLeaf(BTNode *b) { if (b!=NULL) { if (blchild==NULL amp。amp。 brchild==NULL) printf(%c ,bdata)。 else { DispLeaf(blchild)。 DispLeaf(brchild)。 } } } 64 void pre(BiTree t) { if (t!=NULL) { printf (%d\t,tdata)。 pre(tlchild)。 pre(trchild)。 } } 主程序 Pre( T ) 返回 返回 pre(T R)。 返回 返回 pre(T R)。 A C B D T B printf(B)。 pre(T L)。 T A printf(A)。 pre(T L)。 T D printf(D)。 pre(T L)。 T C printf(C)。 pre(T L)。 返回 T 左是空返回 pre(T R)。 T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R)。 先序序列： A B D C 遞歸算法的執(zhí)行過程 T 65 a b c d e + / 如圖二叉樹表示表達(dá)式 : ( a + b ) c – d / e 二叉樹的先序遍歷序列為： – + a b c / d e 二叉樹的中序遍歷序列為： a + b c – d / e 二叉樹的后序遍歷序列為： a b + c d e / – 前綴表達(dá)式 中綴表達(dá)式 后綴表達(dá)式 二叉樹與表達(dá)式 66 void InOrderTraverse (BiTree T, void (*visit) (TelemTypeamp。 e)) { InitStack(S)。 p=T。 while( p || !StackEmpty(S) ){ // 找到最左下的結(jié)點 if (p) { Push(S,p)。 p=plchild。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點，遍歷右子樹 Pop(S,p)。 if ( !visit(pdata) ) return ERROR。 p=prchild。 } //else } // while return OK。 }// InOrderTraverse 四、中序遍歷算法的非遞歸描述 67 非遞歸算法的執(zhí)行過程 A B C D E F G p i A (1) A B C D E F G p i A B (2) A B C D E F G p i A B C (3) p=NULL pC p=NULL A B C D E F G i A B 訪問： C (4) while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點 if (p) { Push(S,p)。 p=plchild。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點，