魏霞　鄭勝

[摘 要]本研究通過把幾何學(xué)的相關(guān)知識遷移到《數(shù)據(jù)結(jié)構(gòu)》教學(xué)中，應(yīng)用幾何學(xué)的對稱特性和等腰三角形巧解二叉樹前序遍歷、中序遍歷和后序遍歷。把文字描述變?yōu)閳D形表述，思路清晰明了，教學(xué)效果顯著。

[關(guān)鍵詞]數(shù)據(jù)結(jié)構(gòu)；二叉樹；遍歷；幾何學(xué)；教學(xué)設(shè)計

[中圖分類號] O18 [文獻標(biāo)識碼] A [文章編號] 2095-3437（2016）03-0155-03

《數(shù)據(jù)結(jié)構(gòu)》是計算機專業(yè)一門重要的基礎(chǔ)課，樹形結(jié)構(gòu)是《數(shù)據(jù)結(jié)構(gòu)》課程中的一種非線形數(shù)據(jù)結(jié)構(gòu)。二叉樹是樹形結(jié)構(gòu)的重點，也是難點。遍歷是二叉樹中一個最重要的運算，是在二叉樹上進行其他運算的基礎(chǔ)。因此，掌握二叉樹遍歷相當(dāng)重要。[1]然而，二叉樹是一種非線性結(jié)構(gòu)，其遍歷不像線性鏈表那樣容易，無法通過簡單的循環(huán)實現(xiàn)。如何通過簡便可行的、通俗易懂的方法，讓學(xué)生理解和掌握二叉樹遍歷，值得廣大教師探索、研究。

一、二叉樹遍歷算法

二叉樹遍歷就是指按照一定的規(guī)則和順序，依次對樹中的所有結(jié)點做一次且僅被訪問一次，即按一定規(guī)律排列成一個線性隊列。[2]二叉樹是一種遞歸定義的結(jié)構(gòu)，包含根結(jié)點（N）、左子樹（L）、右子樹（R）三個部分。根據(jù)訪問根結(jié)點與左右子樹先后進行命名，二叉樹的遍歷有三種方式：前序遍歷（NLR）、中序遍歷（LNR）、后序遍歷（LRN）。對于這種傳統(tǒng)的方法，教師講解起來非常簡單，但是學(xué)生比較難以掌握與應(yīng)用。特別是在做一些遍歷運算的題目時，雖然學(xué)生上課時聽得明白，但是做起題目來卻無從下手，思緒混亂。

二、幾何學(xué)在二叉樹遍歷教學(xué)中的靈活應(yīng)用

我們每個人都比較熟悉幾何學(xué)，尤其是對稱性和等腰三角形。如何將我們熟知的幾何學(xué)應(yīng)用于二叉樹這一復(fù)雜的數(shù)據(jù)結(jié)構(gòu)教學(xué)中，簡化復(fù)雜的問題呢？本文將充分應(yīng)用牽移法思想，基于幾何學(xué)的淺顯概念及屬性，將幾何學(xué)與二叉樹遍歷教學(xué)聯(lián)系起來，讓二叉樹遍歷教學(xué)由繁變簡，讓學(xué)生能夠深刻掌握并靈活應(yīng)用所學(xué)知識。

（一）應(yīng)用對稱對比，掌握二叉樹遍歷算法定義

從上述的前序遍歷、中序遍歷和后序遍歷三種遍歷的遞歸算法對比分析，可以以一個對稱性圖形對三類遍歷類型進行教學(xué)。通過對比，可以讓三類遍歷類型簡單明了、通俗易懂。圖1是二叉樹遍歷類型圖。

圖1演示了二叉樹三種遍歷的過程。從整體來看，圖1是一個對稱的圖形；從中序遍歷本身來看，它也是一個單獨的對稱圖形。圖1演示圖應(yīng)用了軟件工程UML圖形設(shè)計元素、開始和結(jié)束的圖形標(biāo)記，可以讓學(xué)生通過圖形，了解二叉樹的三種遍歷的對比關(guān)系。

