树的遍历

遍历的种类

深度优先遍历

前序遍历

1
2
 3 4

5

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

中序遍历

4
2
 1 3

5

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

后序遍历

5
3
 1 2

4

```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
}
```

广度优先遍历

1
2
 4 5

3

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