基于幾何學(xué)的二叉樹遍歷教學(xué)設(shè)計(jì)研究

魏霞　鄭勝

[摘 要]本研究通過把幾何學(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è)計(jì)

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

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

一、二叉樹遍歷算法

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

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

我們每個(gè)人都比較熟悉幾何學(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)用對稱對比，掌握二叉樹遍歷算法定義

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

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

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

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

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

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

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

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

1.前序遍歷巧解過程

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

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

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

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

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

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

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

2.中序遍歷巧解過程

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

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

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

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

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

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

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

3.后序遍歷巧解過程

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

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

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

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

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

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

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

三、結(jié)語

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

[ 參 考 文 獻(xiàn) ]

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

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

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