Peruse these classes. This assingment must be implemented by modifying/expanding

Question

Peruse these classes. This assingment must be implemented by modifying/expanding these template classes. Additional classes may be created to implement some of the functionalities described below; however such classes must be outside the Obj inheritance hierarchy. In appropriate subclasses of Obj, implement the function traverse( ) that performs, by recursion, depth-first traversal of the object graph starting from "this" object. The function will visit all and only the objects that can be reached from "this" object by chains of reference pointers. The Boolean value of visited field of every visited object will be updated to true. In this project only traverse( ) function will update the values of visited field. In the traversal process none of the previously visited objects will be visited.

In the main function of MainBSTGraph class, implement the following process. All data must be displayed in an output file.

Your output should display the required data in legible format. To make grading efficient and uniform, MainBSTGraph.main is to read the output file name as external argument, argv[0].

Output.java

Obj.java

Linked_List.java

EmptyList.java

NonEmptyList.java

BST.java

EmptyBST.java

NonEmptyBST.java

GraphNode.java

Data.java

PC.java

Smartphone.java

Laptop.java

Desktop.java

Car.java

Sedan.java

Coupe.java

Van.java

MainBSTGraph.java

Output ·Obi 5 Linked List?C extends Obi> EmptyL?SKC extends Obi> . NonEmptyLisKC extends Obi> o BS ?C extends Data> 8 . EmptyBST?C extends Data . NonEmptyBST?C extends Datax o GraphNode o Data . PC ·Smartphone . Lapto . Deskto . Car - Sedan - Coupe Van MainBST Graph

Explanation / Answer

Binary Tree : An information structure in which we have hubs containing information and two references to different hubs, one on the left and one on the right.

Double Tree comprise of Nodes

Hubs are only protests of a class and every hub has information and a connection to one side hub and right hub.

Generally we call the beginning hub of a tree as root.

public class BST {
   public static Node root;
   public BST(){
       this.root = null;
   }
  
   public boolean find(int id){
       Node current = root;
       while(current!=null){
           if(current.data==id){
               return true;
           }else if(current.data>id){
               current = current.l;
           }else{
               current = current.r;
           }
       }
       return false;
   }
   public boolean delete(int id){
       Node parent = root;
       Node current = root;
       boolean isLeftChild = false;
       while(current.data!=id){
           parent = current;
           if(current.data>id){
               isLeftChild = true;
               current = current.l;
           }else{
               isLeftChild = false;
               current = current.r;
           }
           if(current ==null){
               return false;
           }
       }
        if(current.l==null && current.r==null){
           if(current==root){
               root = null;
           }
           if(isLeftChild ==true){
               parent.l = null;
           }else{
               parent.r = null;
           }
       }
        else if(current.r==null){
           if(current==root){
               root = current.l;
           }else if(isLeftChild){
               parent.l = current.l;
           }else{
               parent.r = current.l;
           }
       }
       else if(current.l==null){
           if(current==root){
               root = current.r;
           }else if(isLeftChild){
               parent.l = current.r;
           }else{
               parent.r = current.r;
           }
       }else if(current.l!=null && current.r!=null){
          
            Node successor   = getSuccessor(current);
           if(current==root){
               root = successor;
           }else if(isLeftChild){
               parent.l = successor;
           }else{
               parent.r = successor;
           }          
           successor.l = current.l;
       }      
       return true;      
   }
  
   public Node getSuccessor(Node deleleNode){
       Node successsor =null;
       Node successsorParent =null;
       Node current = deleleNode.r;
       while(current!=null){
           successsorParent = successsor;
           successsor = current;
           current = current.l;
       }
       if(successsor!=deleleNode.r){
           successsorParent.l = successsor.r;
           successsor.r = deleleNode.r;
       }
       return successsor;
   }
   public void insert(int id){
       Node newNode = new Node(id);
       if(root==null){
           root = newNode;
           return;
       }
       Node current = root;
       Node parent = null;
       while(true){
           parent = current;
           if(id<current.data){              
               current = current.l;
               if(current==null){
                   parent.l = newNode;
                   return;
               }
           }else{
               current = current.r;
               if(current==null){
                   parent.r = newNode;
                   return;
               }
           }
       }
   }
   public void display(Node root){
       if(root!=null){
           display(root.l);
           System.out.print(" " + root.data);
           display(root.r);
       }
   }
   public static void main(String arg[]){
       BST b = new BST();
       b.insert(3);b.insert(8);
       b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
       b.insert(20);b.insert(25);b.insert(15);b.insert(16);
       System.out.println("Original Tree : ");
       b.display(b.root);      
       System.out.println("");
       System.out.println("Check whether Node with value 4 exists : " + b.find(4));
       System.out.println("Delete Node with no children (2) : " + b.delete(2));      
       b.display(root);
       System.out.println(" Delete Node with one child (4) : " + b.delete(4));      
       b.display(root);
       System.out.println(" Delete Node with Two children (10) : " + b.delete(10));      
       b.display(root);
   }
}

class Node{
   int data;
   Node l;
   Node r;  
   public Node(int data){
       this.data = data;
       l = null;
       r = null;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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