Programming: 1. For each method, give the pre and post conditions and invariant,

Question

Programming:
1.   For each method, give the pre and post conditions and invariant, if any - 10%
2.   Program execution according to the requirements given 50%
3.   Naming of program as required 5%
Description of Program
You are to write a program name BSTree.java that will:
1.   Generate 100 random integer numbers ranging from 1 – 99.
2.   Store these numbers in a data structure of your choice and display the data on the screen. DO NOT SORT THIS DATA STRUCTURE.
3.   Now build a Binary Search Tree using this set of numbers. You MUST insert the values into the tree starting from the first element of your Data Structure and go sequentially.
4.   After building the tree, use an infix recursive method to display the data on the screen.
5.   To build the Binary Search Tree, you must create your own Linked List.

Explanation / Answer

package BSTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class BSTree {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<Integer>();

       // generate random numbers and add to list
       Random randomGenerator = new Random();
       for (int idx = 1; idx <= 100; ++idx) {
           int randomInt = randomGenerator.nextInt(100);
           list.add(randomInt);
       }

       // print the elements in list without any sorting
       for (int i = 0; i < list.size(); i++) {
           System.out.println(list.get(i) + " ");
       }

       // create binary search tree
       BinarySearchTree bst = new BinarySearchTree();

       // add elements to BST
       for (int i = 0; i < list.size(); i++) {
           bst.insert(list.get(i));
       }

       // print the BST in INORDER
       bst.inOrder(bst.root);

   }
}

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);
       }
   }

}

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

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

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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