填空法講授二叉樹遍歷教學探討

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

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

關鍵詞：填空法；二叉樹；遍歷

中圖分類號：G642

文獻標識碼：A

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

1提出問題

對于二叉樹遍歷過程的講解，傳統的講法以遞歸算法為藍本，加上圖示的輔助，幫助學生理解該算法怎樣實現在樹的遍歷中如何調用對子樹的遍歷，如何輸出結點以及如何返回，返回到哪一個結點。由于學生接觸的遞歸算法不多(最多在C語言、數據結構的“棧”中有所學習，而且C語言大多在大一第一學期學習，關于算法和遞歸等知識的理解不夠)，所以理解不是很好，教起來也不輕松。多次講解此處知識后我們發現，如果以二叉樹的圖示為藍本講解，使學生反向理解二叉樹的遍歷算法效果要好很多。這樣，不僅使學生容易理解二叉樹的遍歷過程，而且對遞歸這一常用的算法設計方法也有更深刻的理解，下面將總結后的經驗與大家共勉。

2“填空法”遍歷二叉樹

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

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

(1左)A(1右)

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

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

DBAEGCHF

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

3總結

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

但是，這種方法不適用于簡單二叉樹，二叉樹結構簡單時，對結點的標號和填空倒是顯得有些笨拙了。

由于經驗有限，此方法只是在作者講授的計算機專業“數據結構”課程和自動化專業的“軟件技術基礎”課程中使用，課堂上學生對這種方法表達出的濃厚興趣是顯而易見的。更重要的是，通過這種填空法的遍歷結果再去講解遍歷的遞歸算法使學生更容易理解算法中有關遞歸調用和返回的過程。考試結果顯示，在這兩門課程中該知識點的滿分得分率達到90%以上，可以說這種填空法比較地成功的運用于教學中。

參考文獻

[1] 嚴蔚敏，吳偉民. 數據結構(C語言版)［M］. 北京:清華大學出版社，2007.

[2] 徐士良. 計算機軟件技術基礎［M］. 北京:清華大學出版社，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