二叉搜索樹的遍历方法

以下摘抄自Wiki

深度优先遍历 //常见的的三种遍历方法均为DFS

以下均是用递归方法。
先序遍历(Pre-Order Traversal)

指先访问根，然后访问子树的遍历方式，其C代码如下：

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)

指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式，其C代码如下

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)

指先访问子树，然后访问根的遍历方式，其C代码如下

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
}

广度优先遍历

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。

void Layer_Traver(tree* root)
{
    int head = 0,tail = 0;
    tree* p[SIZE] = {NULL};
    tree* tmp;
    if(root != NULL)
    {
        p[head] = root;
        tail++;
        //Do Something with p[head]
    }
    else
    {
        return;
    }
    while(head < tail)    //数组实现的队列 翻书
    {
        tmp = p[head];
        //Do Something with p[head]
        if(tmp->left != NULL)//left
        {
            p[tail] = tmp->left;
            tail++;
        }
        if(tmp->right != NULL)//right
        {
            p[tail] = tmp->right;
            tail++;
        }
        head++;
    }
    return;
}