（1）開始：前序遍歷開始在根結(jié)點，中序遍歷開始在左子樹，后序遍歷開始也在左子樹；

（2）結(jié)束：前序遍歷結(jié)束在右子樹，中序遍歷結(jié)束也在右子樹，后序遍歷結(jié)束在根結(jié)點；

（3）根結(jié)點遍歷情況：前序遍歷的根結(jié)點最先遍歷，中序遍歷的根結(jié)點在中間遍歷，后序遍歷的根結(jié)點最后遍歷。

（二）應(yīng)用等腰三角形巧解二叉樹遍歷的運算

若要寫出圖2二叉樹的三種遍歷，很多學(xué)生無法理出一個清晰的思路。在此，本論文引入等腰三角形這個幾何圖形。

從圖2可見，A、B、C三個結(jié)點就好比一個三角形的三個點，其中，B、C為底點，因而A、B、C三個結(jié)點可以組成一個等腰三角形；B、D、E三個結(jié)點也好比一個三角形的三個點，其中，D、E為底點，因而B、D、E三個結(jié)點可以組成一個等腰三角形；以此類推，可以把二叉對所有結(jié)點進行組合，看做多個三角形的組合體。而對于像CF、FH和DG這種只有兩個結(jié)點的，我們可以假設(shè)其存在第三個點，比如，對于D、G兩個結(jié)點，可以假設(shè)其還存在一個左子樹結(jié)點，虛擬一個等腰三角形。在應(yīng)用等腰三角形進行遍歷書寫時，我們將按照從上到下，一層一層地查找三角形。這種不會出現(xiàn)混淆情況。以下是圖3所示的二叉樹的三種遍歷巧解過程。

1.前序遍歷巧解過程

如圖3所示，按照①②③④⑤五個等腰三角形的順序，逐一按前序遍歷的定義書寫二叉樹各結(jié)點，并結(jié)合圖1所示二叉樹遍歷的規(guī)則，從上到下、從左向右，按順序?qū)懗龆鏄浔闅v。其步驟如下：

第一步，寫第①個等腰三角形所在三個結(jié)點，這三個結(jié)點的前序遍歷是ABC。

第二步，寫第②個等腰三角形所在三個結(jié)點，這三個結(jié)點的前序遍歷是BDE。此時，結(jié)合第一步所得，綜合得到一個遍歷順序ABDEC。也可這么理解，即相當(dāng)于用遍歷BDE替換了遍歷ABC中的B。

第三步，寫第③個等腰三角形所在三個結(jié)點，這個三角形沒有左底點，即以C為父結(jié)點的二叉樹沒有左子結(jié)點，即為空，在此，我們以“□”表示。同樣，根據(jù)前序遍歷規(guī)則，這三個結(jié)點的前序遍歷是C□F，在第二步綜合得到的遍歷順序ABDEC的基礎(chǔ)上，通過替換，可以得到一個新的遍歷ABDEC□F。道理與第二步相同，即相當(dāng)于用遍歷C□F替換了遍歷ABDEC中的C。

第四步，寫第④個等腰三角形所在三個結(jié)點，這個三角形也沒有左底點，如第三步一樣，我們以“□”表示。同樣，根據(jù)前序遍歷規(guī)則，這三個結(jié)點的前序遍歷是D□G，在第三步綜合得到的遍歷順序ABDEC□F的基礎(chǔ)上，通過替換，可以得到一個新的遍歷ABD□GEC□F。道理與第二步相同，即相當(dāng)于用遍歷D□G替換了遍歷ABDEC□F中的D。

第五步，寫第⑤個等腰三角形所在三個結(jié)點，這個三角形沒有右底點，如第三步一樣，我們以“□”表示。同樣，根據(jù)前序遍歷規(guī)則，這三個結(jié)點的前序遍歷是FH□，在第四步綜合得到的遍歷順序ABD□GEC□F的基礎(chǔ)上，通過替換，可以得到一個新的遍歷ABD□GEC□FH□。道理與第二步相同，即相當(dāng)于用遍歷FH□替換了遍歷ABD□GEC□F中的F。

