本文将回答以下問題：
- 如何周遊一棵有根樹？
- 如何超越周遊？
如何周遊一棵有根樹？
其實要說一棵樹的周遊，大家其實都很清楚，無非先序、後序、層次三種（當然中序周遊隻存在于二叉樹中，我們後面介紹）。不過既然是函數式角度，免不了還要多bb幾句。
周遊，是以一定順序依次通路樹的每個結點。是以看到順序這個詞，其實大家就很清楚這個東西并不是函數式的産物，函數式的程式設計中中我們要盡力避免這種東西的使用。在本文最後我們将會分析這個問題。
預先的一些約定
首先，我們仍然沿用上一篇文章的那棵樹，也就是
榮國府男性族譜
(
存儲方式當然也與上一次一樣。
為了能讓scheme這個函數式語言類似其他過程式語言一樣依次做一些事情，scheme給出了這樣的文法：
(
為了一個類似過程化語言的實作，我還是寫了這個一個用來實作for循環的函數：
(
可以看到就是就是個将這個清單裡的每個元素執行一遍函數
，類似python的
for
或者C++的
for
先序周遊
衆所周知，先序周遊就是先通路根節點，然後依次遞歸通路孩子，例如C++中我們會這麼寫：
void
這裡假設的是
template
借助前面我們定義的for-list，用scheme寫的話就是：
(
其中(newline)是換行。
感興趣的同學可以試一下，将前面的樹的聲明與這裡的代碼複制進入scheme解釋器中，然後
(
看看效果。
理論上結果應該是這個順序：
賈代善->賈赦->賈琏->賈政->賈珠->賈寶玉->賈環
後序周遊
後序周遊同理，隻不過先遞歸子樹再通路根節點，那麼就是
(
不多解釋了。一樣用上面那棵樹測試的話，結果應該是
賈琏->賈赦->賈珠->賈寶玉->賈環->賈政->賈代善
層次周遊
學過圖論的同學應該知道，其實先序周遊和後序周遊本質上是深度優先搜尋（DFS），而層次周遊就是寬度優先搜尋（BFS）。
層次周遊會按照“輩分”來通路結點，也就是說根結點先來，然後是根節點第一層孩子（模仿數學的話應該叫一階孩子？），接着是根節點的孩子的孩子（二階孩子），以此類推。
在過程化語言中，我們通常采用隊列來完成這個任務。例如C++中：
template
（當然這裡的Queue得用std::deque<*Tree<T>>一類的方法來實作，否則存儲量挺驚人的——不過這個不是本文讨論的重點啦）
首先我們補充定義一個函數
，将兩個清單合并成一個清單
(
舉個栗子，一目了然：
cons-list使用說明
然後，我們隻需要處理一個to-do-list即可（也就是我們前面的Queue）。代碼如下：
(
這裡做個備注，也就是新的to-do-list，我這裡是
(
一行生成的——其實很簡單，(cdr to-do-list)就是pop以後的queue，而(cdr (car to-do-list))是pop出來的那個結點的孩子清單，正好cons-list一下就行。
以前面榮國府的栗子，結果應該是：
賈代善->賈赦->賈政->賈琏->賈珠->賈寶玉->賈環
如何超越周遊？
如果隻寫到這裡，我們隻是用函數式語言中一個最不好的東西（scheme的串行begin）來實作過程語言的任務——用不合适的語言，以一個醜陋的形式去做。
但是回到函數式的起點，我們要函數式的作用，其實是為了避免思考操作的先後順序，用函數來完成全部任務。而周遊這個事情本身，就是要給出一個操作順序，自然是先後沖突的。
另一個角度，其實周遊很多時候是出于一種無奈——樹是分叉的，但是（馮·諾伊曼）計算機的體系結構同時隻能做一件事情，于是我們不得不考慮給他們一個計算的先後順序。比如說一棵數字樹，我要算所有結點的數值之和，因為體系結構隻能将兩個數字加起來，是以我們必須初始化一個sum = 0，然後按照一定順序把樹的每個結點x都來個sum += x。
函數式，我們試圖不考慮體系結構。正如當年mit-scheme誕生的時代——1975年，那時離第一枚多核處理器的誕生還有30年曆史，離現在并行計算最常用的裝置——GPU的誕生也還有24年，但是當年的先驅者就已經在scheme中引入了
這樣的并行語句，并且用随機數這些方法去模拟并發計算時順序的不确定性。暢想未來，也許我們終有一天能借助某些技術（生物？量子？）去實作同時任意多線程的并發，而不是今天受制于核心數的并發，那個時候，樹的周遊又會是怎樣呢？
我想，也許，那個時候就不再有周遊的問題了，我們也許可以同時對全部子樹分别開一個線程，這樣我們便無所謂順序了。這也許正是函數式的高瞻遠矚之處。
以前面的栗子，如果我們需要把一棵樹的全部結點加起來（而不是display這樣的過程），我們可以完完全全用純粹的函數式的手法去描述（對先序的程式稍加修改即可）：
(
如果此時，我們能把+并行計算，比如說(+ (f a) (f b))，能開兩個線程同時計算(f a)和(f b)，然後再求和，那麼其實就實作了我們想要的并發模式——再想想，此時這個“通路順序”還是先序嗎？