1、1數據結構數據結構 C C語言語言 AFEDCBG2 知識與技能知識與技能過程與方法過程與方法實現價值實現價值3 二叉樹遍歷二叉樹遍歷的應用。的應用。重重點點難難點點4新課引入新課引入- -遍歷的應用遍歷的應用1 課程講解課程講解- - 基礎知識基礎知識2教學提升教學提升- -課程總結課程總結4實踐內容實踐內容- -練習討論練習討論3鞏固鞏固拓展拓展- -課后作業課后作業55 3 (2+5) /(9-6)=7先算哪個呢？6將算術表達式畫將算術表達式畫成一棵二叉樹成一棵二叉樹/+36259它的中序遍歷序列為：它的中序遍歷序列為：3 * 2 + 5 / 9 6它的后序遍歷序列為：它的后序遍歷序列為

2、：2 5 + 3 * 9 6 / 中綴表達式（人的思維）后綴表達式（電腦的思維）()()7遍歷定義遍歷定義遍歷用途遍歷用途遍歷方法遍歷方法指按某條搜索路線遍訪每個結點且指按某條搜索路線遍訪每個結點且不重復（又稱周游）。不重復（又稱周游）。它是樹結構插入、刪除、修改、查它是樹結構插入、刪除、修改、查找和排序運算的前提，是二叉樹一找和排序運算的前提，是二叉樹一切運算的基礎和核心。切運算的基礎和核心。對每個結點的查看通常都是對每個結點的查看通常都是“先左后先左后右右” 。8二叉樹由根、左子樹、右子樹構成，定義為二叉樹由根、左子樹、右子樹構成，定義為D、 L、R以根結點為參照系以根結點為參照系注：注：

3、“先、中、后先、中、后”的意思是指訪問的結點的意思是指訪問的結點D D是先于子樹出是先于子樹出現還是后于子樹出現。現還是后于子樹出現。v D、 L、R的組合定義了六種可能的遍歷方案：的組合定義了六種可能的遍歷方案： LDR, LRD, DLR, DRL, RDL, RLDv 若限定若限定先左后右先左后右，則有三種實現方案：，則有三種實現方案： DLR LDR LRD先先序遍歷序遍歷 中中序遍歷序遍歷 后后序遍歷序遍歷 9ADBCD L RAD L RD L RBDCD L R先序遍歷序列：先序遍歷序列：A B D C先序遍歷先序遍歷(DLR):特點：任意一個結點均處在其子女結點的前面(根結點在

4、前)有什么特點？10ADBCD L RAD L RD L RBDCD L RF訪問根結點訪問根結點F先序先序遍歷根的左子樹遍歷根的左子樹F先序先序遍歷根的右子樹遍歷根的右子樹遞歸過程DLR( node *root )if (root !=NULL) printf(“%d”,root-data); DLR(root-lchild); DLR(root-rchild); return(0); 11ADBCL D RBL D RL D RADCL D R中序遍歷序列：中序遍歷序列：B D A C特點：根結點左右分別為左右子樹的所有結點.中序遍歷中序遍歷(LDR):討論中序遍歷思想及算法？12ADBC

5、后序遍歷后序遍歷(LRD):討論后序遍歷思想及算法？ L R DL R DL R DADCL R DB后序遍歷序列：后序遍歷序列： D B C A13三種遍歷算法總結三種遍歷算法總結LDR(node *root)if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);LRD (node *root)if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0);typede

6、f struct nodeint data; struct node *lchild,*rchild； node;node *root; DLR( node *root )if (root !=NULL) /非空二叉樹非空二叉樹 printf(“%d”,root-data); /訪問訪問D DDLR(root-lchild); /遞歸遍歷左子樹遞歸遍歷左子樹DLR(root-rchild); /遞歸遍歷右子樹遞歸遍歷右子樹 return(0); 14三種遍歷算法分析三種遍歷算法分析1. 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將print語句抹去，語句抹去，從遞歸

7、的角度看，這三種算法是完全相同的，或者說這三種從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的遍歷算法的訪問路徑是相同的，只是訪問結點的時機不同。訪問路徑是相同的，只是訪問結點的時機不同。從虛線的出發點到終點的路徑從虛線的出發點到終點的路徑上，每個結點經過上，每個結點經過3次次。第第1次次經過時訪問，是經過時訪問，是先序先序遍歷遍歷第第2次次經過時訪問，是經過時訪問，是中序中序遍歷遍歷第第3次次經過時訪問，是經過時訪問，是后序后序遍歷遍歷2. 2. 二叉樹遍歷的時間效率和空間效率二叉樹遍歷的時間效率和空間效率時間效率時間效率: : /每個結點只訪問一次每個結點只訪問一次空間效率空

8、間效率: : /棧占用的最大輔助空間棧占用的最大輔助空間精確值：樹深為精確值：樹深為k k的遞歸遍歷需要的遞歸遍歷需要k+1k+1個輔助單元個輔助單元AFEDCBG15實踐內容實踐內容-練習討論練習討論例例1：先序遍歷的結果是：先序遍歷的結果是：中序遍歷的結果是：中序遍歷的結果是：后序遍歷的結果是：后序遍歷的結果是： A B CD E口訣：口訣：D DLRLR先序遍歷，即先序遍歷，即先根再左再右先根再左再右L LD DRR中序遍歷，即中序遍歷，即先左再根再右先左再根再右LRLRD D后序遍歷，即后序遍歷，即先左再右再根先左再右再根16實踐內容實踐內容-練習討論練習討論ABCDEFGHK例例2：

