節點拒絕在二叉搜索樹中刪除

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; 
     } 
}