第六步，①②③④⑤五個等腰三角形都已按前序遍歷規(guī)則逐一遍歷到，最終得到了ABD□GEC□FH□遍歷。此時，我們把“□”去掉，最終得到了遍歷ABDGECFH，應(yīng)用傳統(tǒng)二叉樹遍歷解法進行檢驗，ABDGECFH就是圖2所示的二叉樹的前序遍歷。

2.中序遍歷巧解過程

如圖3所示，按照①②③④⑤五個等腰三角形的順序，逐一按中序遍歷的定義書寫二叉樹各結(jié)點，并結(jié)合圖1所示二叉樹遍歷的規(guī)則，從上到下、從左向右，按順序?qū)懗龆鏄浔闅v。其步驟如下：

第一步，寫第①個等腰三角形所在三個結(jié)點，這三個結(jié)點的中序遍歷是BAC。

第二步，寫第②個等腰三角形所在三個結(jié)點，這三個結(jié)點的中序遍歷是DBE。此時，結(jié)合第一步所得，綜合得到一個遍歷順序DBEAC。也可這么理解，即相當(dāng)于用遍歷DBE替換了遍歷BAC中的B。

第三步，寫第③個等腰三角形所在三個結(jié)點，這個三角形沒有左底點，即以C為父結(jié)點的二叉樹沒有左子結(jié)點，即為空，在此，我們以“□”表示。同樣，根據(jù)中序遍歷規(guī)則，這三個結(jié)點的中序遍歷是□CF，在第二步綜合得到的遍歷順序DBEAC的基礎(chǔ)上，通過替換，可以得到一個新的遍歷DBEA□CF。道理與第二步相同，即相當(dāng)于用遍歷□CF替換了遍歷DBEAC中的C。

第四步，寫第④個等腰三角形所在三個結(jié)點，這個三角形也沒有左底點，如第三步一樣，我們以“□”表示。同樣，根據(jù)中序遍歷規(guī)則，這三個結(jié)點的中序遍歷是□DG，在第三步綜合得到的遍歷順序DBEA□CF的基礎(chǔ)上，通過替換，可以得到一個新的遍歷□DGBEA□CF。道理與第二步相同，即相當(dāng)于用遍歷□DG替換了遍歷DBEA□CF中的D。

第五步，寫第⑤個等腰三角形所在三個結(jié)點，這個三角形沒有右底點，如第三步一樣，我們以“□”表示。同樣，根據(jù)中序遍歷規(guī)則，這三個結(jié)點的中序遍歷是HF□，在第四步綜合得到的遍歷順序□DGBEA□CF的基礎(chǔ)上，通過替換，可以得到一個新的遍歷□DGBEA□CHF□。道理與第二步相同，即相當(dāng)于用遍歷HF□替換了遍歷□DGBEA□CF中的F。

第六步，①②③④⑤五個等腰三角形都已按中序遍歷規(guī)則逐一遍歷到，最終得到了□DGBEA□CHF□遍歷。此時，我們把“□”去掉，最終得到了遍歷DGBEACHF，應(yīng)用傳統(tǒng)二叉樹遍歷解法進行檢驗，DGBEACHF就是圖2所示的二叉樹的中序遍歷。

3.后序遍歷巧解過程

如圖3所示，按照①②③④⑤五個等腰三角形的順序，逐一按后序遍歷的定義書寫二叉樹各結(jié)點，并結(jié)合圖1所示二叉樹遍歷的規(guī)則，從上到下、從左向右，按順序?qū)懗龆鏄浔闅v。其步驟如下：

第一步，寫第①個等腰三角形所在三個結(jié)點，這三個結(jié)點的后序遍歷是BCA。

