Urgent Help Please: This programming project is really just a big lab activity.

Question

Urgent Help Please:

This programming project is really just a big lab activity. You have to implement the BinarySearchTree class for a static set of integers. ("Static set" means that it doesn't change...so there is no insertion or removal functionality. So, this is basically just the binary search tree class we've been working with in the lectures.) To accomplish this you'll need to implement traversal functions, a Queue class template, and some other stuff. The enemy will provide a tester program to torture test your BinarySearchTree.h class file.

The lab will be open a lot during finals week. Keep an eye on the course webpage for a schedule..I'll post it as soon as I have it.

Getting started

Here is the basic BinarySearchTree definition:  BinarySearchTree.h

Here is a tester program for the BinarySearchTree class:  bsttester2.cpp.

Grab both of these codes and start hacking!

The tester program instantiates a BinarySearchTree object named bst. It is built from a sorted array of integers by the two-parameter constructor. The tester program will then exercise the printing traversals, as a first step. A second step comes when you've got the contains() function working.

The first thing you need to do is to get the constructor(s) working correctly. The tester program checks is isEmpty() and the size() function as the first thing it does.

After your constructor has built the search tree from the array you will want to look at it to see that it's constructed properly. This means you'll need to build the printing traversal functions. I've commented them out so that you can add them one at a time as you go along. The easy ones are the recursive ones. The most informative one is the non-recursive level-order traversal. You need all of them but start with the in-order traversal since it gives you a chance to identify some of the more likely (and major) problems early. (Remember that an in-order traversal of a binary search tree will encounter the data in sorted order..the array was sorted when it went into the constructor, so if you don't see sorted order when printed in-order you'll know there's a problem.)

For the level-order printing traversal you will need the Queue and Node class templates from Lab 15. It's a good thing you've got them finished already!

I have included two "enhanced" printing traversals that give additional structural information about the tree. Here is the output from all of the printing traversals on the small 5- element tree

Once you get the printing traversals to work correctly and can verify that your tree builds correctly, uncomment and implement the contains() function.

Testing contains()

The tester program doesn't immediately test the contains() function. In order to get that to happen, uncomment all of the commented out lines of the tester program. This will make it display a menu which lets you view the tree via the printing traversals and run contains() for user-specified inputs.

You'll know when you've got everything working correctly. Hopefully that happens quickly for you so you can be done with the project early!

Size 5 is Empty and size are consistant Preorder: 60 39 12 In order: 0 3 6 9 12 Enhanced inorder: Left NULL Right Left NULL Right NULL Left Right 9 Left NULL Right 12 12 Left NULL Right NULL Post Order: 30 12 96 Level Order 6 09 33 12 Enhanced level order: left right 9 left: NULL right 3 left: NULL right 12 left: NULL right NULL 12 left: NULL right NULL

Explanation / Answer

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(current.left==null && current.right==null){
           if(current==root){
               root = null;
           }
           if(isLeftChild ==true){
               parent.left = null;
           }else{
               parent.right = null;
           }
       }
       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){
           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 display(Node root){
       if(root!=null){
           display(root.left);
           System.out.print(" " + root.data);
           display(root.right);
       }
   }
   public static void main(String arg[]){
       BinarySearchTree b = new BinarySearchTree();
       b.insert(3);b.insert(8);
       b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(15);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 (4) : " + b.delete(4));      
       b.display(root);
       System.out.println(" Delete Node with one child (8) : " + b.delete(8));      
       b.display(root);
       System.out.println(" Delete Node with Two children (15) : " + b.delete(15));      
       b.display(root);
   }
}
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 U
• Subjects

---

---

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