删除元素BST

苏拉夫·辛格

当我从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

Chipster

错误在这里：

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{
    //...
 }

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。