【正文】 第 6章 樹和二叉樹 4. 層次遍歷二叉樹 void LevelOrderTraverse(BiTree bt) {//二叉樹 bt采用二叉鏈表存儲，對 bt進行層次遍歷 if(bt) { InitQueue(Q)。 printf(pdata)。amp。 printf(pdata)。 if(GetTop(S, p) == NULL) { Pop(S, p)。 //空指針退棧 if(!StackEmpty(S)) { GetTop(S, p)。p) Push(S, plchild)。 //根指針進棧 while(!StackEmpty(S)){ while(GetTop(S,p)amp。 } }//while }//if }// InOrderTraverse 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 后序遍歷的調(diào)用過程： A D B C L R D L R D L R D D B L R D C A 后序遍歷序列： D B C A 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 后序遍歷二叉樹的非遞歸算法（方法一） : void PostOrderTraverse(BiTree bt){ //二叉樹 bt采用二叉鏈表存儲，對 bt進行后序遍歷 InitStack(S)。 printf(pdata)。 //向左一直走到盡頭 Pop(S, p)。amp。 Push(S, bt)。 else Pop(S, p)。 if(prchild) Push(S, prchild)。 Push(S, NULL)。 } }//while }//if }// PreOrderTraverse 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 先序遍歷二叉樹的非遞歸算法（方法二） : void PreOrderTraverse(BiTree bt){ //二叉樹 bt采用二叉鏈表存儲，對 bt進行先序遍歷 if(bt){ InitStack(S)。 //空指針退棧 if(!StackEmpty(S)) { Pop(S,p)。 Push(S, plchild)。amp。 Push(S, bt)。 //訪問根結(jié)點 } }// PostOrderTraverse 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 表達式求值 ? (a+b)*(cd)+e/f ? 先序遍歷： +*abcd/ef (前綴表達式 ) ? 中序遍歷： a+b*cd+e/f (中綴表達式 ) ? 后序遍歷： ab+cd*ef/+ (后綴表達式 ) + * / d + a b 12 e f c 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 通過上述介紹可以看到：三種遍歷算法遞歸執(zhí)行的 (指針 )路線相同，只是 訪問 根結(jié)點的時機不同。 PostOrderTraverse(btrchild)。 //訪問根結(jié)點 InOrderTraverse(btrchild)。 } }// PreOrderTraverse 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 2. 中序遍歷二叉樹 中序遍歷二叉樹的操作定義 : 若二叉樹為空，則空操作；否則 1) 中序遍歷左子樹 (L)； 2) 訪問根結(jié)點 (D)； 3) 中序遍歷右子樹 (R) 中序遍歷二叉樹的遞歸算法 : void InOrderTraverse(BiTree bt){ //二叉樹 bt采用二叉鏈表存儲，對 bt進行中序遍歷 if(bt) { InOrderTraverse(btlchild)。 //訪問根結(jié)點 PreOrderTraverse(btlchild)。 } }//CreateBiTree 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 四、遍歷二叉樹 ?遍歷二叉樹：是指按某種 搜索路徑 訪問樹中每個結(jié)點，使得每個結(jié)點訪問且只被訪問一次。 CreateBiTree(btlchild)。 else { if(!(bt=(BiTNode *)malloc(sizeof(BiTNode)))) exit( 0 )。ch)。 B^C^三 叉 鏈 表D^^ACBEDFGE FG^^^A^ ^數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 例如按先序遍歷序列建立二叉樹的二叉鏈表，假設(shè)輸入的字符順序為： ABC□ □ DE □ G □ □ F □ □ □ （ □ 表示空格），建立的二叉樹如下圖所示： ACBEDFGvoid CreateBiTree(BiTree amp。 struct BiNode *lchild, *rchild, *parent。 //左、右孩子指針 }BiNode, *BiTree。 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 2 314 5 6 78 9 1 0完 全 二 叉 樹2 34 56 71非 完 全 二 叉 樹1 2 3 4 5 6 7 8 9 10 完全二叉樹的存儲結(jié)構(gòu) 7 1 2 3 4 5 0 0 0 0 6 非完全二叉樹的存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 2. 鏈式存儲結(jié)構(gòu) 二叉鏈表的存儲表示如下： typedef struct BiNode{ TElemType data。 define MAX_TREE_SIZE 20 typedef TElemType SqBiTree[MAX_TREE_SIZE+1]。 ?浪費空間：一個深度為 k的單支樹需要 2k1個存儲空間。 i / 22 i + 32 i + 22 i + 12 ii + 1i結(jié) 點 i和 i + 1 在 同 一 層 上2 i + 12 i2 i + 32 i + 2ii + 1結(jié) 點 i 和 i + 1 不 在 同 一 層 上……數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 補充性質(zhì) : n個節(jié)點的完全二叉樹中： 度為 1的節(jié)點數(shù)為 (n+1)%2 度為 0的節(jié)點數(shù)為 = ?(n+1)/2? 度為 2的節(jié)點數(shù)為 ?(n+1)/2? 1 n個節(jié)點的二叉樹： ?高最多 n ?最低 ?log2n? +1 (完全二叉樹 ) 12 34 5 6 78 9 1 0數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 三、二叉樹的存儲結(jié)構(gòu) 二叉樹的存儲結(jié)構(gòu)有多種，最常用的有兩種：順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)。 對于 i1可以分成兩種情況： ①設(shè)第 j層的第一個結(jié)點的編號為 i（由性質(zhì) 2可知 i=2j1），則其左孩子必為 j+1的第一個結(jié)點，其編號為 2j=2(2j1)=2i，若 2in，則無左孩子；其右孩子必為第 j+1層的第二個結(jié)點，其編號為 2i+1，若 2i+1n，則無右孩子。 3) 深度為 k的完全二叉樹，第 i(1 ≤i ≤k1)層上結(jié)點數(shù)等于 2i1 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6 7 1 2 3 4 5 6 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 性質(zhì) 4證明： 假設(shè)完全二叉樹的深度為 k，根據(jù)性質(zhì) 2和完全二叉樹的定義有 2k11n≤2k1 或 2k1≤n2k 于是 k1 ≤ log2n k，因為 k是整數(shù)，所以 k = ?log2n? +1。 而分 支是由度為 1和度為 2的結(jié)點射出， 所以 B=n1+2n2， 于是， n=B+1=n1+2n2+1 ② 由 ① 和 ②得： n0=n2+1 1 2 3 5 6 7 數(shù)據(jù)結(jié)構(gòu) 第 6章 樹和二叉樹 兩種特殊形態(tài)的二叉樹 ?滿二叉樹： 一棵深度為 k且有 2k1個結(jié)點的二叉樹 12 34 5 6 78 9 1 01 11 2 1 3 1 4 1 5?完全二叉樹： 深度為 k有 n個結(jié)點且每個結(jié)點都與深度為 k的滿二叉樹中編