二叉樹遍歷(稿)

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) C C語言語言 AFEDCBG 知識與技能知識與技能過程與方法過程與方法實(shí)現(xiàn)價值實(shí)現(xiàn)價值 二叉樹遍歷二叉樹遍歷的應(yīng)用。的應(yīng)用。重重點(diǎn)點(diǎn)難難點(diǎn)點(diǎn)新課引入新課引入- -遍歷的應(yīng)用遍歷的應(yīng)用1 課程講解課程講解- - 基礎(chǔ)知識基礎(chǔ)知識2教學(xué)提升教學(xué)提升- -課程總結(jié)課程總結(jié)4實(shí)踐內(nèi)容實(shí)踐內(nèi)容- -練習(xí)討論練習(xí)討論3鞏固鞏固拓展拓展- -課后作業(yè)課后作業(yè)5 3 (2+5) /(9-6)=7先算哪個呢？將算術(shù)表達(dá)式畫將算術(shù)表達(dá)式畫成一棵二叉樹成一棵二叉樹/+36259它的中序遍歷序列為：它的中序遍歷序列為：3 * 2 + 5 / 9 6它的后序遍歷序列為：它的后序遍歷序列為：2 5 +

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

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

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

5、:討論后序遍歷思想及算法？ L R DL R DL R DADCL R DB后序遍歷序列：后序遍歷序列： D B C A三種遍歷算法總結(jié)三種遍歷算法總結(jié)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);typedef struct nodein

6、t 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); 三種遍歷算法分析三種遍歷算法分析1. 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將print語句抹去，語句抹去，從遞歸的角度看，這三種算法是完全相同的，

7、或者說這三種從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時機(jī)不同。訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個結(jié)點(diǎn)經(jīng)過上，每個結(jié)點(diǎn)經(jīng)過3次次。第第1次次經(jīng)過時訪問，是經(jīng)過時訪問，是先序先序遍歷遍歷第第2次次經(jīng)過時訪問，是經(jīng)過時訪問，是中序中序遍歷遍歷第第3次次經(jīng)過時訪問，是經(jīng)過時訪問，是后序后序遍歷遍歷2. 2. 二叉樹遍歷的時間效率和空間效率二叉樹遍歷的時間效率和空間效率時間效率時間效率: : /每個結(jié)點(diǎn)只訪問一次每個結(jié)點(diǎn)只訪問一次空間效率空間效率: : /棧占用的最大輔助空

8、間棧占用的最大輔助空間精確值：樹深為精確值：樹深為k k的遞歸遍歷需要的遞歸遍歷需要k+1k+1個輔助單元個輔助單元AFEDCBG實(shí)踐內(nèi)實(shí)踐內(nèi)容-練習(xí)討論練習(xí)討論例例1：先序遍歷的結(jié)果是：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：后序遍歷的結(jié)果是： A B CD E口訣：口訣：D DLRLR先序遍歷，即先序遍歷，即先根再左再右先根再左再右L LD DR R中序遍歷，即中序遍歷，即先左再根再右先左再根再右LRLRD D后序遍歷，即后序遍歷，即先左再右再根先左再右再根實(shí)踐內(nèi)實(shí)踐內(nèi)容-練習(xí)討論練習(xí)討論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 A知識應(yīng)識應(yīng)用-表達(dá)達(dá)式計(jì)計(jì)算+*A*/EDCB先序遍歷結(jié)果先序遍歷結(jié)果+ * * / A B C D E前綴表示法前綴表示法中序遍歷結(jié)果中序遍歷結(jié)果A / B * C * D + E中綴表示法中綴表示法后序遍歷結(jié)果后序遍歷結(jié)果A B / C * D * E +后綴表示法后綴表示法層次遍歷結(jié)果層次遍歷結(jié)果+ * E * D / C A B例例3 3：用二叉樹表示算術(shù)表達(dá)式用二叉樹表示算術(shù)表達(dá)式特別討論特別討論例：例：已知一棵二叉樹的已知一棵二叉樹的中序序列中序序列和和后序序列后序