第二步，寫第②個等腰三角形所在三個結(jié)點，這三個結(jié)點的后序遍歷是DEB。此時，結(jié)合第一步所得，綜合得到一個遍歷順序DEBCA。也可這么理解，即相當(dāng)于用遍歷DEB替換了遍歷BCA中的B。

第三步，寫第③個等腰三角形所在三個結(jié)點，這個三角形沒有左底點，即以C為父結(jié)點的二叉樹沒有左子結(jié)點，即為空，在此，我們以“□”表示。同樣，根據(jù)后序遍歷規(guī)則，這三個結(jié)點的后序遍歷是□FC，在第二步綜合得到的遍歷順序DEBCA的基礎(chǔ)上，通過替換，可以得到一個新的遍歷DEB□FCA。道理與第二步相同，即相當(dāng)于用遍歷□FC替換了遍歷DEBCA中的C。

第四步，寫第④個等腰三角形所在三個結(jié)點，這個三角形也沒有左底點，如第三步一樣，我們以“□”表示。同樣，根據(jù)后序遍歷規(guī)則，這三個結(jié)點的后序遍歷是□GD，在第三步綜合得到的遍歷順序DEB□FCA的基礎(chǔ)上，通過替換，可以得到一個新的遍歷□GDEB□FCA。道理與第二步相同，即相當(dāng)于用遍歷□GD替換了遍歷DEB□FCA中的D。

第五步，寫第⑤個等腰三角形所在三個結(jié)點，這個三角形沒有右底點，如第三步一樣，我們以“□”表示。同樣，根據(jù)后序遍歷規(guī)則，這三個結(jié)點的后序遍歷是H□F，在第四步綜合得到的遍歷順序□GDEB□FCA的基礎(chǔ)上，通過替換，可以得到一個新的遍歷□GDEB□H□FCA。道理與第二步相同，即相當(dāng)于用遍歷H□F替換了遍歷□GDEB□FCA中的F。

第六步，①②③④⑤五個等腰三角形都已按后序遍歷規(guī)則逐一遍歷到，最終得到了□GDEB□H□FCA遍歷。此時，我們把“□”去掉，最終得到了遍歷GDEBHFCA，應(yīng)用傳統(tǒng)二叉樹遍歷解法進行檢驗，GDEBHFCA就是圖2所示的二叉樹的后序遍歷。

三、結(jié)語

在計算機專業(yè)里，數(shù)據(jù)結(jié)構(gòu)是一門規(guī)律性很強的學(xué)科。我們可以通過建模，使數(shù)據(jù)結(jié)構(gòu)可視化，反映出其中的規(guī)律。我們的日常生活也蘊藏著很多規(guī)律，我們可以通過聯(lián)想遷移的方法，用生活中司空見慣的常識來解決復(fù)雜的問題。數(shù)據(jù)結(jié)構(gòu)在計算機教學(xué)中，雖然看起來非常復(fù)雜，但通過數(shù)據(jù)挖掘、數(shù)學(xué)建模，數(shù)據(jù)結(jié)構(gòu)能在很多日常的生活上得以反映，并能讓數(shù)據(jù)結(jié)構(gòu)教學(xué)化繁為簡，提高教學(xué)效率。本文從幾何學(xué)中最通俗的對稱性和等腰三角形進行挖掘，查找出了它們與二叉樹這一非線形數(shù)據(jù)結(jié)構(gòu)的潛在聯(lián)系，把復(fù)雜的問題簡單化。這樣在教學(xué)過程中，學(xué)生容易接受，教師講授也顯得輕松。

[ 參 考 文 獻 ]

[1] 喬良才，趙奇.二叉樹教學(xué)方法研究[J].攀枝花學(xué)院學(xué)報，2012（2）：124-126.

[2] 陳莉莉，劉琴琴.中序遍歷二叉樹的教學(xué)方法研究[J].電腦知識與技術(shù)，2011（9）：2100-2102.

[責(zé)任編輯：鐘偉芳]