我实现了一个迭代的后序算法以及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