Rui_Xian_Qi_Mu
2016-10-23 16:03
采纳率: 100%
浏览 947
已采纳

这段二叉树的后序非递归遍历错了,请问怎么改

 #include<iostream>
using namespace std; 
template<class DataType>
struct element
{
    BiNode<DataType> * ptr;
    int flag;       //这是一个标志,flag=1时表示第一次出栈,只遍历完左子树,该节点不能访问,flag=2时表示只遍历完右子树,该节点可以访问 
};

//设根指针为bt 
template<class DataType>
void BiTree<DataType>::PostOrder(BiNode<DataType> * bt)
{
    top = -1;           //采用顺序栈,并假定栈不会发生上溢 
    while(bt!=NULL||top!=-1)        //两个条件都不成立才会退出循环 
    {
        while(bt!=NULL)
        {
            top++;
            s[top].ptr=bt;
            s[top].flag=1;      //root连同标志flag入栈 
            bt=bt->lchild;
        }
        while(top!=-1&&s[top].flag=2)
        {
            bt=s[top--].ptr;
            cout<<bt->data;
        }
        if(top!=-1)
        {
            s[top].flag=2;
            bt=s[top].ptr->rchild;
        }
    }
}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • Rui_Xian_Qi_Mu 2017-02-07 06:16
    已采纳

    实际这段代码只是在走到根节点时出现了死循环,只要加一句bt=NULL;终止了循环,问题就得以解决了!

    点赞 评论
  • devmiao 2016-10-23 16:06
    点赞 评论
  • SeaTalks 2016-10-23 17:10

    最后一个if中,没有判断有没有右子树就直接让bt=右子树了,这样若没有右子树到下一轮循环时,程序就退出了

    点赞 评论
  • 蓝月心语 2016-10-24 05:25
    
    struct snode//定义链栈节点
    {
        bitree data;
        struct snode *next;
    };
    typedef snode *linkstack;
    
    int init_linkstack(linkstack &s)//初始化栈
    {
       s=NULL;
      return ok;
    }
    
    int isempty(linkstack s)
    {
        if (s == NULL)
            return 1;
        return 0;
    }
    int push(linkstack &s, bitree p)//进栈
    {
        linkstack pr;
        pr = (snode*)malloc(sizeof(snode));
        if (!pr)
            return false;
        pr->data = p;
        pr->next = s;
        s = pr;
        return ok;
    }
    int pop(linkstack &s, bitree &p)//出栈
    {
        if (!isempty(s))
        {
            p = s->data;
            s = s->next;
        }
        return ok;
    }
    int gettop(linkstack s, bitree &p)
    {
        p = s->data;
        return ok;
    }int feidiguipostorder(bitree t)//非递归后序遍历
    {
        linkstack s;
        init_linkstack(s);//初始化空栈,不带头结点
        bitree p = t, r=NULL;//r用于记录返回根节点时右子树是否访问过,p为各子树的根节点
        while (p || !isempty(s))
        {
            if (p)
            {
                push(s, p);//向左走到最左端
                p = p->lchild;
            }
            else//然后
            {
                gettop(s, p);//取栈顶元素,p子树最左端的结点
                if (p->rchild&&p->rchild != r)//如果该节点有右孩子,且未被访问过
                {
                    p = p->rchild;//转向右孩子
                    push(s, p);//压入栈中
                    p = p->lchild;//转向孩子结点的左结点
                }
                else//该节点右孩子不存在或者被访问过
                {
                    pop(s, p);//出栈,访问节点p
                    visit1(p);
                    r = p;//记录最近访问过的结点
                    p = NULL;//结点访问玩后重置p指针
                }
            }
    
        }
        return ok;
    }
    
    
    点赞 评论

相关推荐 更多相似问题