我实现了一个迭代的后序算法以及pre和inorder但是迭代后的顺序不起作用,我所有的努力都白费了。
程序在按后序打印树的最后一个节点数据之前崩溃。
这是代码片段。

t=root;

    while(t!=NULL || !st.empty())
    {
        if(t!=NULL)
        {
            if(t->r!=NULL)
                st.push(t->r);
            st.push(t);
            t=t->l;
        }
        else
        {
            t=st.top();
            st.pop();
            if(t->r!=NULL && t->r==st.top())
            {
                st.pop();
                st.push(t);
                t=t->r;
            }
            else
            {
                cout<<t->data<<" ";
                t=NULL;
            }
        }
    }

更多信息:st是stl堆栈,将根视为全局(在我的代码中,上面的代码片段是类的一部分,根变量也是)

最佳答案

问题就在这一行:

if(t->r!=NULL && t->r==st.top())

问题是此时堆栈可能为空,在这种情况下调用st.top()将导致程序崩溃。
您可以将该行更改为:
if(t->r!=NULL && !st.empty() && t->r==st.top())

例子
如果树的根在其左侧连接到null,而在其右侧连接到a,则程序将:
推A(堆栈现在有A)
推根(堆栈现在有一个,根)
弹出根(堆栈现在有一个)
弹出A(堆栈现在为空)
推根(堆栈现在有根)
推A(堆栈有根,A)
弹出A并打印A的数据(堆栈有根)
弹出根目录(堆栈现在为空)
在这个阶段,程序有一个空堆栈和t->r!=空,因此它将访问st.top

10-07 19:01
查看更多