尝试从二叉搜索树中删除节点

当节点被删除后尝试显示我的树时，出现内存错误。
这是我删除（删除）方法：尝试从二叉搜索树中删除节点

void binarySearchTree::remove(int x, node * r) 
{ 
    bool found = false; 
    node * previous = NULL; 

    if (root == NULL) 
    {cout << "Tree is empty. Nothing to remove." << endl; return;} 

    while (!found) 
    { 
     if (x < r->data) 
     { 
      previous = r; 
      r = r->left; 
     } 
     else if (x > r->data) 
     { 
      previous = r; 
      r = r->right; 
     } 
     else 
      found = true; 
    } 


    if (r->left == NULL && r->right == NULL)  //case 1: node to be deleted is a leaf (no children) 
    { 
     delete r; 
     return; 
    } 
    else if(r->left == NULL && r->right != NULL) //case 2: node only has a right child 
     previous->right = r->right; 
    else if (r->left != NULL && r->right == NULL) //case 2: node only has a left child 
     previous->left = r->left; 
    else 
    {            //case 3: node has two children 
     node * minNode = findMinNode(r->right);  //finds min node in the right sub tree 
     r->data = minNode->data; 
     delete minNode; 
     return; 
    } 
    delete r; 
}

我findMinNode方法：

binarySearchTree::node * & binarySearchTree::findMinNode(node * r) 
{ 
    if (r == NULL)  //if tree is empty 
     return r; 

    if (r->left == NULL && r->right == NULL) 
     return r; 
    else if (r->left != NULL) 
     return findMinNode(r->left); 
    else 
     return findMinNode(r->right); 
}

我的显示方法（使用前序遍历）：

void binarySearchTree::display(node * r) 
{ 
    if (r == NULL) 
     return; 

    display(r->left); 
    cout << r->data << endl; 
    display(r->right); 
}

我使用的是公众display()方法，然后调用这个私人display(node * r)方法。

我知道这个问题是，当我使用delete，因为当我通过代码加强，并得到了我的display()方法，当它检查是否r== NULL我刚刚删除的节点上，地址是不是NULL用的地址0x000000000，而是有0x000000001。因此，我的程序会崩溃。我从来没有遇到过这个问题。任何帮助将不胜感激。

我应该补充一点，我按照这个确切的顺序插入了这些值：10,5,34,2,8,12,25,6,18,27,38,11。我试图用值删除节点12因为它有两个孩子。

来源

2015-09-22 David Velasquez

删除指针不会将其设置为NULL。这是你所期待的吗？ –

@NeilKirk我以为它呢？那么，如何在释放内存的同时创建这个NULL是一个很好的选择？ –

'delete r; r = NULL;' –

当你删除一个节点时，你需要将指向它的指针NULL，这在你的例子中可以是root，previous-> left或previous-> right。如果您以前更改为node **，并将其指向前一个指针（初始化为&根目录），则可以仅指*previous = null或*previous = r->right。

来源

2015-09-22 04:35:40 1201ProgramAlarm

如果您可以详细说明，因为我不了解您的解决方案。尽量按照我的理解尽力去做你所说的话，但它仍然崩溃。 –

在找到的循环中，使用'previous =＆r-> left; r = r-> left'。如果一片树叶，“删除r; * previous = null;'。只有正确的孩子：'* previous = r-> right;'。你需要用'minNode'做类似的事情，因为指向它的指针会在你删除它之后悬而未决。 – 1201ProgramAlarm

尝试从二叉搜索树中删除节点

回答

相关问题