# Binary Tree traversal

## **深度優先 (Depth-first)**

### 1.In-Order Traversal (LVR)

* 中序
* 步驟
  * 1.訪問左子樹
  * 2.訪問根節點
  * 3.訪問右子樹
* 特性
  * 如果以Inoder走訪[BST](https://jenhsuan.gitbooks.io/letcode/content/3data-structure/33binary-tree/333-binary-search-tree.html), 則可以得到一個有序數列
* Code

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LHBg6kuuMFxp-hrFuQA%2F-LHBgxXdlnvCoqciY9v0%2Fc3ebcb94-bd5b-412f-acb0-7c679ca90c38.png?alt=media\&token=2a590913-aad4-4b43-b47e-f8c0b6733318)

### 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);
        }
    }
}
```