【正文】 (A,L)() ()退棧， (A,L) (B,R)入棧 (A,L) (B,R) (E,L)入棧 (A,L) (B,R) (E,L) (E,L)退棧 (A,L) (B,R) (E,R)入棧 (A,L) (B,R) (E,P) (E,R)退棧 (A,L) (B,R) 訪問 E (B,R)退棧 (A,L) 訪問 B (A,L)退棧 (A,R)入棧 (A,R) (C,L)入棧 (A,R) (C,L) (C,L)退棧 (A,R) (C,R)入棧 (A,R) (C,R) (C,R)退棧 (A,R) 訪問 C (A,R)退棧 訪問 A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 課堂練習(xí) 前序遍歷序列： EDACBGFE 中序遍歷序列： ADCBEFHG 試畫出滿足以上序列的二叉樹 課堂練習(xí) 中序遍歷序列： ADCBHFEG 后序遍歷序列： ABCDEFGH 試畫出滿足以上序列的二叉樹 二、線索二叉樹 (Threaded Binary Tree) 目的 ：利用二叉樹的空指針保存遍歷序列的前驅(qū)和后繼。} //訪問 p else { push((p, R))。 if (tag==‘R’) { visite(pdata)。 //出棧頂元到 e中 p=。 //指向根 while (p || !StackEmpty(S)) { if (p) { push((p, L))； // p帶 L入 棧 p=plchild。A 訪問： C B E G D F p=NULL (13) 例 A B C D E F G i 訪問： C B E G D F A p (14) 例 A B C D E F G i 訪問： C B E G D F A p=NULL (15) 例 非遞歸后序遍歷二叉樹的算法思想 建立棧 stack； 1. P指向根； 2. 當(dāng) p不空 且 stack 不空時反復(fù)做： 若 p不空 ： (p,L) 入 棧 。A amp。D 訪問： C B E G p (10) 例 A B C D E F G i amp。G 訪問： C B E P=NULL (9) 例 A B C D E F G i amp。A amp。A amp。D amp。D 訪問： C B p (6) 例 A B C D E F G i amp。A 訪問： C B (5) 例 A B C D E F G i amp。A amp。B amp。B (2) 例 A B C D E F G p i amp。A (1) 例 A B C D E F G p i amp。 p指向左子女； 否則 ： ? 出棧頂元素到 p中； ? 訪問 p； ? p指向右子女； 4. 結(jié)束 如何進(jìn)行前序遍歷？ Void lnorderTraverse(BiTree BT) { ／／ 采用二叉鏈表存儲結(jié)構(gòu)，中序遍歷二叉樹 T的非遞歸算法 . InitStack(S)； p=BT； while(p||!StackEmpty(S)) { if(p) { push(S， p)； p=plchild； }//根指針進(jìn)棧，遍歷左子樹 else { ／／ 根指針退棧，訪問根結(jié)點，遍歷右子樹 pop(S， p)； visit(p))。 Boolean StackEmpty(S)。 push(S,p)。 A B C E F H G D I * * * * * * * * * 三種遍歷的訪問位置對比： 三種遍歷的路線完全一樣，只是訪問時間不同； 前序：第一次經(jīng)過 * 時訪問 中序：第二次經(jīng)過 時訪問 后序：第三次經(jīng)過 amp。 amp。 amp。 amp。 amp。 amp。 amp。 amp。 amp。 ／／ 構(gòu)造右于樹 } return OK； }／／ CreateBiTree A B C D A BT B C D ^ ^ ^ ^ ^ 遍歷二叉樹的 非遞歸算法： 我們先觀察一下三種遍歷行走的路線 A B C E F H G D I * * * * * * * * * 前序遍歷 NLR A B C E F H G D I 中序遍歷 LNR amp。 ／／ 生成根結(jié)點 CreateBiTree(BTlchild)。BT) { //按先序次序輸入二叉樹中結(jié)點的值 (一個字符 )，空格字符表示空樹， 構(gòu)造二叉鏈表表示的二叉樹 T. scanf(amp。 3. 建立左子樹和右子樹。 D B F E A C 該擴充二叉樹的前序遍歷序列是：ABD**EF***C** 該算法是一遞歸算法，遞歸三要素： 1. 遞歸出口：當(dāng)遇到 *時，是空。 }// } // end of PreOrderTraverse 請同學(xué)們自己寫出 InOrderTraverse(BT) 和 PostOrderTraverse(BT) 建立二叉樹 建立二叉樹的方法很多，我們給出 以前序遍歷序列 建 立二叉樹的方法，但該序列是 擴充二叉樹 的前序遍歷 序列。 PreOrderTraverse(BTlchild)。 算法思想 中序遍歷： 若 BT非空，則： ； ； ； 算法思想 后序遍歷： 若 BT非空，則： ； ； ； 遍歷二叉樹和 線索二叉樹 A B C E F H G 例 6 前序遍歷 (NLR)序列： A B E H G C F 中序遍歷 (LNR)序列： E B G H A F C 后序遍歷 (LRN)序列： E G H B F C A 算法思想 前序遍歷： 若 BT非空，則： ； ； 。 因二叉樹是非線性結(jié)構(gòu)， 每個結(jié)點可能有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。 二叉樹的存儲結(jié)構(gòu) BiTNode: A B C E F H G 二 、二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) (三叉鏈表 ) 二叉樹的存儲結(jié)構(gòu) A B C E H F G 三叉鏈表 BT 遍歷二叉樹和 線索二叉樹 按照某種搜索路徑 訪問 二叉樹中的所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。 struct BiTNode *lchild,*rchild,*parent。 }BiTNode, *BiTree。 否則無右子女； ? ?2i1 2 3 4 6 5 i i+1 2i 2i+1 ? ?2i 二叉樹的性質(zhì) 2i+2 二叉樹的存儲結(jié)構(gòu) 一 、二叉樹的順序存儲 完全二叉樹的順序存儲： A B C E F H 1 2 3 4 5 6 A B C E H F 0 1 2 3 4 5 6 ST[ ] 根據(jù)性質(zhì) 5知： ST[i] 的雙親是 ST[ ], 左子女是 ST[2*i]， 右子女是ST[2*i+1]． ? ?2/i一、二叉樹的順序存儲 A B C E F H 0 1 2 3 4 5 6 7 8 9 ST[ ] 根據(jù)性質(zhì) 5知： ST[i] 的雙親是 ST[ ], 左子女是 ST[2*i],右子女是 ST[2*i+1]. A B C E F H 1 2 3 4 7 9 ? ?2/i 二叉樹的存儲結(jié)構(gòu) 這樣太浪費空間 ,適合完全二叉樹 二、 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) (二叉鏈表 ) typedef struct BiTNode{ ElemType data。 若 i1， 則它的雙親是 （ 2）若 2i ≤ n， 則結(jié)點 i的左子女是 2i。若它是雙親 的右子女 ,則它的編號是雙親編號的 2倍 +1. 二叉樹的性質(zhì) A B C D E F H 1 2 3 4 5 6 7 編號的滿二叉樹 完全二叉樹 (Complete Binary Tree): 深度為 k的滿二叉樹 , 刪去第 k層上最右邊的 j(0 j2k1)個結(jié)點 ,就得到一個深度為 k 的完全二叉樹 . 編號的完全二叉樹 : 與滿二叉樹編號相同 ? 二叉樹的性質(zhì) 1 A B C E 2 3 4 A B C D E 1 2 3 4 5 A B C E F H 1 2 3 4 5 6 F 7 性質(zhì) 4: 具有 n個結(jié)點的完全二叉樹 ,其深度為 。 i=k+1時 ,二叉樹上每個結(jié)點至多有兩棵子樹，則第 i 層的結(jié)點數(shù) = 2k1? 2 = 2(k+1)1=2i1 。 基本操作 : LevelOrderTraverse(T)； 初始條件：二叉樹 T存在 。 PostOrderTraverse(T)； 初始條件：二叉樹 T存在 。 基本操作 : InOrderTraverse(T)； 初始條件：二叉樹 T存在。 PreOrderTraverse(T)； 初始條件：二叉樹 T存在。 基本操作 : DeleteChild(T， p， LR)； 初始條件：二叉樹 T存在 ， p指向 T中某個結(jié)點 ， LR為 0或 1。 操作結(jié)果：根據(jù) LR為 0或 1，插入 c為 T中 p所指結(jié)點的左或 右子樹。若 e是 T的右孩子或無右兄弟， 則返回 “ 空 ” 。 Rightsibling(T， e)； 初始條件：二叉樹 T存在， e是 T中某個結(jié)點。 操作結(jié)果：返回 e的左兄弟。 操作結(jié)果：返回 e的右孩子 ,若 e無右孩子 ， 則返回 “ 空 ” 。 操作結(jié)果：返回 e的左孩子 ， 若 e無左孩子 ， 則返回 “ 空 ” 。 操作結(jié)果：若 e是 T的非根結(jié)點 ， 則返回它的雙親 ， 否則返回 “ 空 ”。 操作結(jié)果：結(jié)點 e賦值為 value。 基本操作 : Assign(T， amp。 Value(T， e) 初始條件：二叉樹 T存在 ， e是 T中某個結(jié)點 。 Root(T)； 初始條件 : 二叉樹 T存在 。 操作結(jié)果：若 T為空二叉樹 ,則返回 TRUE,否則 FALSE. BiTreeDepth(T)； 初始條件：二叉樹 T存在 。 操作結(jié)果：將二叉樹 T清為空樹 。 ClearBiTree(amp。 初始條件： definition給出二叉樹 T的定義 。 CreatBiTree(amp。 初始條件：二叉樹 T存在 。 DestroyBiTree(amp。T)。 數(shù)據(jù)關(guān)系 R：