李曉

摘要：二叉樹及二叉樹的遍歷在全國計算機等級考試公共知識部分占很大比重，針對學(xué)生沒有數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)知識，學(xué)起來困難，做題困難，拿不到分等問題，通過對二叉樹遍歷問題進行詳細闡述，再結(jié)合一些考題進行分析，給學(xué)生找到一些解題的捷徑，樹立解決這類問題的信心，幫助學(xué)生順利通過等級考試。

關(guān)鍵詞：NCRE；二叉樹；二叉樹遍歷

中圖分類號：G64 文獻標(biāo)識碼：A 文章編號：1009-3044（2018）08-0106-03

1引言

NCRE：全國計算機等級考試（National Compeer Rank Ex-amination），是由教育部考試中心主辦，面向社會考試，考查應(yīng)試人員計算機應(yīng)用知識與技能的全國性計算機水平考試。該考試分為四個級別，即一級到四級，一級為初級，四級為最高級。通常，普通高等學(xué)校本科學(xué)生要求達到二級水平。二級考試要求參考者具有計算機基礎(chǔ)知識和基本運用能力，可以從事計算機程序編制，初級計算機教學(xué)培訓(xùn)以及企業(yè)中與信息化相關(guān)的工作。二級考試分為9個不同的類別，但所有類別都需要考生掌握一定的二級公共知識，這些公共知識主要包括計算機基礎(chǔ)知識，程序設(shè)計、軟件工程、數(shù)據(jù)結(jié)構(gòu)與算法、數(shù)據(jù)模型等。筆者所在的高校，學(xué)生普遍為文科類學(xué)生，這一部分公共知識的教學(xué)一直都非常困難，學(xué)生表示很難理解，考試中學(xué)生解題非常困難。其中數(shù)據(jù)結(jié)構(gòu)中的二叉樹及二叉樹的遍歷更是教學(xué)中的難點。

2二叉樹即二叉樹的遍歷

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，具有層次關(guān)系或分支關(guān)系，可以用來描述客觀世界的很多結(jié)構(gòu)，在人工智能和算法分析中都有廣泛的應(yīng)用。二叉樹是指每個結(jié)點最多有兩個子結(jié)點的結(jié)構(gòu)，這兩個結(jié)點通常被稱為左子樹和右子樹。二叉樹是一種獨立的數(shù)據(jù)結(jié)構(gòu)，不是樹的特殊形式。若將二叉樹的左右子樹顛倒，就成為了另一棵不同的二叉樹，即使二叉樹中的根結(jié)點只有一個子結(jié)點，也要說明該結(jié)點是左子樹還是右子樹，這是二叉樹與樹的最大區(qū)別。

在二叉樹的應(yīng)用中，往往要求在二叉樹中查找滿足指定條件的結(jié)點，或者對樹中全部結(jié)點逐一進行處理，如：輸出結(jié)點信息等，這就引入了二叉樹的遍歷問題、或者稱為二叉樹的周游問題。二叉樹的遍歷實際上就是把二叉樹的所有結(jié)點進行線性排列的過程，從而可以按這種線性排列訪問到二叉樹中的每一個結(jié)點，使得每一個結(jié)點均被訪問一次，且只能被訪問一次。遍歷對線性結(jié)構(gòu)非常容易解決，但對二叉樹這種非線性的結(jié)構(gòu)，需要找到一種規(guī)律，使二叉樹上的結(jié)點能排列在一個線性隊列上，從而便于遍歷或周游。

根據(jù)二叉樹的定義，二叉樹由根結(jié)點和左右兩課子樹構(gòu)成，如果用T代表根結(jié)點，L代表左子樹，R代表右子樹，那么二叉樹有TLR，LTR，LRT，TRL，RTL，RLT六種不同的遍歷方式。但最常用到的都是先左后右的順序，所以，將TLR（即根左右）表示的遍歷稱為先根遍歷，LTR（即左根右）表示的遍歷稱為中根遍歷，而LRT（即左右根）表示的遍歷稱為后根遍歷。另外，還有一種遍歷的方式是一層一層地訪問二叉樹中的結(jié)點，稱為層序遍歷。但層序遍歷一般不能簡單地使用L、T、R排列的方式來表示。

（1）先根遍歷

規(guī)則：先訪問根結(jié)點，再訪問左子樹，最后訪問右子樹。

