# 树的遍历

## 遍历的种类

### 深度优先遍历

#### 前序遍历(Pre-Order Traversal)

F, B, A, D, C, E, G, I, H.

```void pre_order_traversal(TreeNode *root) {
// Do Something with root
if (root->lchild != NULL)//若其中一側的子樹非空則會讀取其子樹
pre_order_traversal(root->lchild);
if (root->rchild != NULL)//另一側的子樹也做相同事
pre_order_traversal(root->rchild);
}
```

#### 中序遍历(In-Order Traversal)

A, B, C, D, E, F, G, H, I.

```void in_order_traversal(TreeNode *root) {
if (root->lchild != NULL)//若其中一側的子樹非空則會讀取其子樹
in_order_traversal(root->lchild);
// Do Something with root
if (root->rchild != NULL)//另一側的子樹也做相同事
in_order_traversal(root->rchild);
}
```

#### 后序遍历(Post-Order Traversal)

A, C, E, D, B, H, I, G, F.

```void post_order_traversal(TreeNode *root) {
if (root->lchild != NULL)//若其中一側的子樹非空則會讀取其子樹
post_order_traversal(root->lchild);
if (root->rchild != NULL)//另一側的子樹也做相同事
post_order_traversal(root->rchild);
// Do Something with root
}
```

### 广度优先遍历

F, B, G, A, D, I, C, E, H.
```void level(TreeNode *node)
{
Queue *queue = initQueue();
enQueue(queue, node);

while (!isQueueEmpty(queue))
{
TreeNode *curr = deQueue(queue);

// Do Something with curr

if (curr->lchild != NULL)
enQueue(queue, curr->lchild);
if (curr->rchild != NULL)
enQueue(queue, curr->rchild);
}
}
```

## 多叉树的遍历

### 深度优先遍历

```void travel(treenode* nd){
for(treenode* nex :　nd->childs){ // childs 存放指向其每個子結點的指標
travel(nex);
}
return;
}
```