二叉树的前序、中序、后续遍历

本篇博文用来介绍二叉树的前序、中序、后续遍历。先通过递归实现三种方式的遍历，再讨论如何采用非递归的方法实现要求。
二叉树的遍历：就是按一定的顺序对每一个结点进行操作，具体操作视情况而定，主要是经过每个结点。
前序：先根结点，再左子树，最后右子树。
中序：先左子树、再根结点、最后右子树。
后序：先左子树、再根结点、最后右子树。

1、递归方法实现三种不同方式的遍历。

前序遍历：

void PreOrderTraverse(BiTree root)            //前序遍历二叉树(递归)
{
    if (root)
    {
        cout << root->data;                   //输出根节点的值
        PreOrderTraverse(root->lchild);       //前序遍历左子树
        PreOrderTraverse(root->rchild);       //前序遍历右子树
    }
}

中序遍历：

void InOrderTraverse(BiTree root)             //中序遍历二叉树
{
    if (root)
    {
        InOrderTraverse(root->lchild);        //中序遍历左子树
        cout << root->data;                   //输出根节点的值
        InOrderTraverse(root->rchild);        //中序遍历右子树
    }
}

后序遍历：

void PostOrderTraverse(BiTree root)           //后序遍历二叉树
{
    if (root)
    {
        PostOrderTraverse(root->lchild);      //后序遍历左子树
        PostOrderTraverse(root->rchild);      //后序遍历右子树
        cout << root->data;                   //输出根节点的值
    }
}

2、非递归实现

中序遍历：
先遍历左子树，在这过程，将经过的结点存入堆栈中，直到空结点；这是弹出一个结点，然后输出，再遍历结点的右子树。

void InOrderTraverse1(BiTree root)
{ //非递归中序遍历二叉树
    if (root == NULL)
    {
        cout << "空二叉树" << endl;
        return;
    }
    stack<BTNode *> s;            //用来存放结点指针的栈
    BTNode * p;
    p = root;
    while (p || !s.empty())
    {
        while (p) //遍历左子树
        {
            s.push(p);//入栈
            p = p->lchild;
        }
        //p为空
        p = s.top();  //获取栈顶元素
        s.pop();
        cout << p->data;           //访问根节点
        p = p->rchild;             //遍历右子树，当做一个新的树，重新进行while(p||!s.empty())
    }
    return ;
}

后序遍历：
方法1：

void PostOrderTraverse2(BiTree root)
{  //后序遍历二叉树(非递归)
    if (root == NULL)
    {
        cout << "空二叉树" << endl;
        return;
    }
    enum Tag{left,right};
    struct snode
    {
        BTNode *p;
        Tag tag;
    }temp;
    stack<snode> s;
    BTNode *p=root;
    while (p || !s.empty())
    {
        while (p)                  //遍历左子树
        {
            temp.p = p;            //根结点第一次被碰到
            temp.tag = Tag::left;
            s.push(temp);
            p = p->lchild;
        }
        temp = s.top();
        s.pop();
        if (temp.tag == Tag::left)  //再次碰到根结点，判断根节点的右子树有没有被访问，依此决定是否访问根结点
        {//不访问根节点
            temp.tag = Tag::right;
            s.push(temp);
            p = temp.p->rchild;    //遍历右子树
        }
        else 
        {
            cout << temp.p->data;
            p = NULL;
        }
    }
    return;
}

方法2：