0

基本上，该程序由一个 BST 类组成，该类指向二叉树的第一个节点，并且节点也是它们自己的类。

BST 调用这个成员函数：

void remove(const T& x)
{
    removeNode(m_root, x);
    return;
}

这是删除节点的递归部分，它一直运行到完成：

template <typename T>
void removeNode(TreeNode<T>* &p, const T& x)
{
    if(p == NULL)
        return;

    if(x < p -> m_data)
        removeNode(p -> m_left, x);
    else if(x > p -> m_data)
        removeNode(p -> m_right, x);

    else
    {
        TreeNode<T>* tmp = new TreeNode<T>;

        if(p -> m_left == NULL)
        {
            tmp = p -> m_right;
            delete p;
            p = tmp;
        }
        else if(p -> m_right == NULL)
        {
            tmp = p -> m_left;
            delete p;
            p = tmp;
        }
        else
        {
            tmp = p -> m_right;
            TreeNode<T>* tmp2 = new TreeNode<T>;

            while(tmp -> m_left != NULL)
            {
                tmp2 = tmp;
                tmp = tmp -> m_left;
            }

            p -> m_data = tmp -> m_data;

            if(tmp2 != NULL)
                removeNode(tmp2 -> m_left, tmp -> m_left -> m_data);
            else
                removeNode(p -> m_right, p -> m_right -> m_data);
        }
    }

    return;
}

当 remove() 函数返回时，我出现了段错误，我想知道为什么？

4

1 回答 1

1

用户@WhozCraig 指出了您代码中最重要的错误：您分配了从未使用过的对象（也从未销毁！）：

TreeNode<T>* tmp = new TreeNode<T>;

TreeNode<T>* tmp2 = new TreeNode<T>;

后一个赋值导致条件

if(tmp2 != NULL)

始终满意，这会阻止您执行

else
    removeNode(p -> m_right, ...)

分支。

编辑

假设您有一个三节点树，键为 2、5 和 7。让我们分别表示节点node2和。假设是一个树根。假设您还要删除密钥 5。 然后：node5node7node5

  • *p == node5;
  • 前三个if不满足，控制权传递给else分支；
  • tmp被赋值p->m_right为&node7;
  • tmp2被分配了一个新的“空”对象——我们称之为nodeEmpty；
  • node7没有孩子，所以tmp->m_left是NULL，while循环被跳过，没有迭代；
  • 分配指令p->m_data = tmp->m_data导致node5获得密钥 7；
  • 因为tmp2 == &nodeEmpty那不是NULL，你打电话
    • removeNode(tmp2 -> m_left, tmp -> m_left -> m_data)

这显然是要从(?!)的不存在的左子树中删除一些东西，但是...... 但是在这一点上并且没有孩子，所以. 因此，访问会触发内存访问错误，并且进程在递归调用之前崩溃。nodeEmpty
tmp == &node7node7tmp->m_left == NULLtmp->m_left->m_dataremoveNode

于 2015-04-27T13:23:29.437 回答