Binary Tree traversal

深度優先 (Depth-first)

1.In-Order Traversal (LVR)

• 中序

• 步驟

  • 1.訪問左子樹

  • 2.訪問根節點

  • 3.訪問右子樹

• 特性

  • 如果以Inoder走訪BST, 則可以得到一個有序數列

• Code

void BinaryTree::Inorder(TreeNode *current){
    if (current) {
        // if current != NULL
        Inorder(current->leftchild);// L
        std::cout << current->str << " "; // V
        Inorder(current->rightchild); // R
    }
}

2.Post-Order Traversal (LRV)

• 後序

• 步驟

  • 1.訪問左子樹

  • 2.訪問右子樹

  • 3.訪問根節點

• 特性

  • 可以利用Post order確定是否為AVL tree

• Code

void BinaryTree::Postorder(TreeNode *current){
    if (current) { // if current != NULL
        Postorder(current->leftchild); // L
        Postorder(current->rightchild); // R
        std::cout << current->str << " "; // V
    }
}

3.Pre-Order Traversal(VLR)

廣度優先 (Breadth-first)

1.Level-Order Traversal

• BST

• 步驟

  • 1. 從queue加入tree的第一個node

  • 2.從queue清除本層(不管左右子樹)的所有成員

  • 3.從queue加入下一層(不管左右子樹)的所有成員

void BinaryTree::Levelorder(){
    std::queue<TreeNode*> q;
    q.push(this->root);
    while (!q.empty()){
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            //從queue清除本層(不管左右子樹)的所有成員
            TreeNode *node = q.front();
            q.pop();
            //從queue加入下一層(不管左右子樹)的所有成員
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
}