10、序列分別是分別是BDCEAFHGBDCEAFHG 和和 DECBHGFADECBHGFA，請畫出這棵二叉樹。請畫出這棵二叉樹。分析：分析：由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（即（即A A）；由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹的子孫部是左子樹的子孫（即（即BDCEBDCE），其右部必全部是右子樹的其右部必全部是右子樹的子孫子孫（即（即FHGFHG）；繼而，根據(jù)后序中的繼而，根據(jù)后序中的DECBDECB子樹可確定子樹可確定B B為為A A的左孩子，根的左孩子，根據(jù)據(jù)HGFHGF子串可確

11、定子串可確定F F為為A A的右孩子；以此類推。的右孩子；以此類推。特別討論：特別討論：已知中序遍歷：已知中序遍歷：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 E知識拓展知識拓展利用遍歷建立二叉樹利用遍歷建立二叉樹用用空格字符表示空格字符表示無孩子無孩子或指針或指針為空為空如何把二叉樹存入電腦內(nèi)？如何把二叉樹存入電腦內(nèi)？怎樣利用遍歷建立一棵二叉樹？怎樣利用遍歷建立一棵二叉樹？例：將下面的二叉樹以二叉鏈表形式存入計(jì)算機(jī)內(nèi)。例：將下面的二叉樹以二叉鏈表形式存入計(jì)算機(jī)內(nèi)

12、?？紤]考慮1 1：輸入結(jié)點(diǎn)時怎樣表示：輸入結(jié)點(diǎn)時怎樣表示“無孩子無孩子”？考慮考慮2 2：以何種遍歷方式來輸入和建樹？：以何種遍歷方式來輸入和建樹？將二叉樹按先序遍歷次序輸入：將二叉樹按先序遍歷次序輸入：A B CA B C D ED E G G F F (/n)(/n)以先序遍歷最為合適，以先序遍歷最為合適，讓每個結(jié)點(diǎn)都能及時讓每個結(jié)點(diǎn)都能及時被連接到位。被連接到位。字符串輸完后字符串輸完后應(yīng)當(dāng)再應(yīng)當(dāng)再加一特殊的結(jié)束符號加一特殊的結(jié)束符號(如如$)，因?yàn)?，因?yàn)?無無法惟一表示結(jié)束。法惟一表示結(jié)束。知識拓展知識拓展利用遍歷建立二叉樹利用遍歷建立二叉樹建樹算法：建樹算法：Status Creat

13、eBiTree( BiTree &T ) /構(gòu)造二叉樹構(gòu)造二叉樹T Tscanf(“%c”,&ch);If (ch=) T=NULL; else if(!(T=( BiTNode*)malloc(sizeof(BiTNode)exit(overflow); T-data=ch; /生成根結(jié)點(diǎn)生成根結(jié)點(diǎn) CreateBiTree(T-lchild); /構(gòu)造左子樹構(gòu)造左子樹 CreateBiTree(T-rchild); /構(gòu)造右子樹構(gòu)造右子樹 return OK; /CreateBiTreeCreateBiTree輸入序列：輸入序列： A B C D E G F 二叉樹的遍歷二

14、叉樹的遍歷定義、用途、方法定義、用途、方法中序遍歷：左、根、右中序遍歷：左、根、右先序遍歷：根、左、右先序遍歷：根、左、右后序遍歷：左、右、根后序遍歷：左、右、根利用先序遍歷建立二叉樹利用先序遍歷建立二叉樹表達(dá)式的計(jì)算順序表達(dá)式的計(jì)算順序遍歷算法：遞歸遍歷算法：遞歸遍歷規(guī)則遍歷規(guī)則問題引入問題引入遍歷的概述遍歷的概述遍歷的應(yīng)用遍歷的應(yīng)用特別討論特別討論如何利用遍歷構(gòu)造一棵二叉樹？如何利用遍歷構(gòu)造一棵二叉樹？遍歷效率：遍歷效率：O(n)把二叉樹的遍歷算法改寫成程序進(jìn)行上機(jī)調(diào)試。把二叉樹的遍歷算法改寫成程序進(jìn)行上機(jī)調(diào)試。寫出利用先序遍歷創(chuàng)建一棵二叉樹的完整算法。寫出利用先序遍歷創(chuàng)建一棵二叉樹的完整算法。1 1、如右圖所示：寫出該二、如右圖所示：寫出該二叉樹的前序遍歷、中序叉樹的前序遍歷、中序遍歷和后序遍歷的序列。遍歷和后