樹和森林的周遊

一、樹的周遊

樹的結構是一個根加上森林，而森林又是樹的集合，由此我們可以引出樹的兩種周遊方式（這兩種周遊方式本身也是一種遞歸定義）。

1、先根（先序）周遊：即先通路樹的根結點，然後依次先根周遊根的每棵子樹

2、後根（後序）周遊：即先依次後根周遊根的每棵子樹，然後通路根結點

3、另外還有一種層序周遊，這種周遊就是自上向下，自左向右按層次進行周遊即可

根據上面的兩種周遊定義可得上圖樹的周遊結果如下：

先根周遊：ABEFCDGHIJK

後根周遊：EFBCIJKHGDA

層次周遊：ABCDEFGHIJK

二、森林的周遊

森林由三部分構成：森林中第一個樹的根結點+森林中第一顆樹的根結點的子樹森林+森林中除去第一棵樹而由其它樹構成的森林。按照森林和樹互相遞歸的定義，我們可以推出森林的兩種周遊方（這兩種周遊方法也是遞歸定義）。

1、先序周遊森林，通路規則如下：

第一、先通路森林中第一棵樹的根結點

第二、然後，先序周遊第一棵樹中根結點的子樹森林（相當于二叉樹的左子樹）

第三、然後，先序周遊除去第一棵樹之後剩餘的樹構成的森林（相當于二叉樹的右子樹）

2、中序周遊森林

第一、中序周遊第一棵樹中根結點的子樹森林（相當于二叉樹的左子樹）

第二、然後，通路森林中第一棵樹的根結點

第三、然後，中序序周遊除去第一棵樹之後剩餘的樹構成的森林（相當于二叉樹的右子樹）

将上面的樹的根結點去掉得到的森林，按照森林的兩種周遊方法得到的結果如下：

先序周遊：BEFCDGHIJK

中序周遊：EFBCIJKHGD

三、總結

對照上面樹和圖的周遊我們可以得到樹、森林、二叉樹周遊的對應關系

樹的周遊	對應	森林的周遊	對應	二叉樹的周遊
先根周遊	->	先序周遊	->	先序周遊
後根周遊	->	中序周遊	->	中序周遊