9、先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A17知識應用知識應用-表達式計算表達式計算+*A*/EDCB先序遍歷結果先序遍歷結果+ * * / A B C D E前綴表示法前綴表示法中序遍歷結果中序遍歷結果A / B * C * D + E中綴表示法中綴表示法后序遍歷結果后序遍歷結果A B / C * D * E +后綴表示法后綴表示法層次遍歷結果層次遍歷結果+ * E * D / C A B例例3 3：用二叉樹表示算術表達式用二叉樹表示算術表達式18特別討論特別討論例：例：已

10、知一棵二叉樹的已知一棵二叉樹的中序序列中序序列和和后序序列后序序列分別是分別是BDCEAFHGBDCEAFHG 和和 DECBHGFADECBHGFA，請畫出這棵二叉樹。，請畫出這棵二叉樹。分析：分析：由后序遍歷特征，根結點必在后序序列尾部由后序遍歷特征，根結點必在后序序列尾部（即（即A A）；由中序遍歷特征，根結點必在其中間，而且其左部必全由中序遍歷特征，根結點必在其中間，而且其左部必全部是左子樹的子孫部是左子樹的子孫（即（即BDCEBDCE），其右部必全部是右子樹的，其右部必全部是右子樹的子孫子孫（即（即FHGFHG）；繼而，根據后序中的繼而，根據后序中的DECBDECB子樹可確定子樹可確

11、定B B為為A A的左孩子，根的左孩子，根據據HGFHGF子串可確定子串可確定F F為為A A的右孩子；以此類推。的右孩子；以此類推。19特別討論：特別討論：已知中序遍歷：已知中序遍歷：B D C E A F H G已知后序遍歷：已知后序遍歷：D E C B H G F A（B D C E）（ F H G）A （D C E）BFGHCD EABBACCD C E20知識拓展知識拓展利用遍歷建立二叉樹利用遍歷建立二叉樹用空格字符表示用空格字符表示無孩子無孩子或指針或指針為空為空如何把二叉樹存入電腦內？如何把二叉樹存入電腦內？怎樣利用遍歷建立一棵二叉樹？怎樣利用遍歷建立一棵二叉樹？例：將下面的二叉

12、樹以二叉鏈表形式存入計算機內。例：將下面的二叉樹以二叉鏈表形式存入計算機內。考慮考慮1 1：輸入結點時怎樣表示：輸入結點時怎樣表示“無孩子無孩子”？考慮考慮2 2：以何種遍歷方式來輸入和建樹？：以何種遍歷方式來輸入和建樹？將二叉樹按先序遍歷次序輸入：將二叉樹按先序遍歷次序輸入：A B CA B C D ED E G G F F (/n)(/n)以先序遍歷最為合適，以先序遍歷最為合適，讓每個結點都能及時讓每個結點都能及時被連接到位。被連接到位。字符串輸完后字符串輸完后應當再應當再加一特殊的結束符號加一特殊的結束符號(如如$)，因為，因為 無無法惟一表示結束。法惟一表示結束。21知識拓展知識拓展利

13、用遍歷建立二叉樹利用遍歷建立二叉樹建樹算法：建樹算法：Status CreateBiTree( BiTree &T ) /構造二叉樹構造二叉樹T Tscanf(“%c”,&ch);If (ch=) T=NULL; else if(!(T=( BiTNode*)malloc(sizeof(BiTNode)exit(overflow); T-data=ch; /生成根結點生成根結點 CreateBiTree(T-lchild); /構造左子樹構造左子樹 CreateBiTree(T-rchild); /構造右子樹構造右子樹 return OK; /CreateBiTree/Crea

14、teBiTree輸入序列：輸入序列： A B C D E G F 22二叉樹的遍歷二叉樹的遍歷定義、用途、方法定義、用途、方法中序遍歷：左、根、右中序遍歷：左、根、右先序遍歷：根、左、右先序遍歷：根、左、右后序遍歷：左、右、根后序遍歷：左、右、根利用先序遍歷建立二叉樹利用先序遍歷建立二叉樹表達式的計算順序表達式的計算順序遍歷算法：遞歸遍歷算法：遞歸遍歷規則遍歷規則問題引入問題引入遍歷的概述遍歷的概述遍歷的應用遍歷的應用特別討論特別討論如何利用遍歷構造一棵二叉樹？如何利用遍歷構造一棵二叉樹？遍歷效率：遍歷效率：O(n)23把二叉樹的遍歷算法改寫成程序進行上機調試。把二叉樹的遍歷算法改寫成程序進行上機調試。寫出利用先序遍歷創建一棵二叉樹的完整算法。寫出利用先序遍歷創建一棵二叉樹的完整算法。241 1、如右圖所示：寫出該二、如右圖所示：寫出該二叉樹的前序遍歷、中序叉樹的前序遍歷、中序遍歷和后序遍歷的序列。遍歷和