二叉樹周遊算法之一：前序周遊

遞歸實作前序周遊

二叉樹的前序周遊是指從根節點出發，按照先根節點，再左子樹，後右子樹的方法周遊二叉樹中的所有節點，使得每個節點都被通路一次。

當調用周遊算法的時候前序周遊的具體過程如下：

首先通路根節點，如果根節點不為空，執行輸出語句，列印根節點的值。

如果左子樹不為空，則通路根節點的左孩子，并輸出根節點做孩子的值

繼續通路根節點的左孩子的左孩子，如果不為空則繼續輸出該左孩子的值；

如果這時左孩子為空，說明該節點是葉子節點，則按照先左孩子後右孩子的通路方式通路其左右孩子，如果不為空就列印輸出

左子樹通路完畢之後，繼續通路根節點的右子樹，如果根節點的右孩子不為空，則輸出該右孩子

繼續通路根節點右孩子的左孩子，如果不為空，則輸出

接着通路根節點右孩子的右孩子，如果不為空，則輸出

可以發現這個過程是不斷循環進行的，可以使用遞歸算法實作，具體代碼如下：

為了測試使用，我構造一棵二叉樹，先添加如下測試代碼：

構造出來的二叉樹是這樣的：

是以根據前面的前序周遊算法周遊的結果應該是：8，6，5，15，24，7，10，9，30，11，28。

非遞歸方式實作前序周遊

遞歸代碼很簡潔，但是也有一些不是很好了解，能不能直接使用循環的方法加以解決呢？采用非遞歸的思路其實與上面是一緻的，不過在周遊的過程中需要使用一些額外的空間儲存周遊的中間結果，下面是使用非遞歸的方式實作前序周遊的代碼：