數(shù)據(jù)結(jié)構(gòu)-二叉樹(shù)的遍歷

運(yùn)城職業(yè)技術(shù)大學(xué)教案(本科）20—20學(xué)年第學(xué)期課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)課程性質(zhì)學(xué)時(shí)授課班級(jí)授課教師教案首頁(yè)教學(xué)單元名稱(chēng)第六章樹(shù)和二叉樹(shù)第三節(jié)遍歷二叉樹(shù)教學(xué)內(nèi)容1.二叉樹(shù)遍歷的概念及方法2.二叉樹(shù)的遍歷算法課時(shí)2授課地點(diǎn)教室授課所需教具、工具、軟件、耗材等多媒體、黑板、粉筆教學(xué)目標(biāo)知識(shí)目標(biāo)能力目標(biāo)素質(zhì)目標(biāo)面對(duì)一些工程問(wèn)題，能夠聯(lián)想到二叉樹(shù)的方法，將二叉樹(shù)的遍歷思想融會(huì)貫通，開(kāi)拓思維，注重創(chuàng)新教學(xué)重難點(diǎn)重點(diǎn)難點(diǎn)教學(xué)方法與手段講授、演示、討論、案例分析、實(shí)驗(yàn)課程資源備注教案一、導(dǎo)入新課（5分鐘）作為有智慧的人類(lèi)，我們學(xué)過(guò)“先乘除后加減，有括號(hào)先算括號(hào)”的算術(shù)順口溜。但是計(jì)算機(jī)只會(huì)一條一條的執(zhí)行預(yù)設(shè)的命令，并不會(huì)隨機(jī)應(yīng)變二、講授新課（75分鐘）授課環(huán)節(jié)1二叉樹(shù)遍歷的概念及方法（40分鐘）1.遍歷概念（5分鐘）（1）遍歷定義：是指沿著某條搜索路線，依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。注意：不可有結(jié)點(diǎn)被重復(fù)訪問(wèn)，也不可有結(jié)點(diǎn)沒(méi)有被訪問(wèn)。舉反例講解。（2）遍歷用途：遍歷是樹(shù)結(jié)構(gòu)插入、修改、刪除、查找和排序計(jì)算的前提，是二叉樹(shù)一切計(jì)算的基礎(chǔ)和核心。訪問(wèn)結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn)題。2.二叉樹(shù)遍歷規(guī)則（5分鐘）二叉樹(shù)由根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)構(gòu)成，分別定義為：D、L、R。排列組合后可以有六種遍歷方案：LDR、RDL、DRL、DLR、LRD、RLD。但根據(jù)“先左后右”的遍歷原則，二叉樹(shù)只有3種遍歷方案：（1）DLR先序遍歷，根結(jié)點(diǎn)最先被訪問(wèn)。（2）LDR中序遍歷，根結(jié)點(diǎn)在左右子樹(shù)中間被訪問(wèn)。（3）LRD后序遍歷，根結(jié)點(diǎn)最后被訪問(wèn)。注意：“先、中、后”的含義是以根結(jié)點(diǎn)為參照物，標(biāo)志著訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在訪問(wèn)子樹(shù)之前還是之后。3.二叉樹(shù)的遍歷方法（30分鐘）基于二叉樹(shù)的遞歸定義．可得下述遍歷二叉樹(shù)的遞歸算法定義：先序遍歷二叉樹(shù)的操作定義為：若二叉樹(shù)為空，則空操作；否則(1)訪問(wèn)根結(jié)點(diǎn)；(2)先序遍歷左子樹(shù)；(3)先序遍歷右子樹(shù)中序遍歷二叉樹(shù)的操作定義為：若二叉樹(shù)為空，則空操作；否則(1)中序遍歷左子樹(shù)；(2)訪問(wèn)根結(jié)點(diǎn)；(3)中序遍歷右子樹(shù)。后序遍歷二叉樹(shù)的操作定義為：若二叉樹(shù)為空，則空操作；否則(1)后序遍歷左子樹(shù)；(2)后序遍歷右子樹(shù)；(3)訪問(wèn)根結(jié)點(diǎn)。例題講解：將先導(dǎo)問(wèn)題中的算術(shù)表達(dá)式以二叉樹(shù)的形式存儲(chǔ)，使用二叉樹(shù)的遍歷方法解決計(jì)算問(wèn)題。//-*6+3952根據(jù)上述二叉樹(shù)的遍歷操作定義，其先序序列為：/*3+25-96，中序序列為：3*2+5/9-6，后序序列為：325+*96-/。然后，計(jì)算機(jī)程序可以使用棧為工具計(jì)算后序序列。當(dāng)訪問(wèn)到數(shù)字時(shí)，把數(shù)字壓入棧中，而當(dāng)訪問(wèn)到運(yùn)算符時(shí)，從棧中取出兩個(gè)元素進(jìn)行運(yùn)算，然后再壓回棧中，直到訪問(wèn)完所有元素。最后在棧中的元素就是最終計(jì)算結(jié)果。授課環(huán)節(jié)2二叉樹(shù)的遍歷算法（35分鐘）1.二叉樹(shù)的遞歸算法（10分鐘）根據(jù)上一環(huán)節(jié)的二叉樹(shù)遍歷遞歸操作定義，我們給出先序遍歷的遞歸算法：voidDLR(BiTreeT){if(T!=NULL){visit(T);//訪問(wèn)根節(jié)點(diǎn)DLR(T->lchild);//遞歸遍歷左子樹(shù)DLR(T->rchild);//遞歸遍歷右子樹(shù)}}可以看到，在遞歸算法中，輸入一棵樹(shù)，首先判斷是否非空，然后才開(kāi)始遍歷過(guò)程。根據(jù)先序遍歷的規(guī)則，首先訪問(wèn)根結(jié)點(diǎn)，visit()操作根據(jù)具體的應(yīng)用要求實(shí)現(xiàn)。然后遍歷左子樹(shù)，進(jìn)入一個(gè)新的遍歷二叉樹(shù)的程序中，遍歷完成后繼續(xù)程序。最后遍歷右子樹(shù)。討論：中序遍歷和后序遍歷的遞歸算法？（5分鐘）2.二叉樹(shù)的非遞歸算法（15分鐘）可以借助棧S，將二叉樹(shù)的遞歸遍歷算法轉(zhuǎn)換為非遞歸算法，以中序遍歷為例給出中序遍歷的非遞歸算法。先掃描(并非訪問(wèn))根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并將它們一一進(jìn)棧。然后出棧一個(gè)結(jié)點(diǎn)P*(顯然結(jié)點(diǎn)P*沒(méi)有左孩子結(jié)點(diǎn)或者左孩子結(jié)點(diǎn)均已訪問(wèn)過(guò))，則訪問(wèn)它。然后掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，將其進(jìn)棧，再掃描該右孩子結(jié)點(diǎn)的所有左結(jié)點(diǎn)并一一進(jìn)棧，如此繼續(xù)，直到?？諡橹埂Ｖ行虮闅v的非遞歸算法如下：voidInOrder2(BiTreeT){InitStack(S);BiTreep=T;//初始化棧；p是指針while(p||!empty(S)){//棧非空或p非空時(shí)循環(huán)if(p){push(S,p);//遇到非空樹(shù)先向左走p=p->lchild;}else{pop(S,p);visit(p);//退棧；訪問(wèn)根結(jié)點(diǎn)p=p->rchild;//再向右走}}}討論：先序遍歷和后序遍歷的非遞歸算法？（5分鐘）三、課堂小結(jié)（5分鐘）本次課我們了解了二叉樹(shù)遍歷的基本概念和方法，掌握了二叉樹(shù)的三種遍歷方法，并使用算法實(shí)現(xiàn)了遍歷過(guò)程，包括遞歸算法和非遞