节点拒绝在二叉搜索树中删除

Question

我目前正在编写一个程序，它将从二叉搜索树中删除一个节点（其中包括删除是我的问题），而且我遇到了问题删除步骤，特别是删除具有2个子节点的节点的最后一步。

我要删除的方式是here。 我将最左下方的子节点（如果位于根的右侧）或最右下方的子节点（如果位于左侧）替换为要删除的节点的值，然后删除我刚刚复制的节点。

我已完成所有步骤，除了删除从我复制的节点;出于某种原因，我的代码没有正确删除它，并为我刚刚尝试删除的节点创建了一个随机数值以及一个随机父值。我相信这是由树中某个未修复的链接引起的，但是作为一个没有经验的程序员，我无法找到它。希望对BST更精通的人可以帮助我。

这里是我的代码（我只包括了影响删除功能的代码，我不认为有必要包括后这样来的破坏作用的东西）：

#include <iostream> 

using namespace std; 

struct node 
{ 
    int data; //Stores data within the trees pointers 
    node * parent; //Used to move up in the tree 
    node * left; //Used to move left in the tree 
    node * right; //Used to move right in the tree 
}; 

node * create (int data, node **tree); //Function to insert elements into the tree 

void printTree (node * tree); //Function to print the tree 

node *search(int key, node *tree); //Function to find data in the tree 

node * delNode (node * tree, node * root); //Function to delete data from the tree 

node * findSmallestRight (node * tree, node **smallest); 

node * findLargestLeft (node * tree, node **smallest); 

int main() 
{ 
    node * root = NULL; //Root will be the first element in the tree 
    node * current = NULL; //Return value for insert function to keep changes 
    int value; //Value entered by user 

    while (true) //Loop to fill tree with data 
    { 
     cout << "Enter an integer, 0 to quit" << endl; 
     cin >> value; 
     if (value == 0) //Quit when 0 is entered, BEFORE entering it into the tree 
      break; 
     current = create(value, &root); //Insert value into the tree 
     cout << "After inserting " << value << " tree is:" << endl; 
     printTree(root); //Print the tree 
    } 
    while (true) //Loop to delete data from tree 
    { 
     cout << "Search for a value to delete from the tree, 0 to quit" << endl; 
     cin >> value; 
     if (value == 0) 
      break; 
     current = search(value, root); //Find the value in the tree 
     if (current == NULL) 
      cout << value << " is not in tree. Could not delete." << endl; 
     else 
     { 
      root = delNode(current, root); //Delete the data 
      cout << value << " has been deleted. The tree is now:" << endl; 
      printTree(root); //print the tree 
     } 
    } 
    destroy(root); //Destroy the tree 
    return 0; 
} 

void printNode (node * Node) //Function to print a node in the tree 
{ 
    cout << "addr= " << Node << " parent= " << Node->parent << " left= " << Node->left << " right= " << Node->right << " data= " << Node->data << endl; 
} 

node * createNode (int data) //Function to create a new node in the tree 
{ 
    node * newNode = NULL; //Create a new pointer 
    newNode = new node; //Make that pointer a node 
    newNode->data = data; //Fill it with data 
    newNode->left = NULL; //Make it point left to NULL 
    newNode->right = NULL; //and right to NULL 
    return newNode; 
} 

node * create (int data, node **tree) //Function to insert elements into the tree 
{ 
    node * newNode = NULL; //Create a new pointer 
    if ((*tree) == NULL) //Check if tree exists already 
    { 
     //If it doesn't, create a new node and make it the root 
     newNode = createNode(data); 
     *tree = newNode; 
     (*tree)->parent = NULL; //Root has a parent of NULL 
    } 
    else if (data < (*tree)->data) //If the data is smaller than root, insert on the left 
    { 
     if ((*tree)->left == NULL)//If there is no node on the left, create a new one and point to it 
     { 
      newNode = createNode(data); 
      (*tree)->left = newNode; 
      newNode->parent = *tree; 
     } 
     else 
     { 
      newNode = create(data, &((*tree)->left));//If there is a node on the left, repeat function until there isn't 
     } 
    } 
    else //If the data is greater than or equal to root, insert on the right 
    { 
     if ((*tree)->right == NULL) 
     { 
      newNode = createNode (data); //If there is no node on the right, create a new one and point to it 
      (*tree)->right = newNode; 
      newNode->parent = *tree; 
     } 
     else 
     { 
      newNode = create(data, &((*tree)->right)); //If there is a node on the right, repeat function until there isn't 
     } 
    } 
    return newNode; //Return the new node to keep the changes to the value 
} 