在二叉樹中，如果除了先根遍歷的結(jié)點序列，還有中根遍歷的結(jié)點序列，由先根遍歷的第一個結(jié)點在中根遍歷節(jié)點序列中的位置，可以將中根遍歷的結(jié)點序列分為左右兩部分，由中根遍歷的方式可知，中根遍歷序列里根結(jié)點前面的結(jié)點必然是左子樹的結(jié)點，根結(jié)點后面的結(jié)點必然是右子樹中的結(jié)點。從而該二叉樹的根結(jié)點及其左右子樹中的結(jié)點就可以確定下來。將這一過程遞歸地進行下去，可逐步確定出二叉樹的樹形結(jié)構(gòu)。同理，如果知道二叉樹的中根遍歷序列和后根遍歷序列，同樣可以確定出二叉樹的樹形結(jié)構(gòu)。

全國計算機等級考試公共基礎(chǔ)知識部分，關(guān)于二叉樹的遍歷每年都會有比較經(jīng)典的考題出現(xiàn)，下面對等級考試中出現(xiàn)的關(guān)于二叉樹遍歷問題的幾道考題做一一分析。

3實例講解

（1）設(shè)二叉樹如下圖，則此二叉樹的后根遍歷序列為：（）

A、ABDEGCFH B、DBGEAFHC C、DGEBHFCA D、ABCDEFGH

解題方案一：根據(jù)后根序列規(guī)則，推算出此二叉樹的后根序列。

從根結(jié)點依次往下，A到B，B為左子樹的根結(jié)點，仍然不訪問，繼續(xù)再到下一層，到D。D為葉子結(jié)點，所以訪問D，再到E，E為根結(jié)點，不訪問，到下一層的左子樹G，訪問G，因為沒有右子樹，接著訪問E，再到上一層，訪問B，則左子樹部分的后根序列為DGEB。接著是此樹的右子樹部分，直接到葉子結(jié)點H，訪問H，接著訪問上一層的F，再訪問上一層的C，即右子樹部分的后根序列為HFC，最后訪問整棵樹的根結(jié)點A，因此，這棵二叉樹的后根序列為DGEBHFCA，答案為C。

解題方案二：此題可以有捷徑的解法。根據(jù)二叉樹后根序列的規(guī)則，需要先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點，因此二叉樹的后根序列的最后一個字母一定是根結(jié)點。分析答案，發(fā)現(xiàn)只有C答案是以A字母結(jié)尾的，因此，可以很快得到此題答案為C。

（2）設(shè)二叉樹的前根序列為ABDEGHCFIJ，中根序列為DB-GEHACIFJ，則按層次輸出（從上到下，同一層從左到右）的序列為（）。

A、ABCDEFGHIJ B、DGHEBUFCA C、JIHGFEDCBA D、GHIJDEFBCA

解題方案一：根據(jù)前根序列和中根序列，還原這棵二叉樹。

根據(jù)前根序列規(guī)則，第一個字母即為這棵二叉樹的根結(jié)點，則這棵二叉樹的根結(jié)點為A，因為根結(jié)點為A，在中根序列中，A字母以前的字母DBGEH為這棵二叉樹的左子樹部分，CIFJ為這棵二叉樹的右子樹。繼續(xù)分析左子樹部分，根據(jù)前根序列BDEGH，左子樹的根結(jié)點為B，根據(jù)中根序列DBGEH，B字母左邊的D為左子樹，GEH為右子樹部分。再根據(jù)前根EGH，判斷E為根結(jié)點，依次判斷G為左子樹，H為右子樹。再分析右子樹部分，前序CFIJ，C為根節(jié)點，下一層，前序FIJ，中序IFJ，即根結(jié)點F，左子樹I，右子樹J。至此，已經(jīng)還原了這棵二叉樹。見圖2。

根據(jù)還原以后的二叉樹，可以得到此題答案為：ABCDEF-GHIJ，則答案為A答案

解題方案二：此題也可不還原二叉樹，根據(jù)前根序列規(guī)則，二叉樹的前根序列第一個字母即為二叉樹的根結(jié)點，則該二叉樹的根結(jié)點為A，根據(jù)層序遍歷規(guī)則，層序的第一個字母必須是二叉樹的根結(jié)點，因此，此題可以在答案中選擇以A字母開頭的序列，分析答案，只有A答案符合這個條件，因此，選擇A答案。

（3）設(shè)二叉樹的前根序列為ABDEGHCFIJ，中根序列為DB-GEHACIH，則該二叉樹的后根序列為（）

A、DGHEBIJFCA B、JIHGFEDCBA C、GHIJDEFBCA D、ABCDEFGHIJ

解題方案一：根據(jù)前根序列和中根序列，還原這棵二叉樹。

