今天要來完成第四種遍歷法：Level Order Traversal

比起前三者來說，他顯得更加直觀，因為他是按照 level 大小來輸出資料，換句話說，就是由上而下、由左而右進行輸出。

定義類別

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

定義類別方法

在 level order traversal 中，我們需要一個資料結構作為暫存的角色。

這個資料結構一定是「堆疊」或「佇列」，但是我們該使用哪一個呢？
你可能已經發現我們的資料是由左而右輸出，下一層的資料也是由左而右輸出，因此我們可以說這是一串有序的資料，而使用佇列。

為什麼需要暫存的角色？
因為我們必須將一層都輸出完後，才可以輸出下一層，但是我們必須藉由上一層的節點來觸及下一層的節點，因此需要先儲存。

void BST::levelorder() {
    if (this -> root == NULL) return ;
    std::queue <BSTNode *> q;
    q.push(this -> root);
    while (q.size()) {
        int size = q.size();
        for (int i=0; i<size; i++) {
            std::cout << q.front() -> data << " -> ";
            if (q.front() -> left) q.push(q.front() -> left);
            if (q.front() -> right) q.push(q.front() -> right);
            q.pop();
        }
    }
    std::cout << "end";
}

四種遍歷法大致介紹完畢，我們也對數有更進一步的認識了！
下一篇，我們要介紹 BST::Max(), BST::Min(), BST::Search()