1

我正在尝试从二叉树函数中删除。我有点迷路了，所以我试图逐个处理它，首先是我要删除的值是否在 BST 的根目录中。为了测试我的函数，我首先调用 printcontents() 函数来打印树的所有内容，然后调用 remove(8) [8 是我的根目录中的值），然后调用 printcontents( ） 再次。我这样做的方式是尝试用树左侧的“最右边”值替换根。当我第二次调用 printcontents 时，它会正确打印新的根值，但是当它继续打印内容并到达该值曾经的位置时，它有一个随机长数“-572......” （虽然我不认为这个数字很重要）然后我的程序崩溃了。

这是我的删除功能：

void BinarySearchTree::remove(int value) {

      Node* tmp = head;
      Node* tmp2 = head;


     if (head->data == value && head->left != NULL) {

        tmp=tmp->left;

        while (tmp->right != NULL) {
            tmp=tmp->right;

        }

        while (tmp2->right->right != NULL) {
            tmp2=tmp2->right;

        }

        if (tmp->left == NULL) {     

        head->data = tmp->data;
        tmp2->right = NULL;
        delete tmp;

        }

        if (tmp->left != NULL) {

            head->data = tmp->data;
            tmp2->right = tmp->left;
            delete tmp;

        }




}

这显然是不完整的，但我正在测试它以仅处理根被删除并被树左侧最右边的值替换的情况（假设有一个左侧），并且我觉得从逻辑上讲它应该可以工作，所以也许是当我“删除 tmp”时出现问题。我不知道是否有必要发布我的整个程序，但如果有，请告诉我！

4

1 回答 1

1

我可以建议您不要写出 root 权限，而不要像在 CLRS 中处理的那样处理这个案例：这是两个不同的案例。1. 当要删除的节点是叶子时 2. 当要删除的节点是非叶子时（在这种情况下，用有序的后继/前任替换它）。

根删除显然属于第二种情况。这只是一个建议。

于 2013-10-24T04:17:19.980 回答