填空法講授二叉樹遍歷教學(xué)探討

文章編號：1672-5913(2008)12-0075-02

摘要：本文從教學(xué)實踐的角度出發(fā)，闡述了學(xué)生對“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)中二叉樹遍歷這一知識點不易理解的問題，并提出一種新的方法——填空法解決這一問題。通過對填空法的基本原理和講授方式的探討，使學(xué)生產(chǎn)生興趣從而提高該知識點的課堂教學(xué)效果。

關(guān)鍵詞：填空法；二叉樹；遍歷

中圖分類號：G642

文獻(xiàn)標(biāo)識碼：A

數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)極其重要的專業(yè)基礎(chǔ)課。所有數(shù)據(jù)結(jié)構(gòu)中，樹是非常重要的一種，尤其是二叉樹，學(xué)習(xí)者是應(yīng)該牢固掌握的。在學(xué)習(xí)了較為簡單的線性表之后，學(xué)生開始接觸了較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)——樹。概念樹是容易接受的，可一旦講到對樹的建立和運算等問題時，很多學(xué)生或多或少地會感到一些困惑，尤其是二叉樹的遍歷，看似簡單的遞歸算法，可要理解其遍歷過程，未必能夠一目了然。

1提出問題

對于二叉樹遍歷過程的講解，傳統(tǒng)的講法以遞歸算法為藍(lán)本，加上圖示的輔助，幫助學(xué)生理解該算法怎樣實現(xiàn)在樹的遍歷中如何調(diào)用對子樹的遍歷，如何輸出結(jié)點以及如何返回，返回到哪一個結(jié)點。由于學(xué)生接觸的遞歸算法不多(最多在C語言、數(shù)據(jù)結(jié)構(gòu)的“?！敝杏兴鶎W(xué)習(xí)，而且C語言大多在大一第一學(xué)期學(xué)習(xí)，關(guān)于算法和遞歸等知識的理解不夠)，所以理解不是很好，教起來也不輕松。多次講解此處知識后我們發(fā)現(xiàn)，如果以二叉樹的圖示為藍(lán)本講解，使學(xué)生反向理解二叉樹的遍歷算法效果要好很多。這樣，不僅使學(xué)生容易理解二叉樹的遍歷過程，而且對遞歸這一常用的算法設(shè)計方法也有更深刻的理解，下面將總結(jié)后的經(jīng)驗與大家共勉。

2“填空法”遍歷二叉樹

對二叉樹中的任何一個結(jié)點來說，它都有自己的左、右子樹(當(dāng)然有些可視為空)。那么，對于三種遍歷方法：前序、中序、后序，我們無非是將該結(jié)點作為根，然后按照一定的順序去遍歷該結(jié)點及其左、右子樹，同時還能確定的是：無論哪種遍歷，左子樹必定在右子樹之前遍歷。因此，我們可以將整個樹的遍歷過程看作根在A(左子樹遍歷序列)B(右子樹遍歷序列)C這一過程中可能出現(xiàn)的A、B、C三個位置之一，進(jìn)而，可將二叉樹中任何一個結(jié)點的遍歷視作上述過程。由此我們可以發(fā)現(xiàn)，無論是前序、中序、后序哪種遍歷方式，都可以將遍歷過程中的任何一步作為當(dāng)前結(jié)點與其左、右子樹遍歷順序的填空過程，只要確定了或前、或中、或后的遍歷順序，即確定了二叉樹中任一結(jié)點在上述過程中的A或B或C的位置，進(jìn)而將遍歷的結(jié)點依次填寫在對整個二叉樹遍歷序列的相應(yīng)位置上。此時我們發(fā)現(xiàn)，整個遍歷過程的重點已經(jīng)不在左子樹、根、右子樹的遍歷順序上了，因為對每個結(jié)點來說，一旦遍歷順序定則三者位置定，重點轉(zhuǎn)移到遍歷到任一結(jié)點時，該結(jié)點在整個遍歷序列中的具體位置上了，所以，由于位置的確定，先遍歷左子樹或是右子樹已經(jīng)不重要了。下面以一個具體的實例來說明填空法的詳細(xì)講解過程。

