【文章內(nèi)容簡介】 a + b * c – d – e / f 2. 中序遍歷二叉樹： 中序遍歷序列為 ： 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 52 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 Void inorder(treenode *t) { if(t!=NULL) { inorder(t–lchild)。 printf(―%c‖, t–data)。 inorder(t–rchild)。 } } 二叉樹的中序遍歷算法 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 53 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 中序遍歷遞歸算法 遞歸函數(shù)的調(diào)用過程 ? B C A Void inorder(A) { if(p!=NULL){ inorder(B)。 printf(A)。 inorder(null)。} } Void inorder(B) { if(p!=NULL){ inorder(null)。 printf(B)。 inorder(C)。} } Void inorder(null) { if(p!=NULL){} } Void inorder(null) { if(p!=NULL){} } Void inorder(C) { if(p!=NULL){ inorder(null)。 printf(C)。 inorder(null)。 } Void inorder(null) { if(p!=NULL){} } Void inorder(null) { if(p!=NULL){} } 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 54 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 中序遍歷二叉樹的非遞歸算法 init(S)。 p=root。 Do { while(p!=NULL) { PUSH(S,pdata)。 p=plchild。} if (!EMPTY(S)) { p=POP(S)。 Visit(pdata)。 p=prchild。 } } while(!EMPTY(S)||p!=NULL)。 B C D E A 3 2 1 0 C B A 3 2 1 0 B A 3 2 1 0 D A 3 2 1 0 A 3 2 1 0 E 3 2 1 0 CBDAE 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 55 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 若二叉樹不空則： （ 1）后序遍歷左子樹； （ 2）后序遍歷右子樹； （ 3）訪問根結(jié)點(diǎn)。 ＋ * a / b d c f e a b c d * + e f / 3. 后序遍歷二叉樹： 后序遍歷序列為： 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 56 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 Void postorder(treenode *t) { if(t!=NULL) { postorder(t–lchild)。 postorder(t–rchild)。 printf(―%c‖, t–data)。 } } 二叉樹的后序遍歷算法 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 57 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 層次遍歷是指： 從二叉樹的第一層開始，從上到下逐層遍歷， 同一層按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。 ＋ * a / b d c f e + / a * e f b – c d 4. 層次遍歷： 層次遍歷序列為： 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 58 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 ?用隊(duì)列 q[M]存放當(dāng)前訪問結(jié)點(diǎn) 1. 首先為根結(jié)點(diǎn)先入隊(duì) 2. 再每次從隊(duì)首取一個(gè)結(jié)點(diǎn)，訪問該結(jié)點(diǎn)并把它的孩子訪問順序入隊(duì)。 3. 重復(fù) 2，直到隊(duì)空為止。 按層次遍歷樹的思想 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 59 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 Void ccbls(JD *T) {JD *p, q[M]。 int j,f=1,w=1。 q[1]=T。 While(f=w) {p=q[f++]。 printf(pdata)。 for (j=0。jD。j++) If (pch[j]!=NULL) q[++w]=pch[j]。 } } A B C D E F H 輸出序列： ABCDEFH BCD f w A出隊(duì) CDEF f w B出隊(duì) EFH f w CD出隊(duì) A f w A入隊(duì) 按層次遍歷樹的算法及其模擬實(shí)現(xiàn) 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 60 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 若先序遍歷此二叉樹 ,按訪問結(jié)點(diǎn)的先后次序?qū)⒔Y(jié)點(diǎn)排列起來 ,其先序序列為： ？ ______________ ? 按中序遍歷 ,其中序序列為： ？ ______________ ? 按后序遍歷 ,其后序序列為： ？ ______________ A B E D C H I K J G F 示例 – 右圖所示的二叉樹 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 61 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 ?可恢復(fù)二叉樹的結(jié)點(diǎn)序列組合： （ 1）先序序列和中序序列 （ 2）中序序列和后序序列 ?不可恢復(fù)二叉樹的結(jié)點(diǎn)序列組合： 先序序列和后序序列 ——只能確定根結(jié)點(diǎn)，不能劃分左右子樹 由結(jié)點(diǎn)序列恢復(fù)二叉樹 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 62 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 由先序序列和中序序列恢復(fù)二叉樹 （ 1）由先序序列得到二叉樹的根結(jié)點(diǎn)； （ 2）由 (1)得到的根結(jié)點(diǎn)把中序序列分為兩個(gè)部分：左子樹中序序列和右子樹中序序列； （ 3）根據(jù) (2)得到的子樹中序序列找到對應(yīng)的左子樹先序序列和右子樹的先序序列； （ 4）重復(fù) (1)(2)(3) ，直到所得左、右子樹只含一個(gè)結(jié)點(diǎn)為止。 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 63 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 由結(jié)點(diǎn)序列恢復(fù)二叉樹 示例 ?方法： 先序序列： ABCDEFGH（ A是根） 中序序列： CBED A GHF 左子樹 右子樹 A B C D E F G H 以 A為根的左、右子樹先序序列示意圖： ?已知遍歷二叉樹的先序序列 ABCDEFGH和中序序列CBEDAGHF，請畫出該二叉樹： 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 64 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 ?同理由右子樹先序序列 FGH和右子樹中序序列GHF構(gòu)造 A的右子樹： A B F C D E G H A B F C D E G H ?由左子樹先序序列 BCDE和左子樹中序序列CBED構(gòu)造 A的左子樹 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 65 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 ? 已知一棵二叉樹： 先序遍歷二叉樹的結(jié)點(diǎn)序列為： A B D E C F G 中序遍歷二叉樹的結(jié)點(diǎn)序列為： D B E A F G C ? 要求畫出該二叉樹 A B C D E F G 練習(xí) 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 66 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 練習(xí)：已知一棵二叉樹的中根序列和后根序列分別為BDCEAFGH和 DECBHGFA，試畫出二叉樹。 第 7章 樹和二叉樹 A B F C G H D E 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 67 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 Void inorder(BNODE *T) { if(T!=NULL) { inorder(T–lchild)。 if (Tlchild!=null amp。amp。 Trchild!=null) printf(―%c‖, T–data)。 inorder(T–rchild)。 } } 二叉樹遍歷算法應(yīng)用示例 設(shè)計(jì)算法，按照中序次序輸出二叉樹 T中度為 2的結(jié)點(diǎn)的數(shù)據(jù)值 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 68 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 Void inorder(BNODE *T) { if(T!=NULL) { inorder(T–lchild)。 n++。 inorder(T–rchild)。 } } 二叉樹遍歷算法應(yīng)用示例 設(shè)計(jì)算法，求二叉樹 T的結(jié)點(diǎn)數(shù) 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 69 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 int high(BNODE *T) { if(T==NULL) return 0。 else return max(high(T–lchild), high(T–rchild))+1。 } 二叉樹遍歷算法應(yīng)用示例 設(shè)計(jì)算法，求二叉樹 T的高度 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 70 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 1. 線索二叉樹的定義 2. 線索二叉樹的結(jié)構(gòu) 3. 線索二叉樹的基本運(yùn)算 線索二叉樹 第 7章 樹和二叉樹 計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)教學(xué)組制作 71 數(shù)據(jù)結(jié)構(gòu) 首頁 上頁 目錄 前頁 后頁 末頁 ? 二叉樹的遍歷得到線性序列，這種先后關(guān)系是動態(tài)的，利用二叉鏈表的空指針域來保留這種前后關(guān)系 ? 有 n個(gè)結(jié)點(diǎn)的二叉鏈表，共 2n個(gè)指針域，其中 n1個(gè)非空，必有 n+1個(gè)空鏈域 ? 利