Any one can help me fix my remove function in the binary search tree in c code?

Question

Any one can help me fix my remove function in the binary search tree in c code?

/* This function is used to remove and deallocate the leftmost descendent of the argument node

   param: curr       The node whose leftmost descendent we wish to find
   param: parent   curr's parent, included to make the operation easier to perform
   param: origAncestor       the node on which the original leftmost call was given
   post:   the leftmost descendent of curr is removed from the tree and freed
   ret:   the value stored in the leftmost descendent of curr
*/
TYPE _removeLeftMost(Node* curr, Node* parent, Node* origAncestor)
{
    TYPE removeThisVar;
   struct Node *temp;
  
   if(curr->left!=NULL)
   {
curr->left =_removeLeftMost(curr->left,curr , ?)/* no idea how to use origAncestor*/
       return curr;
   }  
   else
   {

   }
  
}

/* This function is used to remove a node from a subtree of the BST

   param: curr       The root of the subtree we are currently examining for the value
   param: val       The value to be removed from the subtree
   post: a node containing val has been removed from the tree and freed
   ret: the node where we currently reside in the tree.
           Note that this function uses recursion to put the tree back together as stack
           frames are removed.
*/
Node* _removeNodeFromSubtree(Node* curr, TYPE val)
{
   struct Node *temp;
  
   if(_compare(val, curr->val) == -1)
curr->left = _removeNodeFromSubtree(curr->left, val);
else if(_compare(val, curr->val) == 1)
curr->right = _removeNodeFromSubtree(curr->right, val);
else
{
if (cur->right != NULL)
           {
               curr->right = _removeLeftMost(curr->right, curr, ?);
               return curr;
           }
           else
           {
               temp = curr->left;
               free (curr);
               return temp;
           }
}
return cur;
return NULL;
}

Explanation / Answer

If nodes in the tree contain pointers to the parent node, then 1) There is no need to pass the parent of the node to delete as an argument to the delete function. 2) For every assignment of the form a->left=b or a->right=b, you will need to add code b->parent=a. For every assignment of the form tree->root=b, you will need to add code b->parent=NULL. */ #include #include #include #include "mcs360.c" #define TreeEntry char * typedef struct TreeNode { TreeEntry entry; struct TreeNode *left; struct TreeNode *right; } TreeNode; typedef struct BinarySearchTree { TreeNode *root; int size; } BinarySearchTree; /* delete( tree, p, parent) deletes node p from the binary search tree (first argument). The third argument to delete()is the parent of p (or NULL if p is the root). If the parent is not already known, it may be found by traversing the path from the root to p. The parent is the last node before p on this path. */ void delete( BinarySearchTree *tree, TreeNode *p, TreeNode *parent) { TreeNode *successor; /* Successor of p. */ TreeNode *successor_parent; /* Parent of successor. */ /* Case in which node to be deleted (node p) has no left child. */ if ( p->left == NULL ) { if ( parent == NULL ) tree->root = p->right; else if ( p == parent->left ) parent->left = p->right; else parent->right = p->right; } /* Case in which node to be deleted (node p) has no right child. */ else if ( p->right == NULL ) { if ( parent == NULL ) tree->root = p->left; else if ( p == parent->left ) parent->left = p->left; else par ent->right = p->left; return; } /* Case in which node to be deleted (node p) has two children. In this case, the successor of node p cannot have a left child. */ else { successor = p->right; successor_parent = p; while ( successor->left != NULL ) { successor_parent = successor; successor = successor->left; } /* At this point, node successor is the successor of node p. We remove node successor from its current position and link it into the position of node p. Then node p is deleted. An alternative would be to copy the data in node successor to node p, and then delete node successor. */ if ( parent == NULL ) tree->root = successor; else if ( p == parent->left ) parent->left = successor; else parent->right = successor; if ( successor == successor_parent->left ) successor_parent->left = successor->right; else successor_parent->right = successor->right; successor->left = p->left; successor->right = p->right; } free(p); --tree->size; }

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.