c++ - 通过实现栈实现二叉搜索树的非递归析构函数

Question

此代码存在运行时错误，我无法确定问题所在。stack 类有一个基本的栈操作（pop push top），用来保存遍历的位置。

parityBST::~parityBST()
{

    if (root == NULL)
    {
        return;

    }
    else 
    {
        //postOrder non recursive traversal for destructor
        stack* s1 = new stack();
        s1->push(root);

        binaryNode* nodePtr= root;
        while (!s1->isEmpty())
        {
            //RUNTIME ERROR HERE (after several iterations)
            if (nodePtr->left)
            {
                s1->push(nodePtr->left);
                nodePtr = nodePtr->left;
            } else if (nodePtr->right)
            {

                s1->push(nodePtr->right);
                nodePtr = nodePtr->right;
            } else 
            {

                delete nodePtr;
                s1->pop();
                nodePtr = s1->getTop();
            }

        }

    }

}

Answer 1

您delete在（nodePtr's parent）->left 中时正在输入 nodePtr，但没有将其更改为 null，因此您再次进入它。

尝试添加这个：

s1->pop();
binaryNode* parent = s1->getTop()
if (parent->left==nodePtr)
    parent->left = NULL;
else
    parent->right = NULL;
delete nodePtr;
nodePtr = parent;