I need help adding the code to delete the root in each case. Case 1, case 2, and
ID: 3694177 • Letter: I
Question
I need help adding the code to delete the root in each case. Case 1, case 2, and case 3. Thank you.
public boolean delete(String targetKey)
{ boolean found;
TreeNodeWrapper p = new TreeNodeWrapper();
TreeNodeWrapper c = new TreeNodeWrapper();
TreeNode largest;
TreeNode nextLargest;
found = findNode(targetKey, p, c);
if(found == false) // node not found
{
System.out.println("The employee cannot be found");//node is not found in structure
return false;
}
else
{ if(c.get().lc == null && c.get().rc == null) // case 1: deleted node has no children
{ if(p.get().lc == c.get()) // deleted node is a left child
p.get().lc = null;
else // deleted node is a right child
p.get().rc = null;
}// end case 1
else if(c.get().lc == null || c.get().rc == null) // case 2: delete node has one child
{ if(p.get().lc == c.get()) //deleted node is a left child
{ if(c.get().lc != null) // deleted node has a left child
p.get().lc = c.get().lc;
else
p.get().lc = c.get().rc;
}
else // deleted node is a right child
{ if(c.get().lc != null) // deleted node has a left child
p.get().rc = c.get().lc;
else
p.get().rc = c.get().rc;
}
}// end case 2
else // case 3: deleted node has two children
{ nextLargest = c.get().lc;
largest = nextLargest.rc;
if(largest != null) // left child of deleted node has a right subtree
{ while(largest.rc != null) // move down the right edge of right subtree
{ nextLargest = largest;
largest = largest.rc;
}
c.get().node = largest.node; // "copy" largest node's info into deleted node
nextLargest.rc = largest.lc; // save left subtree of largest node
}
else // left child of deleted node does not have a right subtree
{ nextLargest.rc = c.get().rc; // save the right subtree of the deleted node
if(p.get().lc == c.get()) //deleted node is a left child
p.get().lc = nextLargest; // deleted node's parent jumps around deleted node
else // deleted node is a right child
p.get().rc = nextLargest; // deleted node's parent jumps around deleted node
}
}// end of case 3
return true;
}
}// end of delete method
Explanation / Answer
// Java program to demonstrate delete operation in binary search tree
class BinarySearchTree
{
/* Class containing left and right child of current node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree()
{
root = null;
}
// This method mainly calls deleteRec()
void deleteKey(int key)
{
root = deleteRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node deleteRec(Node root, int key)
{
/* Base Case: If the tree is empty */
if (root == null) return root;
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(root.right, root.key);
}
return root;
}
int minValue(Node root)
{
int minv = root.key;
while (root.left != null)
{
minv = root.left.key;
root = root.left;
}
return minv;
}
// This method mainly calls insertRec()
void insert(int key)
{
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key)
{
/* If the tree is empty, return a new node */
if (root == null)
{
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder()
{
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Driver Program to test above functions
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal of the given tree");
tree.inorder();
System.out.println(" Delete 20");
tree.deleteKey(20);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 30");
tree.deleteKey(30);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 50");
tree.deleteKey(50);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
}
}
output:
NOTE: your code seems to be little confusing. So, I have done it in my way.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.