想輸出鏈結串列其實很容易，只要找到當前節點的 next 即可找到下一個節點。有了節點，我們就可以輸出節點中的資料。這個是之前介紹過的 LinkedList::print()。

那麼我們要怎麼輸出一棵樹的資料呢？
每一個節點至多有兩個子節點，哪一個節點才是我們想要的下一個節點？
有了下一個節點，我們的順序又是如何呢？

這些問題的解答大致可以用三種模式來概括：preorder, inorder, postorder

定義類別

class BST {
private:
    BSTNode *root;
private:
    BST();
    void insert(int); // Non Recursive
    void insert(BSTNode *, int); // Recursive
    void preorder(BSTNode *root);
    void inorder(BSTNode *root);
    void postorder(BSTNode *root);
};

前序遍歷 (Preorder Traversal)

這個遍歷演算法，我們以「遞迴」來定義：

function preorder(根節點) {
    如果根節點為空指標：結束函式
    輸出根節點的內容
    如果根節點的左子節點存在：preorder(左子節點)
    如果根節點的右子節點存在：preorder(右子節點)
}

如果不清楚，可以自己畫一顆二元搜尋樹，跟著上述的演算法模擬，就可以大致了解他的過程！

現在我們就來以程式來實作這個演算法：

void BST::preorder(BSTNode *root) {
    if (root == NULL) return ;
    std:cout << root -> data << " ";
    if (root -> left) preorder(root -> left);
    if (root -> right) preorder(root -> right);
}

中序遍歷 (inorder Traversal)

這個遍歷演算法，我們以「遞迴」來定義：

function preorder(根節點) {
    如果根節點為空指標：結束函式
    如果根節點的左子節點存在：inorder(左子節點)
    輸出根節點的內容
    如果根節點的右子節點存在：inorder(右子節點)
}

現在我們就來以程式來實作這個演算法：

void BST::inorder(BSTNode *root) {
    if (root == NULL) return ;
    if (root -> left) inorder(root -> left);
    std:cout << root -> data << " ";
    if (root -> right) inorder(root -> right);
}

後序遍歷 (postorder Traversal)

這個遍歷演算法，我們以「遞迴」來定義：

function preorder(根節點) {
    如果根節點為空指標：結束函式
    如果根節點的左子節點存在：postorder(左子節點)
    如果根節點的右子節點存在：postorder(右子節點)
    輸出根節點的內容
}

現在我們就來以程式來實作這個演算法：

void BST::postorder(BSTNode *root) {
    if (root == NULL) return ;
    if (root -> left) postorder(root -> left);
    if (root -> right) postorder(root -> right);
    std:cout << root -> data << " ";
}

這些遍歷演算法適用於所有二元樹（不侷限於二元搜尋樹）！

想想看：
一棵二元搜尋樹搭配中序遍歷（inorder）而得的結果有什麼特色？
數字會由小到大被輸出，且為嚴格遞增。

遍歷演算法只能使用遞迴來實作嗎？
當然不是，下一篇我們就來以迭代法實作！