树的遍历（先中后序，非递归，层次遍历）-蒲公英云

树的遍历（先中后序，非递归，层次遍历）

树的遍历分为先序遍历，中序遍历以及后续遍历。其中分为递归形式与非递归形式，及层次遍历。

先序遍历：

首先访问根节点，然后访问左子树，最后访问右子树。

void PreOrder(BiTree T)
{
    if(p)
    {
          visit(p);
          PreOrder(p->lchild);
          PreOrder(p->rchild);
     }
}

中序遍历：

首先访问左子树，然后访问根节点，最后访问右子树。

void InOrder(BiTree T)
{
    if(p)
    {
          InOrder(p->lchild);
          visit(p);
          InOrder(p->rchild);
     }
}

后序遍历：

首先访问左子树，然后访问右子树，最后访问根节点。

void InOrder(BiTree T)
{
    if(p)
    {
          PostOrder(p->lchild);
          PostOrder(p->rchild);
          visit(p);
     }
}

以上三种都是递归形式，下面说一下非递归形式的中序遍历。这里采用了栈：

void InOrder2(BiTree T)
{
        InitStack(S);
        BiTree p = T;
       while(p || ! isEmpty(S))
       {
               if(p)
               {
                       Push(S,p);
                       p = p->lchild;
                }
                else
               {
                      Pop(S,p);
                      visit(p);
                      p = p->rchild;
               }
        }
}

层次遍历：

就是将节点一层一层的输出,这里利用了队列：

void levelOrder(BiTree T)
{
    InitQueue(Q);
    BiTree p = T;
    EnQueue(Q,p);
    while(p || !isEmpty(Q))
    {
        DeQueue(Q,p);
        visit(p);
        if(p->lchild)
            EnQueue(Q,p->lchild);
        if(p->rchild)
            EnQueue(Q,p->rchild);
    }
}