根據(jù)前根序列開頭字母A，證明這棵二叉樹的根結(jié)點為A，再分析中根序列，A字母以前的DBGEH均為該二叉樹的左子樹部分，而CIFJ均為zJ.樹的右子樹部分。再看左子樹的前根序列，B字母開頭，則證明左子樹的根結(jié)點為B字母，再看中根序列，B字母的左邊只有D字母，證明左子樹為D，GEH為右子樹部分，根據(jù)中根序列為EGH，得出結(jié)論，E為根節(jié)點，G為左子樹，H為右子樹。分析右子樹部分，前序CFIJ，證明，C為根結(jié)點?？粗懈蛄校珻的左邊沒有字母，因此沒有左子樹，右子樹部分，前序為FIJ，則F為根結(jié)點，I為左子樹，J為右子樹，至此，這個二叉樹已經(jīng)確定。見圖3。

根據(jù)已經(jīng)還原出來的二叉樹和二叉樹后根遍歷規(guī)則，此二叉樹的后跟遍歷序列為：DGHEBIJFCA，所以A答案為正解。

解題方案二：本題也可不必還原二叉樹。從前根序列可以分析出此樹的根結(jié)點為A，再分析此樹中根序列，A字母以前的DBGEH為此樹的左子樹部分，CIFJ為此樹的右子樹部分。根據(jù)二叉樹后根序列的規(guī)則：先左子樹再右子樹最后根結(jié)點，那么必須把左子樹部分訪問完了以后，才會訪問右子樹。因此右子樹部分的CIFJ結(jié)點不可能出現(xiàn)在二叉樹后根序列的前五個字母，分析答案。B答案開頭即為JI，C答案第三第四個字母為U，故這兩個答案均為錯誤答案。再看D答案，此題已經(jīng)判斷出A結(jié)點為根結(jié)點，那么后根序列的最后一個字母應(yīng)為A，所以，D答案錯誤。得出此題的正確答案為A。

（4）某二叉樹的前根序列為ABCD，中根序列為DCBA，則后根序列為（）。

A、BADC

B、DCBA

C、CDAB

D、ABCD

解題方案一：此題仍然需要根據(jù)前根序列和中根序列還原ZJ.樹。根據(jù)前根序列規(guī)則，得出結(jié)論此二叉樹的根結(jié)點為A，再分析中根序列，發(fā)現(xiàn)，此二叉樹所有的結(jié)點都在左邊。再看左子樹的前序為BCD，則根結(jié)點為B，再依據(jù)中根序列，剩下兩個結(jié)點仍然還是在左邊。那么前序下一個根結(jié)點為C，再分析中序D還是在C的左邊，得出結(jié)論，此二叉樹是一棵非常特殊的二叉樹。見圖4。

根據(jù)還原出來的二叉樹，得到此二叉樹的后跟序列為：DC-BA。故答案為B答案。

解題方案二：此題仍然有比較捷徑的解法。根據(jù)前根序列，得出此二叉樹的根結(jié)點為A字母，那么根據(jù)二叉樹后根序列的規(guī)則，根結(jié)點必然是后根序列里最后一個字母。根據(jù)上述推論，在答案里找到以A字母結(jié)束的序列就是正確答案。由此得到此題的答案是B。

4結(jié)論

根據(jù)二叉樹的先根遍歷結(jié)點序列和中根遍歷結(jié)點序列可確定二叉樹的樹形結(jié)構(gòu)；同樣的，由二叉樹的后根遍歷結(jié)點序列和中根遍歷結(jié)點序列，也可確定二叉樹的樹形結(jié)構(gòu)。但是，如果同時知道二叉樹的先根遍歷和后根遍歷，則無法確定二叉樹的樹形結(jié)構(gòu)。

全國計算機等級考試中關(guān)于二叉樹遍歷的問題，一般都是圍繞知道先根，中根，求后根?；蛘咧乐懈蟾?，求先根這一考點。根據(jù)上述四道非常典型的考題分析，同學(xué)們可以依靠扎實的理論知識，認(rèn)真分析已知條件，再求解。同時，我們也發(fā)現(xiàn)，多數(shù)考題考慮到考生往往并不是計算機專業(yè)的學(xué)生，對數(shù)據(jù)結(jié)構(gòu)的知識掌握并不是特別系統(tǒng)和牢固，因此考題中也有一些捷徑的解法，即并不用完全還原二叉樹，就能得到最終答案，考生掌握這樣的分析方法，可以很快求得答案，通過等級考試。