For this assignment, you are required to implement remove method to remove a nod

Question

 For this assignment, you are required to implement remove method to remove a node from the BT. 1. Create a class named BT.java, which extends BTA, then implement two abstract methods definded in BTA.java 2. Create an aplication to test your implementation of the remove method. You simply create a file named     BTApp.java, then copy/paste the following code ====================================== public class BTApp{     public static void main(String[] args){       BT tree=new BT();       tree.insert(new Node(100));       tree.insert(new Node(20));       tree.insert(new Node(56));       tree.insert(new Node(199));       tree.insert(new Node(82));       tree.insert(new Node(82));       tree.inorder();       tree.remove(56);       tree.remove(new Node(82));       tree.inorder();    } } 

Explanation / Answer

//Class BTApp
public class BTApp
{
   public static void main(String[] args)
   {
   BT bt = new BT();
   bt.setRoot(bt.insert(100));
   bt.setRoot(bt.insert(20));
   bt.setRoot(bt.insert(56));
   bt.setRoot(bt.insert(199));
   bt.setRoot(bt.insert(82));
   bt.setRoot(bt.insert(82));

//start of Testing deletion of nodes.
System.out.print("Nodes in the BST (In order) are: ");
   bt.printTree(bt.getRoot());
System.out.println("");

System.out.print("Nodes in the BST (In order) are: ");
   bt.printTree(bt.deleteNode(bt.getRoot(), 56));
// bt.setRoot(bt.insert(56));
System.out.println("");

   System.out.print("Nodes in the BST (In order) are: ");
   bt.printTree(bt.deleteNode(bt.getRoot(), 82));
bt.setRoot(bt.insert(82));
System.out.println("");

}
}
//Class BTA
class BTA
{
   //For left child
   Node left;
   //For right child
   Node right;
   //For value
   int data;
   //Constructor
   public BTA(int data)
   {
   this.data = data;
   this.left = null;
   this.right = null;
   }
}

//Class BT derived from BTA
class BT extends BTA
{
   private Node root;
   //Constructor for BT
   public BT()
   {
       //Calls base class constructor
       super(0);
       //Initializes root to null
   root = null;
   }
   //Returns the root note
   public Node getRoot()
   {
   return root;
   }
   //Sets the root node
   public void setRoot(Node root)
   {
   this.root = root;
   }
   //Insearts a node
   public Node insert(int data)
   {
   return insert(root, data);
   }
   //Finds the position to insert
   private Node insert(Node node, int data)
   {
       //Checks for null if null creates a node
   if( node == null )
       {
           node = new Node(data);
   }
   else
       {
           //If the inserted data lessthan or equal to the current node data put it in left otherwise put it in right
       if (data <= node.data)
           {
       node.left = insert(node.left, data);
       }
       else
           {
       node.right = insert(node.right, data);
       }
       }
   return node;
   }
   //Prints the nodes
   public void printTree(Node node)
   {
   //If no node available
       if( node == null)
           return;

   printTree(node.left);
   System.out.print(node.data + " ");
   printTree(node.right);
   }

// All posible cases
// case 0: No children - Leaf Node - Delete the Parent Link
// case 1: 1 Child available - Make the Parent to point to the Node Child and Delete the node
// case 2: Find MIN from Right Sub Tree, Copy the value in the Targetted Node and Delete Duplicate Node
//                        (OR)
// Find Max from Left Sub Tree, Copy value in Targetted BST Node and Delete Duplicate Node
//
   public Node deleteNode(Node myN, int data)
   {
   if( myN == null) return null;

   Node p, p2;

   if (data < myN.data)
   {
   myN.left = deleteNode(myN.left, data);
   }
   else if( data > myN.data)
   {
   myN.right = deleteNode(myN.right, data);
   }
   else
   {
       //Leaf Node
           if (myN.left == null && myN.right == null)  
           {
       return null;
       }
           //One Child
       else if (myN.left == null)
       {
            return myN.right;
       }
           //One Child          
           else if (myN.right == null)
       {
       return myN.left;
       }
           //2 Children
       else
       {
       p2 = myN.right;
       p = myN.right;
       while (p.left != null)
               {
        p = p.left;
       }
       p.left = myN.left;
       return p2;
       }
   }
   return myN;
   }
}

Output

Nodes in the BST (In order) are: 20 56 82 82 100 199
Nodes in the BST (In order) are: 20 82 82 100 199
Nodes in the BST (In order) are: 20 82 100 199

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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