树的遍历

遍历的种类

与那些基本上都有标准遍历方式（通常是按线性顺序）的线性数据结构（如链表、一维数组）所不同的是，树结构有多种不同的遍历方式。从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行操作（称为“访问”节点）、遍历左边子节点、遍历右边子节点。这三个步骤的先后顺序也是不同遍历方式的根本区别。
由于从给定的某个节点出发，有多个可以前往的下一个节点（树不是线性数据结构），所以在顺序计算（即非并行计算）的情况下，只能推迟对某些节点的访问——即以某种方式保存起来以便稍后再访问。常见的做法是采用栈（LIFO）或队列（FIFO）。由于树本身是一种自我引用（即递归定义）的数据结构，因此很自然也可以用递归方式，或者更准确地说，用corecursion，来实现延迟节点的保存。这时（采用递归的情况）这些节点被保存在call stack中。
遍历方式的命名，源于其访问节点的顺序。最简单的划分：是深度优先（先访问子节点，再访问父节点，最后是第二个子节点）？还是广度优先（先访问第一个子节点，再访问第二个子节点，最后访问父节点）？ 深度优先可进一步按照根节点相对于左右子节点的访问先后来划分。如果把左节点和右节点的位置固定不动，那么根节点放在左节点的左边，称为前序（pre-order）、根节点放在左节点和右节点的中间，称为中序（in-order）、根节点放在右节点的右边，称为后序（post-order）。对广度优先而言，遍历没有前序中序后序之分：给定一组已排序的子节点，其“广度优先”的遍历只有一种唯一的结果。

深度优先遍历

以下均是用递归方法。

前序遍历(Pre-Order Traversal)

指先访问根，然后访问子树的遍历方式
其C代码如下：
1 void pre_order_traversal(TreeNode *root) {2     // Do Something with root3     if (root->lchild != NULL)4         pre_order_traversal(root->lchild);5     if (root->rchild != NULL)6         pre_order_traversal(root->rchild);7 }

中序遍历(In-Order Traversal)

指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式
其C代码如下
1 void in_order_traversal(TreeNode *root) {2     if (root->lchild != NULL)3         in_order_traversal(root->lchild);4     // Do Something with root5     if (root->rchild != NULL)6         in_order_traversal(root->rchild);7 }

后序遍历(Post-Order Traversal)

指先访问子树，然后访问根的遍历方式
其C代码如下
1 void post_order_traversal(TreeNode *root) {2     if (root->lchild != NULL)3         post_order_traversal(root->lchild);4     if (root->rchild != NULL)5         post_order_traversal(root->rchild);6     // Do Something with root7 }

广度优先遍历

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。
 1 void Layer_Traver(tree *root) { 2     int head = 0, tail = 0; 3     tree *p[SIZE] = {NULL}; 4     tree *tmp; 5     if (root != NULL) { 6         p[head] = root; 7         tail++; 8         // Do Something with p[head] 9     } else10         return;11     while (head < tail) {12         tmp = p[head];13         // Do Something with p[head]14         if (tmp->left != NULL) { // left15             p[tail] = tmp->left;16             tail++;17         }18         if (tmp->right != NULL) { // right19             p[tail] = tmp->right;20             tail++;21         }22         head++;23     }24     return;25 }

深度优先遍历

先访问根结点，后选择一子结点访问并访问该节点的子结点，持续深入后再依序访问其他子树，可以轻易用递归或栈的方式实现。
1 void travel(treenode* nd){2     for(treenode* nex :　nd->childs){ // childs 存放指向其每個子結點的指標3         travel(nex);   
4     }5     return;6 }