這兩個(gè)術(shù)語(yǔ)區(qū)分了步行樹(shù)的兩種不同方式。

展示差異可能是最容易的?？紤]這棵樹(shù)：

    A

   / \

  B   C

 /   / \

D   E   F

一個(gè)深度優(yōu)先遍歷將訪問(wèn)節(jié)點(diǎn)順序

A, B, D, C, E, F

請(qǐng)注意，在繼續(xù)前進(jìn)之前，您要完全沿著一條腿向下移動(dòng)。

一個(gè)廣度優(yōu)先遍歷將訪問(wèn)節(jié)點(diǎn)順序

A, B, C, D, E, F

在這里，我們一直深入到每個(gè)級(jí)別，然后再進(jìn)行下去。

（請(qǐng)注意，遍歷順序有些歧義，我作弊要在樹(shù)的每個(gè)級(jí)別上保持“讀取”順序。無(wú)論哪種情況，我都可以在C之前或之后到達(dá)B，同樣，我可以到達(dá)E在F之前或之后。這可能會(huì)或可能不會(huì)重要，取決于您的應(yīng)用程序...）

兩種遍歷都可以通過(guò)偽代碼實(shí)現(xiàn)：

Store the root node in Container

While (there are nodes in Container)

   N = Get the "next" node from Container

   Store all the children of N in Container

   Do some work on N

兩種遍歷順序之間的差異在于對(duì)的選擇Container。

對(duì)于深度，請(qǐng)先使用堆棧。（遞歸實(shí)現(xiàn)使用調(diào)用堆棧...）

對(duì)于廣度優(yōu)先，請(qǐng)使用隊(duì)列。

遞歸實(shí)現(xiàn)看起來(lái)像

ProcessNode(Node)

   Work on the payload Node

   Foreach child of Node

      ProcessNode(child)

   /* Alternate time to work on the payload Node (see below) */

當(dāng)您到達(dá)沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)，遞歸結(jié)束，因此對(duì)于有限的非循環(huán)圖，可以保證遞歸結(jié)束。

在這一點(diǎn)上，我還是有點(diǎn)作弊。隨著一點(diǎn)點(diǎn)的小聰明，你也可以工作在這個(gè)秩序中的節(jié)點(diǎn)：

D, B, E, F, C, A

這是深度優(yōu)先的一種變體，在這種情況下，直到我向后走到樹(shù)上之前，我不會(huì)在每個(gè)節(jié)點(diǎn)上進(jìn)行工作。但是，我在去的途中參觀了較高的節(jié)點(diǎn)以找到他們的孩子。

在遞歸實(shí)現(xiàn)中，這種遍歷是很自然的（使用上面的“ Alternate time”行而不是第一條“ Work”行），并且如果您使用顯式堆棧也不會(huì)太難，但是我將其保留為練習(xí)。