c++ - 通过迭代进行二叉搜索树后序遍历

Question

我实现了迭代后序算法以及 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 堆栈并将根视为全局(在我的代码中，上面的代码片段是类的一部分，根变量也是)

Answer 1

问题出在这一行:

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

问题在于此时堆栈可能为空，在这种情况下调用 st.top() 将导致程序崩溃。

您可以通过将行更改为以下内容来解决此问题:

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

例子

如果您的树的根节点在其左侧连接到 NULL，而在其右侧连接到 A，则程序将:

1. 推送 A(堆栈现在有 A)
2. 推送根(堆栈现在有 A，根)
3. pop root(栈现在有A)
4. 弹出 A(栈现在为空)
5. 推送根(堆栈现在有根)
6. 压入A(栈有根，A)
7. 弹出A并打印A的数据(栈有根)
8. pop root(栈现在是空的)
9. 在这个阶段程序有一个空栈和 t->r!=NULL 所以它将访问 st.top