Linked List 的 Traversal 其實很簡單，基本上不是由前向後走，就是由後向前走。

但是，樹要怎麼被遍歷呢？
每一個節點都可以分岔出數個岔路，每一條岔路又會再分岔下去。
因此樹狀結構的遍歷包含數種方式，今天要介紹「前序」、「中序」、「後序」遍歷法！

Preorder Traversal

這個遍歷法用遞迴來實作比較容易，大概敘述一下這個遍歷法：
我們不斷將樹分成數個子樹，但是在處理子樹之前，我們都先輸出根節點資料。

def 前序遍歷(樹根)：
    輸出根節點資料
    前序遍歷(左子樹根)
    前序遍歷(右子樹根)

用 Python 實作：

def preOrder(root):
    if (root is None):
        return None
    print(root.data, end = " ")
    if (root.left != None):
        preOrder(root.left)
    if (root.right != None):
        preOrder(root.right)

Inorder Traversal

這個遍歷法用遞迴來實作比較容易，大概敘述一下這個遍歷法：
我們不斷將樹分成數個子樹，當處理完左子樹時，我們輸出根節點資料，再繼續處理右子樹

def 中序遍歷(樹根)：
    中序遍歷(左子樹根)
    輸出根節點資料
    中序遍歷(右子樹根)

用 Python 實作：

def inOrder(root):
    if (root is None):
        return None
    if (root.left != None):
        inOrder(root.left)
    print(root.data, end = " ")
    if (root.right != None):
        inOrder(root.right)

Postorder Traversal

這個遍歷法用遞迴來實作比較容易，大概敘述一下這個遍歷法：
我們不斷將樹分成數個子樹，當處理完所有子樹時，我們才輸出根節點資料。

def 後序遍歷(樹根)：
    後序遍歷(左子樹根)
    後序遍歷(右子樹根)
    輸出根節點資料

用 Python 實作：

def postOrder(root):
    if (root is None):
        return None
    if (root.left != None):
        postOrder(root.left)
    if (root.right != None):
        postOrder(root.right)
    print(root.data, end = " ")

還有一種遍歷法叫做 level order traversal ，我們下一篇來介紹