I have a struct called TreeNode with an int key, and left right and parent. I am trying to delete a node from a tree with my DeleteNode function and it is not working. I am supposed to replace the deleted node in my DeleteNode function with the max value from the left subtree. My transplant and max functions are helper functions for DeleteNode. My issue is I'm not sure where in my DeleteNode function I should be comparing the node value I am at to the value I am passing in through the function. I have a comment in my code with astericks where I'm confused what to do. Any help would be greatly appreciated!
void transplant(TreeNode* u, TreeNode* v) //swaps u with v
{
if (u->parent == NULL) //if u was root, make v new root
u->parent = v;
else if (u == u->parent->left) //if u is smaller than it's parent
u->parent->left = v; //set v to the left child of parent of u. Swap them at left, really
else
u->parent->right = v; //otherwise swap them at right
if (v != NULL) //reassign parents to double link
v->parent = u->parent;
}
TreeNode* maximum(TreeNode* n)
{
while (n->left != NULL)
n = n->left;
return n;
}
void deleteNode(TreeNode *node, int key)
{
if (node->left == NULL) //if there is no left child
transplant(node, node->right); //swap
else if (node->right == NULL) //if there is no right child
transplant(node, node->left); //swap
else
{
if(node->key == key){ //****This if comparison must be wrong***
TreeNode* temp = maximum(node->right); //make temp the max on right
if (temp->parent != node ) //if it is more than one chain down
{
transplant(temp, temp->right); //swap temp and it's right branch
temp->right = node->right; //set right branch to nodes right
temp->parent->right = temp; //set temp to the right child
}
transplant(node, temp); // transplant
temp->left = node->left; //get nodes left branch
temp->left->parent = temp; //replace
}
}
}
Aucun commentaire:
Enregistrer un commentaire