例求下圖所示二叉樹的中序遍歷序列首先，為數(shù)中的所有結(jié)點標(biāo)號(可用學(xué)生最易接受的層次遍歷順序依次為每層結(jié)點標(biāo)號)，接下來便開始遍歷，按照中序遍歷的順序，任一結(jié)點在以其為根的子樹中的位置是(左子樹)該結(jié)點(右子樹)，因此，對于結(jié)點A，我們可以用(1左)A(1右)這樣的公式來表示，接下來，無論我們先遍歷A的左子樹或右子樹，則A及其左子樹在遍歷的序列中的位置是不變的，A的左子樹是以B為根結(jié)點的，因此該子樹的遍歷序列可用(2左)B(2右)來表示，由于B右為空，B左只有一個結(jié)點D，因此，(2左)B(2右)所表達(dá)的遍歷序列即DB，也即在(1左)A(1右)中的(1左)；再看(1右)是以C為根結(jié)點的子樹，我們同樣可以用(3左)C(3右)來表示該子樹的中序遍歷，以后的遍歷過程依次類推，那么在講課過程中，我們實際上就可以按照以下的填空步驟來講解該二叉樹的遍歷過程。

(1左)A(1右)

(2左)B(2右)A(3左)C(3右)

DB A(5左)E(5右)C(6左)F(6右)

DBAEGCHF

由此可得該二叉樹的中序遍歷序列為DBAEGCHF，那么同時我們也可以看出為什么在填空法中要為樹中結(jié)點標(biāo)唯一的號，這是因為在二叉樹中，結(jié)點的名字是很可能不唯一的，假如在填空的過程中用A左、A右來表示其左右子樹的話很容易與其他重名結(jié)點的遍歷混淆，在結(jié)點較多的情況下，發(fā)生混淆的可能性就更大。同樣的道理，若是前序遍歷二叉樹，那么可以用類似A(1左)(1右)這樣的公式表示，后序遍歷則是(1左)(1右)A來表示，填空的方法基本相同。

3總結(jié)

使用“填空法”講授二叉樹遍歷的優(yōu)是顯而易見的，直觀的講述和演示使學(xué)生能夠很快掌握二叉樹遍歷的過程。此外，在遇到較為復(fù)雜的二叉樹需要寫出遍歷序列時，填空法更顯示出它的優(yōu)點，比如對表達(dá)式的線性化要求寫出表達(dá)式的波蘭式，填空法的使用比直接用傳統(tǒng)法遍歷的出錯率大大降低。當(dāng)樹中有多個重名結(jié)點時，填空法利用了結(jié)點標(biāo)號的方法避免了遍歷過程中結(jié)點混淆的問題，遍歷迅速且不易出錯。

但是，這種方法不適用于簡單二叉樹，二叉樹結(jié)構(gòu)簡單時，對結(jié)點的標(biāo)號和填空倒是顯得有些笨拙了。

由于經(jīng)驗有限，此方法只是在作者講授的計算機(jī)專業(yè)“數(shù)據(jù)結(jié)構(gòu)”課程和自動化專業(yè)的“軟件技術(shù)基礎(chǔ)”課程中使用，課堂上學(xué)生對這種方法表達(dá)出的濃厚興趣是顯而易見的。更重要的是，通過這種填空法的遍歷結(jié)果再去講解遍歷的遞歸算法使學(xué)生更容易理解算法中有關(guān)遞歸調(diào)用和返回的過程?？荚嚱Y(jié)果顯示，在這兩門課程中該知識點的滿分得分率達(dá)到90%以上，可以說這種填空法比較地成功的運用于教學(xué)中。

參考文獻(xiàn)

[1] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)［M］. 北京:清華大學(xué)出版社，2007.

[2] 徐士良. 計算機(jī)軟件技術(shù)基礎(chǔ)［M］. 北京:清華大學(xué)出版社，2002.

A Discussion on Fill in Blanks Method to Teach Binary Tree Traversal

Yang Chun-Lei， Wu Qing-Tao， Zhang Hong-Yi

(Electronic Information Engineering College OF HAUST HeNan LuoYang 471003)

Abstract：From the angle of teaching practice， this article states a question that students can’t easily catch the binary tree traversal on Data Structure course， and brings forward a new method of filling in blanks to resolve it. The goal of discussion on the fundamental and teaching mode to it is giving birth to students’ interest and improving the teaching effect.

Keywods：Fill in blanks method， Binary tree， Traversal