void printTree (node * tree) //Function to print the tree 
{ 
    if (tree != NULL) //Check if tree actually existsreturn root; 
    { 
     //Recursively print the left side, then the root, then the right side 
     printTree(tree->left); 
     printNode(tree); 
     printTree(tree->right); 
    } 
} 

node *search(int key, node *tree) //Function to find data in the tree 
{ 
    if (tree == NULL || tree -> data == key) 
    { 
     return tree; //If the data either does not exist or has been found, return 
    } 
    if (key < tree->data) 
    { 
     return search(key, tree->left); //If the data is less than the current data, keep checking the left 
    } 
    else 
    { 
     return search(key, tree->right); //If the data is more than the current data, keep checking the right 
    } 
} 

node * delNode (node * tree, node * root) 
{ 
    node * parent; //Node for quick-reference and manipulation of tree's parent 
    if (tree->parent != NULL) //If tree value is not root assign a parent (root has parent of NULL so assigning would crash) 
    { 
     parent = tree->parent; 
    } 
    node * curr = tree; 
    //Removing node with 2 children on right 
    //There would also be cases for no children, 1 child, and 2 children on left but I did not include them as the two former are done and the latter can be copied once this is solved :) 
    else if (tree->left != NULL && tree->right != NULL && parent->right == tree && parent != NULL) 
    { 
     node * smallest; //Node to find smallest data value on left side 
     //Initialise and make it point to nothing 
     smallest = new node; 
     smallest->left = NULL; 
     smallest->right = NULL; 
     smallest->parent = NULL; 

     node * nReplace = NULL; //Node to replace data in tree 
     //Initialise and make it point to nothing 
     nReplace = new node; 
     nReplace->left = NULL; 
     nReplace->right = NULL; 
     nReplace->parent = NULL; 

     nReplace = findSmallestRight(tree, &smallest); //Function to find smallest data value on right side 
     tree->data = nReplace->data; //Replace tree's data with the new data 
     cout << nReplace << " " << nReplace->data << endl; //Debugging code 
     delete nReplace; //Delete nReplace 
     cout << nReplace << " " << nReplace->data << endl; //Debugging code 
    } 
    return root; //Return root to keep changes in tree 
} 

node * findSmallestRight (node * tree, node **smallest) //Function to find smallest data value on right side 
{ 
    node * parent = tree->parent; //Node for easy manipulation of tree's parent 
    //Check if current value is a potential candidate for smallest 
    if (tree->left == NULL && tree->right == NULL && parent->left == tree) 
    { 
     *smallest = tree; //If it is, make smallest equal to it 
    } 
    if (tree->left == NULL && tree->right != NULL) //Check if the are only branches on the right 
    { 
     findSmallestRight (tree->right, smallest); //Recurse through the right 
    } 
    else if (tree->left != NULL && tree->right == NULL) //Check if there are only branches on the left 
    { 
     findSmallestRight (tree->left, smallest); //Recurse through the left 
    } 
    else if (tree->left == NULL && tree->right == NULL) //Check if there are no branches on both sides 
    { 
     return *smallest; //Return the smallest 
    } 
    else 
    { 
     //If there are branches on both sides recurse through both 
     findSmallestRight (tree->left, smallest); 
     findSmallestRight (tree->right, smallest); 
    } 
    return *smallest; //Return the smallest 
} 

Answer 1

我觉得你findSmallestRight （）从递归到返回值都被搞乱了。

你只需要找到右子树上的SMALLEST元素，即对于正确的子元素迭代它的左子元素直到最后一个子元素，这将是最小的元素。

代码是简单为：（一见的名字协会图片）

if (current->left != NULL && current->right != NULL) //condition if you Current Node (to be deleted) has 2 Children 
    {  if((current->right)->left!=NULL) //If Right Child has left child go till last leftmost child. 
     { 
      Node* leftCurrent; 
      Node* leftCurrentPred; 
      leftCurrentPred=current->right; 
      leftCurrent=(current->right)->left; 
      while(leftCurrent->left != NULL) 
      { 
       leftCurrentPred=leftCurrent; 
       leftCurrent=leftCurrent->left; 
      } 
      current->data=leftCurrent->data; 
      delNode(leftCurrent, root); //Delete leftCurrent node i.e node with no child 
      leftCurrentPred->left=NULL; 
      cout<<item<<" has been removed from the Tree."<<endl; 
     } 
     else 
     { //If Right Child of current doesn't has Left child it is itself smallest one. 
      Node* temp=current->right; 
      current->data=temp->data; 
      current->right=temp->right; 
      delNode(temp,root); //Delete temp node i.e node with no child 
      cout<<item<<" has been removed from the Tree."<<endl; 
     } 
}