搜索法講解二叉樹遍歷的教學(xué)探討

搜索法講解二叉樹遍歷的教學(xué)探討摘要:本文從教學(xué)實(shí)踐的角度出發(fā),闡述了學(xué)生對(duì)“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)中二叉樹遍歷這一知識(shí)點(diǎn)不易理解的問(wèn)題,并提出了一種新的方法——搜索法來(lái)解決這一問(wèn)題。通過(guò)對(duì)搜索法的分析、解決過(guò)程及案例的演示,使學(xué)生產(chǎn)生興趣從而提高該知識(shí)點(diǎn)的課堂教學(xué)效果。關(guān)鍵字:數(shù)據(jù)結(jié)構(gòu)二叉樹二叉樹遍歷搜索法數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)尤其是軟件技術(shù)專業(yè)中極其重要的一門專業(yè)基礎(chǔ)課。所有數(shù)據(jù)結(jié)構(gòu)中,樹是非常重要的一種,尤其是二叉樹,學(xué)習(xí)者是應(yīng)該牢固掌握的。在學(xué)習(xí)了較為簡(jiǎn)單的線性表之后,學(xué)生開始接觸了較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)——樹。通過(guò)形象的比喻,概念樹是容易接受的,但是講到對(duì)樹的建立和運(yùn)算等問(wèn)題時(shí),很多學(xué)生或多或少地會(huì)感到一些困惑,尤其是二叉樹的遍歷,看似簡(jiǎn)單的遞歸算法,可要理解其遍歷過(guò)程,未必能夠一目了然。1、 問(wèn)題的提出對(duì)于二叉樹遍歷過(guò)程的講解,傳統(tǒng)的講法以遞歸算法為藍(lán)本,加上圖示的輔助,幫助學(xué)生理解該算法怎樣實(shí)現(xiàn)在樹的遍歷中如何調(diào)用對(duì)子樹的遍歷,如何輸出結(jié)點(diǎn)以及如何返回,返回到哪一個(gè)結(jié)點(diǎn)。由于學(xué)生接觸的遞歸算法不多,所以理解不是很好,有時(shí)候感覺像是在走迷宮,教起來(lái)自然也就不輕松。多次講解此處知識(shí)后我們發(fā)現(xiàn),如果以二叉樹的搜索圖示為藍(lán)本講解,使學(xué)生反向理解二叉樹的遍歷算法效果要好很多。這樣,不僅使學(xué)生容易理解二叉樹的遍歷過(guò)程,而且對(duì)遞歸這一常用的算法設(shè)計(jì)方法也有更深刻的理解。下面將總結(jié)后的經(jīng)驗(yàn)與大家共勉。2、 問(wèn)題的分析——搜索法二叉樹的遍歷是針對(duì)任意二叉樹,任意二叉樹存在結(jié)點(diǎn)度為0的結(jié)點(diǎn),也可能存在結(jié)點(diǎn)度為的1的結(jié)點(diǎn),還可能存在結(jié)點(diǎn)度為2的結(jié)點(diǎn)。用搜索法對(duì)二叉樹進(jìn)行遍歷時(shí),無(wú)論二叉樹的結(jié)點(diǎn)度是為0,為1還是為2,首先將結(jié)點(diǎn)度不為2的結(jié)點(diǎn),用空結(jié)點(diǎn)將其補(bǔ)充為結(jié)點(diǎn)度為2的結(jié)點(diǎn)。其次從根結(jié)點(diǎn)左側(cè)出發(fā),搜索每一個(gè)結(jié)點(diǎn),每個(gè)非空結(jié)點(diǎn)都將訪問(wèn)三次。第一次訪問(wèn)標(biāo)為①,第二次訪問(wèn)標(biāo)為②,第三次訪問(wèn)標(biāo)為③。如果是先序遍歷(先根遍歷),則沿著搜索線將標(biāo)記為①的結(jié)點(diǎn)依次輸出;如果是中序遍歷(中根遍歷),則沿著搜索線將標(biāo)記為②的結(jié)點(diǎn)依次輸出;如果后序遍歷(后根遍歷),則沿著搜索線將標(biāo)記為③的結(jié)點(diǎn)依次輸出。這樣就將原來(lái)的根左右、左根右和左右根變?yōu)棰?、②、③的輸?當(dāng)然標(biāo)記也可以用其他數(shù)字或字母,只要標(biāo)記統(tǒng)一就可以)。其他標(biāo)記①、②、③也也正好是前序遍歷、中序遍歷和后序遍歷遞歸算法中的輸出語(yǔ)句所在的位置。3、問(wèn)題的解決——搜索法根據(jù)對(duì)搜索法遍歷方法的分析,可制定出搜索法遍歷二叉樹的三個(gè)步驟。(1)完善二叉樹?？v觀整個(gè)二叉樹,將其結(jié)點(diǎn)度不為2的結(jié)點(diǎn),用空結(jié)點(diǎn)將其補(bǔ)充為結(jié)點(diǎn)度為2的結(jié)點(diǎn)。(2)畫搜索線。從根結(jié)點(diǎn)的左側(cè)出發(fā),沿著二叉樹圖畫出搜索線。第一次到達(dá)某非空結(jié)點(diǎn)標(biāo)示為①,第二次到達(dá)某非空結(jié)點(diǎn)標(biāo)示為②,第三次到達(dá)某非空結(jié)點(diǎn)標(biāo)示為③。最后回到根結(jié)點(diǎn)的右側(cè)。(3)寫出要求的遍歷序列。如果是先序遍歷,就沿著搜索線依次將標(biāo)記為①的結(jié)點(diǎn)寫出。如果是中序遍歷,就沿著搜索線依次將標(biāo)記為②的結(jié)點(diǎn)寫出。如果是后序遍歷,就沿著依次將標(biāo)記為③的結(jié)點(diǎn)寫出。4、綜合案例給出二叉樹(如圖1)的先序遍歷序列、中序遍歷序列和后序遍歷序列圖1原始二叉樹圖2完善后的二叉樹(1)完善二叉樹,如圖2所示:(2)畫搜索線,如圖3所示:圖3帶搜索線的二叉樹根據(jù)搜索線圖如圖3所示,前序遍歷是沿著箭頭方向依次寫出結(jié)點(diǎn)處標(biāo)示為①的結(jié)點(diǎn),故前序遍歷序列為ABDCEF;中序遍歷是沿著箭頭方向依次寫出結(jié)點(diǎn)處標(biāo)示為②的結(jié)點(diǎn),故中序遍歷序列為DBAECF;后序遍歷是沿著箭頭方向依次寫出結(jié)點(diǎn)處標(biāo)示為③的結(jié)點(diǎn),故后序遍歷序列為DBEFCA。5 結(jié)語(yǔ)使用“搜索法”講解二叉樹遍歷的優(yōu)勢(shì)顯而易見的,直觀的講述和演示使學(xué)生能夠很快掌握二叉樹遍歷的過(guò)程,輕松地寫出二叉樹的遍歷序列。此外,在遇到較為復(fù)雜的二叉樹需要寫出遍歷序列時(shí),“搜索法”更顯示出它的優(yōu)點(diǎn)。但“搜索法”也有一個(gè)弱點(diǎn),那就是操作繁瑣。由于經(jīng)驗(yàn)有限,此方法只是在作者講授的軟件技術(shù)“數(shù)據(jù)結(jié)構(gòu)”課程和自考“數(shù)據(jù)結(jié)構(gòu)”課程中使用,課堂上學(xué)生對(duì)這種方法表達(dá)出的濃厚興趣。學(xué)生的學(xué)習(xí)效果也是非常好?？荚嚱Y(jié)果顯示,通過(guò)“搜索法”遍歷二叉樹的教學(xué),同學(xué)們完全掌握了這個(gè)知識(shí)點(diǎn),可以說(shuō)“搜索法”比較地成功的運(yùn)用于教學(xué)中。參考文獻(xiàn):[1]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).北京:清華大學(xué)出版社,2007.8.[2]黃劉生數(shù)據(jù)結(jié)構(gòu).北京:經(jīng)濟(jì)科學(xué)出版社,2004.2.[3]譚浩強(qiáng)C語(yǔ)言程序設(shè)計(jì)(