樹(shù)的遍歷是樹(shù)的一種重要的運(yùn)算。所謂遍歷是指對(duì)樹(shù)中所有結(jié)點(diǎn)的系統(tǒng)的訪問(wèn)，即依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。樹(shù)的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和后序遍歷。以這3種方式遍歷一棵樹(shù)時(shí)，若按訪問(wèn)結(jié)點(diǎn)的先后次序?qū)⒔Y(jié)點(diǎn)排列起來(lái)，就可分別得到樹(shù)中所有結(jié)點(diǎn)的前序列表，中序列表和后序列表。相應(yīng)的結(jié)點(diǎn)次序分別稱為結(jié)點(diǎn)的前序、中序和后序。

樹(shù)的這3種遍歷方式可遞歸地定義如下：

如果T是一棵空樹(shù)，那么對(duì)T進(jìn)行前序遍歷、中序遍歷和后序遍歷都是空操作，得到的列表為空表。

如果T是一棵單結(jié)點(diǎn)樹(shù)，那么對(duì)T進(jìn)行前序遍歷、中序遍歷和后序遍歷都只訪問(wèn)這個(gè)結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)本身就是要得到的相應(yīng)列表。

否則，設(shè)T如圖6所示，它以n為樹(shù)根，樹(shù)根的子樹(shù)從左到右依次為T(mén)1,T2,..,Tk，那么有：

對(duì)T進(jìn)行前序遍歷是先訪問(wèn)樹(shù)根n,然后依次前序遍歷T1,T2,..,Tk。

對(duì)T進(jìn)行中序遍歷是先中序遍歷T1，然后訪問(wèn)樹(shù)根n，接著依次對(duì)T2,T2,..,Tk進(jìn)行中序遍歷。

對(duì)T進(jìn)行后序遍歷是先依次對(duì)T1,T2,..,Tk進(jìn)行后序遍歷，最后訪問(wèn)樹(shù)根n。

圖6 樹(shù)T

前序遍歷和中序遍歷可形式地依次描述如下

三種遍歷可以形式地描述如下，其中用到了樹(shù)的ADT操作：

Procedure Preorder_Traversal(v:NodeType); {前序遍歷算法}

begin

Visite(v); {訪問(wèn)節(jié)點(diǎn)v}

i:=Leftmost_Child(v);

while i<>∧ do

begin

Preorder_Traversal(i);{從左到右依次訪問(wèn)v的每一個(gè)兒子節(jié)點(diǎn)i}

i:=Right_Sibling(i);

end;

end;

Procedure Inorder_Traversal(v:NodeType); {中序遍歷算法}

begin

if Leftmost_Child(v)=∧ {判斷v是否是葉節(jié)點(diǎn)}

then Visite(v)

else

begin

Inorder_Traversal(Leftmost_Child(v)); {中序遍歷v的左邊第一個(gè)兒子節(jié)點(diǎn)}

Visite(v); {訪問(wèn)節(jié)點(diǎn)v}

i:=Right_Sibling(Leftmost_Child(v)); {i=v的左邊第二個(gè)兒子}

while i<>∧ do

begin

Inorder_Traversal(i);

{從左邊第二個(gè)開(kāi)始到最右邊一個(gè)為止依次訪問(wèn)v的每一個(gè)兒子節(jié)點(diǎn)i}

i:=Right_Sibling(i);

end;

end;

end;

Procedure Postorder_Traversal(v:NodeType); {后序遍歷算法}

begin

i:=Leftmost_Child(v);

while i<>∧ do

begin

Preorder_Traversal(i);{從左到右依次訪問(wèn)v的每一個(gè)兒子節(jié)點(diǎn)i}

i:=Right_Sibling(i);

end;

Visite(v); {訪問(wèn)節(jié)點(diǎn)v}

end;

為了將一棵樹(shù)中所有結(jié)點(diǎn)按某種次序列表，只須對(duì)樹(shù)根調(diào)用相應(yīng)過(guò)程。例如對(duì)圖7中的樹(shù)進(jìn)行前序遍歷、中序遍歷和后序遍歷將分別得到前序列表：A B E F I J C D G H；中序列表：E B I F J A C G D H；后序列表：E I J F B C G H D A。

圖7 一棵樹(shù)

下面介紹一種方法可以產(chǎn)生上述3種遍歷方式的結(jié)點(diǎn)列表。設(shè)想我們從樹(shù)根出發(fā)，依逆時(shí)針?lè)较蜓貥?shù)的外緣繞行(例如圍繞圖7中的樹(shù)繞行的路線如圖8所示)。繞行途中可能多次經(jīng)過(guò)同一結(jié)點(diǎn)。如果我們按第一次經(jīng)過(guò)的時(shí)間次序?qū)⒏鱾€(gè)結(jié)點(diǎn)列表，就可以得到前序列表；如果按最后一次經(jīng)過(guò)的時(shí)間次序列表，也就是在即將離開(kāi)某一結(jié)點(diǎn)走向其父親時(shí)將該結(jié)點(diǎn)列出，就得到后序列表。為了產(chǎn)生中序列表，要將葉結(jié)點(diǎn)與內(nèi)部結(jié)點(diǎn)加以區(qū)別。葉結(jié)點(diǎn)在第一次經(jīng)過(guò)時(shí)列出，而內(nèi)部結(jié)點(diǎn)在第二次經(jīng)過(guò)時(shí)列出。

圖8 樹(shù)的遍歷

在上述3種不同次序的列表方式中，各樹(shù)葉之間的相對(duì)次序是相同的，它們都按樹(shù)葉之間從左到右的次序排列。3種列表方式的差別僅在于內(nèi)部結(jié)點(diǎn)之間以及內(nèi)部結(jié)點(diǎn)與樹(shù)葉之間的次序有所不同。

一棵樹(shù)進(jìn)行前序列表或后序列表有助于查詢結(jié)點(diǎn)間的祖先子孫關(guān)系。假設(shè)結(jié)點(diǎn)v在后序列表中的序號(hào)(整數(shù))為postorder(v)，我們稱這個(gè)整數(shù)為結(jié)點(diǎn)v的后序編號(hào)。例如在圖7中，結(jié)點(diǎn)E，I和J的后序編號(hào)分別為1，2和3。

結(jié)點(diǎn)的后序編號(hào)具有這樣的特點(diǎn)：設(shè)結(jié)點(diǎn)v的真子孫個(gè)數(shù)為desc(v)，那么在以v為根的子樹(shù)中的所有結(jié)點(diǎn)的后序編號(hào)恰好落在postorder(v)-desc(v)與postorder(v)之間。因此為了檢驗(yàn)結(jié)點(diǎn)x是否為結(jié)點(diǎn)y的子孫，我們只要判斷它們的后序編號(hào)是否滿足：

postorder(y)-desc(y)≤postorder(x)≤postorder(y)

前序編號(hào)也具有類似的性質(zhì)。

數(shù)據(jù)結(jié)構(gòu)知識(shí)——樹(shù)的三種不同遍歷算法解析