删除二叉搜索树的节点

Question

当我从二叉树(BT)中删除25时，它能完美地工作。 但是当我想删除另一个数字，比如17时， 它会将17与其他一些数字一起从BT中删除。

#include<iostream>
using namespace std;

struct node
{

    int data;
    node *left;
    node *right;
};

node *root = NULL;

node* createnode(int data)
{

    node *t = new node();
    t->data = data;
    t->left = NULL;
    t->right = NULL;
    return t;

}

node* min(node*);

node* insert(node *root, int data)
{

    if (root == NULL)
    {


        root = createnode(data);
        return root;
    }

    else{

        node *t = root;
        if (data <= t->data)
            t->left = insert(t->left, data);
        else{
            t->right = insert(t->right, data);
        }
    }
}

node* print(node *root)
{

    if (root == NULL)
    {

        return root;
    }

    else{

        cout << root->data << " ";
        print(root->left);
        print(root->right);
    }

    return root;
}

node* deleten(node *root, int data)
{

    if (root == NULL)
        return root;
    else{
        if (data<root->data)
            root->left = deleten(root->left, data);
        if (data>root->data)
            root->right = deleten(root->right, data);
        else{
            if (root->left == NULL && root->right == NULL)
            {
                node *t = root;
                root = NULL;
                delete t;
            }
            else if (root->left == NULL)
            {
                node *t = root;
                root = root->right;
                delete t;
            }
            else if (root->right == NULL)
            {
                node *t = root;
                root = root->left;
                delete t;
            }
            else{
                node *t = min(root->right);
                root->data = t->data;
                root->right = deleten(root->right, t->data);
            }
        }
        return root;
    }
}

node* min(node *root)
{

    if (root == NULL)
        return root;
    else{
        if (root->left != NULL)
            min(root->left);
        else{
            return root;
        }
    }
}

int main()
{

    root = insert(root, 15);
    root = insert(root, 10);
    root = insert(root, 8);
    root = insert(root, 12);
    root = insert(root, 11);
    root = insert(root, 20);
    root = insert(root, 23);
    root = insert(root, 17);
    root = insert(root, 25);
    root = print(root);
    cout << endl;
    root = deleten(root, 17);
    root = print(root);
}

案例1：

删除前：15 10 8 12 11 20 17 23 25

删除后：15 10 8 12 11 23 25 // root=deleten(root,17);

期望结果：15 10 8 12 11 20 23 25

案例2：

删除前：15 10 8 12 11 20 17 23 25

删除后：15 10 8 12 11 20 17 23 // root=deleten(root,25);

期望结果：15 10 8 12 11 20 17 23

案例3：

删除前：15 10 8 12 11 20 17 23 25

删除后：17 12 11 23 25 // root= deleten(root,8);

期望结果：15 10 12 11 20 17 23 25

- sourav singh

---

你尝试过使用调试器来查看 root= deleten(root,8); 发生了什么吗？ - PilouPili

这是一棵树，因此简单地删除一个节点将删除其子节点。如果它没有子节点（可能是25的情况），那么这不是问题，但如果它有子节点，则是一个重大问题。您需要在删除后重新组织树。 - user10957435

也许你的意思是这里应该用else if，而不是if：if (data<root->data) root->left = deleten(root->left, data); if... - user10957435

Answer 1

错误在这里：

if (data<root->data)
    root->left = deleten(root->left, data);
if (data>root->data)
    root->right = deleten(root->right, data);
else{
    //...
 }

如果data小于root->data，它将删除树的left侧和节点，因为您正在使用if而不是else if来测试右侧。

答案很简单，只需改为else if：

if (data<root->data)
    root->left = deleten(root->left, data);
else if (data>root->data)
    root->right = deleten(root->right, data);
else{
    //...
 }

- user10957435

---

你可能已经注意到了，在 if (root == NULL) return root; 后面的 else 是多余的，因为函数已经 返回 了。最好避免额外的缩进级别。你还可以推荐阅读 如何调试小程序。 - David C. Rankin