Question

In: Computer Science

JAVA *** All data structures, including array operations, queues, stacks, linked lists, trees, etc need to...

JAVA

*** All data structures, including array operations, queues, stacks, linked lists, trees, etc need to be implemented by you.

Write a menu driven program that implements the following Binary Search Tree Operations

  • FIND (item)
  • INSERT (item)
  • DELETE (item)
  • DELETE_TREE (delete all nodes - be careful with the traversal!)

Solutions

Expert Solution

Binary Search Tree

Binary Search Tree, is a node-based binary tree data structure which has the following properties:

  • The left subtree of a node contains only nodes with keys lesser than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be a binary search tree.
    There must be no duplicate nodes.

CODE

public class BinarySearchTree {
   public static Node root;
   public BinarySearchTree(){
       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.left;
           }else{
               current = current.right;
           }
       }
       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.left;
           }else{
               isLeftChild = false;
               current = current.right;
           }
           if(current ==null){
               return false;
           }
       }
       //if i am here that means we have found the node
       //Case 1: if node to be deleted has no children
       if(current.left==null && current.right==null){
           if(current==root){
               root = null;
           }
           if(isLeftChild ==true){
               parent.left = null;
           }else{
               parent.right = null;
           }
       }
       //Case 2 : if node to be deleted has only one child
       else if(current.right==null){
           if(current==root){
               root = current.left;
           }else if(isLeftChild){
               parent.left = current.left;
           }else{
               parent.right = current.left;
           }
       }
       else if(current.left==null){
           if(current==root){
               root = current.right;
           }else if(isLeftChild){
               parent.left = current.right;
           }else{
               parent.right = current.right;
           }
       }else if(current.left!=null && current.right!=null){
          
           //now we have found the minimum element in the right sub tree
           Node successor   = getSuccessor(current);
           if(current==root){
               root = successor;
           }else if(isLeftChild){
               parent.left = successor;
           }else{
               parent.right = successor;
           }          
           successor.left = current.left;
       }      
       return true;      
   }
  
   public Node getSuccessor(Node deleleNode){
       Node successsor =null;
       Node successsorParent =null;
       Node current = deleleNode.right;
       while(current!=null){
           successsorParent = successsor;
           successsor = current;
           current = current.left;
       }
       //check if successor has the right child, it cannot have left child for sure
       // if it does have the right child, add it to the left of successorParent.
//       successsorParent
       if(successsor!=deleleNode.right){
           successsorParent.left = successsor.right;
           successsor.right = deleleNode.right;
       }
       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.left;
               if(current==null){
                   parent.left = newNode;
                   return;
               }
           }else{
               current = current.right;
               if(current==null){
                   parent.right = newNode;
                   return;
               }
           }
       }
   }
   // Function to display data
   public void display(Node root){
       if(root!=null){
           display(root.left);
           System.out.print("\n" + root.data);
           display(root.right);
       }
   }
  
  
  
  

// Function to delete tree
public Node deleteTree(Node root) {
if(null == root) {
return null;
}
root.left = deleteTree(root.left);
root.right = deleteTree(root.right);
root = null;
return root;
}

  
  
   public static void main(String arg[]){
       BinarySearchTree b = new BinarySearchTree();
      
       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("\n");
       //find function will return true or false
       System.out.println("Check whether Node with value 12 exists : " + b.find(12));
       System.out.println("Check whether Node with value 10 exists : " + b.find(10));
      
       //node deletion
       System.out.println("Delete Node with no children (2) : " + b.delete(2));      
       b.display(root);
       System.out.println("\n Delete Node with one child (4) : " + b.delete(4));      
       b.display(root);
       System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));      
       b.display(root);
  
   // tree deletion
       Node node = b.deleteTree(root);
if(null == node) {
System.out.println("\n Binary tree deleted successfully");
} else {
System.out.println("\n Error: Could not delete tree successfully");
}
  
  
   }
}

class Node{
   int data;
   Node left;
   Node right;  
   public Node(int data){
       this.data = data;
       left = null;
       right = null;
   }
}

THESE ARE THE SCREENSHOT OF CODE AND OUTPUT

I hope you will find it helpful.

Thanks for reading!

Have a wonderful day!


Related Solutions

Programming Project – Deques, Stacks & Queues General Description: Design and develop array based and linked...
Programming Project – Deques, Stacks & Queues General Description: Design and develop array based and linked list-based implementations for the Dequeue ADT. Your implementation must support generic data types using C++ templates. Develop Adapter Files to provide Stack and Queue functionality for the Deques. Definitions: You should implement the ADTs precisely as described in the following partial header files. Deque.h template class Deque { public:         Deque();                    //constructor         ~Deque();                 //destructor         void insertFront(const E& e);...
2.1 Linked Lists Linked lists are an example of an unbound data structure. Whereas the array...
2.1 Linked Lists Linked lists are an example of an unbound data structure. Whereas the array is based around having a fixed size per array creation, there is no logical limit on the ability of a linked list to grow. Physical limitations aside, linked lists are capable of growing largely without any limitations. To achieve this, they trade easier access to their individual elements. This is because linked lists have to be traversed from their root node to any node...
04 Prove : Homework - Data Structures Linked Lists Outcomes At the end of this study,...
04 Prove : Homework - Data Structures Linked Lists Outcomes At the end of this study, successful students will be able to: Articulate the strengths and weaknesses of Linked Lists. Use Linked Lists in Python to solve problems. Preparation Material Read the following sections from Wikipedia: Linked Lists: The Introduction Advantages Disadvantages Basic concepts and nomenclature The following subsections are sufficient: Intro Singly Linked Lists Doubly Linked Lists Tradeoffs The following subsections are sufficient: Linked Lists vs. Dynamic Arrays Data...
Data Structures on Java Basic Linked List exercises a. Suppose x is a linked-list node and...
Data Structures on Java Basic Linked List exercises a. Suppose x is a linked-list node and not the last node on the list. What is the effect of the following code fragment? x.next = x.next.next b. Singly Linked List has two private instance variables first and last as that point to the first and the last nodes in the list, respectively. Write a fragment of code that removes the last node in a linked list whose first node is first....
In this Java program you will implement your own doubly linked lists. Implement the following operations...
In this Java program you will implement your own doubly linked lists. Implement the following operations that Java7 LinkedLists have. 1. public DList() This creates the empty list 2. public void addFirst(String element) adds the element to the front of the list 3. public void addLast(String element) adds the element to the end of the list 4. public String getFirst() 5. public String getLast() 6. public String removeLast() removes & returns the last element of the list. 7. public String...
JAVA DATA STRUCTURE (Linked Lists/Queue) public class Node {    int value;    Node nextNode;   ...
JAVA DATA STRUCTURE (Linked Lists/Queue) public class Node {    int value;    Node nextNode;    Node(int v, Node n){        value = v;        nextNode = n;    }    Node (int v){        this(v,null);    } } public class Stack {    protected Node top;    Stack(){        top = null;    }    boolean isEmpty(){        return( top == null);    }    void push(int v){        Node tempPointer;       ...
The assignment: C++ program or Java You need to use the following programming constructs/data structures on...
The assignment: C++ program or Java You need to use the following programming constructs/data structures on this assignment. 1. A structure named student which contains:   a. int ID; student id; b. last name; // as either array of char or a string c. double GPA;    2. An input file containing the information of at least 10 students. 3. An array of struct: read the student information from the input file into the array. 4. A stack: you can use the...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT