李曉

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

關鍵詞：NCRE；二叉樹；二叉樹遍歷

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

1引言

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

2二叉樹即二叉樹的遍歷

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

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

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

（1）先根遍歷

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

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

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

3實例講解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A、BADC

B、DCBA

C、CDAB

D、ABCD

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

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

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

4結論

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

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