The language is JAVA Complete TestBinarySearchTree program to test the following

Question

The language is JAVA

Complete TestBinarySearchTree program to test the following methods. you must thoroughly test these methods with multiple different BinarySearchTrees!!!!!

search

insert

delete

inorder

preorder

postorder

path

leftSubTree

rightSubTree

getNumberOfLeaves

sameTree

import java.util.*;
import java.io.*;
public class TestBinarySearchTree {   
public static void main(String[] args) {
Integer[] num = {67, 87, 55, 43, 48, 73, 91, 39, 59, 92, 34, 95, 81, 66,
40, 53, 84, 77};
// Create an empty BinaryTree
BinarySearchTree<Integer> tree = new BinarySearchTree<>(num);
Scanner input = new Scanner(System.in);   
System.out.println(" Enter an element to search");   
System.out.println(" Enter an element to delete");   
Integer key = input.nextInt();   
}
}

Explanation / Answer

BinarySearchTree.java

public class BinarySearchTree {
   public static Node root;
   static int max_level = 0;

   public BinarySearchTree() {
       this.root = null;
   }

   public BinarySearchTree(Integer[] num) {
       this.root = null;
       for (int i = 0; i < num.length; i++) {
           insert(num[i]);
       }
   }

   public boolean search(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 node 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;
           }
       }
       // if node 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) {

           // minimum element in 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;
       }
       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;
               }
           }
       }
   }

   public void inOrder(Node root) {
       if (root != null) {
           inOrder(root.left);
           System.out.print(" " + root.data);
           inOrder(root.right);
       }
   }

   public void preOrder(Node root) {
       if (root != null) {
           System.out.print(" " + root.data);
           preOrder(root.left);
           preOrder(root.right);
       }
   }

   public void postOrder(Node root) {
       if (root != null) {
           preOrder(root.left);
           preOrder(root.right);
           System.out.print(" " + root.data);
       }
   }

   public void leftSubTree(Node node) {
       if (node != null) {
           inOrder(node.left);
           System.out.print(" " + node.data);
       }
   }
  
   int getLeafCount(Node node)
{
if (node == null)
return 0;
if (node.left == null && node.right == null)
return 1;
else
return getLeafCount(node.left) + getLeafCount(node.right);
}

   public void rightSubTree(Node node) {

       if (node != null) {
           // inOrder(root.left);
           System.out.print(" " + node.data);
           inOrder(node.right);
       }

       /*
       * if (node == null) return;
       *
       * if (max_level < level) { System.out.print(" " + node.data); max_level
       * = level; }
       *
       * rightSubTree(node.right, level + 1); rightSubTree(node.left, level +
       * 1);
       */
   }

}

class Node {
   int data;
   Node left;
   Node right;

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

---------------------------------------------------

TestBinarySearchTree.java

import java.util.Scanner;

public class TestBinarySearchTree {
   public static void main(String[] args) {
       Integer[] num = { 67, 87, 55, 43, 48, 73, 91, 39, 59, 92, 34, 95, 81,
               66, 40, 53, 84, 77 };
       BinarySearchTree tree = new BinarySearchTree();
       for (int i = 0; i < num.length; i++) {
           tree.insert(num[i]);
       }
       tree.inOrder(tree.root);
       Scanner input = new Scanner(System.in);
       System.out.println(" Enter an element to search");
       int n = input.nextInt();
       if (tree.search(n))
           System.out.println("Element is present in tree");
       else
           System.out.println("Element is present in tree");

       System.out.println(" Enter an element to delete");
       n = input.nextInt();
       tree.delete(n);
       System.out.println(" in order: ");
       tree.inOrder(tree.root);
       System.out.println(" pre order: ");
       tree.inOrder(tree.root);
       System.out.println(" post order: ");
       tree.inOrder(tree.root);
       System.out.println(" leftSubTree: ");
       tree.leftSubTree(tree.root);
       System.out.println(" rightSubTree: ");
       BinarySearchTree.max_level = 0;
       tree.rightSubTree(tree.root);
       System.out.println(" count : "+tree.getLeafCount(tree.root));
   }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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