李曉

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

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

中圖分類(lèi)號(hào)：G64 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）08-0106-03

1引言

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

2二叉樹(shù)即二叉樹(shù)的遍歷

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

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

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

（1）先根遍歷

規(guī)則：先訪問(wèn)根結(jié)點(diǎn)，再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)。

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

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

3實(shí)例講解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A、BADC

B、DCBA

C、CDAB

D、ABCD

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

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

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

4結(jié)論

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

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