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

展示差異可能是最容易的。考慮這棵樹：

    A

   / \

  B   C

 /   / \

D   E   F

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

A, B, D, C, E, F

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

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

A, B, C, D, E, F

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

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

兩種遍歷都可以通過偽代碼實(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

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

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

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

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

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á)沒有子節(jié)點(diǎn)的節(jié)點(diǎn)時，遞歸結(jié)束，因此對于有限的非循環(huán)圖，可以保證遞歸結(jié)束。

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

D, B, E, F, C, A

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

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