欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-20 13:52:56
...

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

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: