Binary Search Tree

1. Objectives This assignment will help you to:

• Learn how to program using data structure Binary SearchTree

• Understand how Binary Search Tree works

• Enhance your skills in programming using linked lists

2. Overview

You are given the classes BinaryTree1.java,BinarySearchTree.java, and BinarySearchTreeTest.java.

Add the following member methods to BinaryTree1:

• depth: this method will return the depth of the callingBinaryTree1 object.

• size: this method will return the number of data items storedin the calling BinaryTree1 object.

Add the following member methods to the classBinarySearchTree:

• preOrderTraversal(): returns the preorder traversal string ofall items stored in the calling BinarySearchTree object. Mustseparate each two adjacent values by 2 spaces, not by newlinecharacter ‘’.

• inOrderTraversal(): returns the inorder traversal string ofall items stored in the calling BinarySearchTree object. Mustseparate each two adjacent values by 2 spaces, not by newlinecharacter ‘’.

• postOrderTraversal(): returns the postorder traversal stringof all items stored in the calling BinarySearchTree object. Mustseparate each two adjacent values by 2 spaces, not by newlinecharacter ‘’.

• copy: copy each item in a given BinarySearchTree object to thecalling BinarySearchTree object. Each item in the givenBinearySearchTree object has to be added to the callingBinarySearchTree object.

• equals: check if both the structure and the content of a givenBinarySearchTree object is exactly the same as the callingBinarySearchTree object.

• delete2: delete a given data item from the callingBinarySearchTree object. Must use the leftmost node data in theright subtree of the deleted node to replace the deleted item. Thatis to use the inorder-traversal successor of the deleted node toreplace the item in the deleted node.

You must also write another class BinarySearchTreeTest that usesthe class BinarySearchTree and completes a number of operations ona single BinarySearchTree objects and multiple BinarySearchTreeobjects. More specifically your BinarySearchTreeTest will createthree BST collections of random integers. Use the first collectionto test the implementation of all required methods except copy andequals. Then use the first and the second collections to testequals. Then use the second and the third to test copy.

3. Implementation Requirements

• You must use the given classes BinaryTree1 andBinarySearchTree.

• This requirement means that you cannot use Java API classesrelated to Binary Search Tree.

• You cannot add new data fields into the given classesBinaryTree1 and BinarySearchTree.

• You must use recursion to implement all methods except methodcopy. Each of these methods must have a public wrapper method and aprivate recursive counterpart method. For example, for method size,there is a public method size and a private recursive counterpartmethod size. Please refer to how methods find, add are implementedin BinarySearchTree class.

• You must write each method except method copy from scratch. Itmeans that each of such methods cannot call the other methods thatare already implemented in the given classes BinaryTree1 andBinarySearchTree.

• Your class BinarySearchTreeTest must create 3 different BSTcollections of random integers.

4. Detailed Hints

• Add to class BinaryTree1 the following public wrapper methodsfor the corresponding private recursive methods

o public int size()

o public int depth()

• Add to class BinarySearchTree the following public wrappermethods for the corresponding private recursive methods

o public boolean equals(BinarySearchTreebst2)

o public void copy(BinarySearchTreebst2)

o public String preOrderTraversal()

? returns a string inthis format: "45 27 15 21 36"

o public String inOrderTraversal()

? returns a string inthe same format as preOrderTraversal o public StringpostOrderTraversal()

? returns a string inthe same format as preOrderTraversal

o public E delete2(E item2Delete)

? use the smallest inthe right subtree to replace the deleted item

5. Major Steps

• Understand the related classes I gave you in the lectures(Lec#17, Lec#18).

i. BinaryTree1.java,BinarySearchTree.java, SearchTree.java, ReadBinaryTree1.java,BinarySearchTreeTest.java

• Revise the class BinarySearchTree. Add necessary methods. Addone method at a time. Test it in BinarySearchTreeTest.

---BinaryTree1---

/*

*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.Serializable;
import java.util.Scanner;

public class BinaryTree1 implements Serializable {

/*

*/
/** Class to encapsulate a tree node. */
protected static class Node implementsSerializable {
// Data Fields

/** The information stored in thisnode. */
public E data;
/** Reference to the left child.*/
public Node left;
/** Reference to the right child.*/
public Node right;

// Constructors
/**
* Construct a node with givendata and no children.
* @param data The data to storein this node
*/
public Node(E data) {
this.data = data;
left = null;
right = null;
}

// Methods
/**
* Returns a string representationof the node.
* @return A string representationof the data fields
*/
@Override
public String toString() {
returndata.toString();
}
}
/*

*/
// Data Field
/** The root of the binary tree */
protected Node root;

/** Construct an empty BinaryTree1 */
public BinaryTree1() {
root = null;
}

/**
* Construct a BinaryTree1 with a specifiedroot.
* Should only be used by subclasses.
* @param root The node that is the root of thetree.
*/
protected BinaryTree1(Node root) {
this.root = root;
}

/**
* Constructs a new binary tree with data in itsroot,leftTree
* as its left subtree and rightTree as itsright subtree.
*/
public BinaryTree1(E data, BinaryTree1leftTree,
BinaryTree1rightTree) {
root = new Node(data);
if (leftTree != null) {
root.left =leftTree.root;
} else {
root.left = null;
}
if (rightTree != null) {
root.right =rightTree.root;
} else {
root.right = null;
}
}

/**
* Return the left subtree.
* @return The left subtree or null if eitherthe root or
* the left subtree is null
*/
public BinaryTree1 getLeftSubtree() {
if (root != null && root.left!= null) {
return newBinaryTree1(root.left);
} else {
return null;
}
}

/**
* Return the right sub-tree
* @return the right sub-tree or
* null ifeither the root or the
* rightsubtree is null.
*/
public BinaryTree1 getRightSubtree() {
if (root != null && root.right!= null) {
return newBinaryTree1(root.right);
} else {
return null;
}
}

/**
* Return the data field of the root
* @return the data field of the root
* or null ifthe root is null
*/
public E getData() {
if (root != null) {
return root.data;
} else {
return null;
}
}

/**
* Determine whether this tree is a leaf.
* @return true if the root has nochildren
*/
public boolean isLeaf() {
return (root == null || (root.left ==null && root.right == null));
}

@Override
public String toString() {
StringBuilder sb = newStringBuilder();
preOrderTraverse(root, 1, sb);
return sb.toString();
}

/**
* Perform a preorder traversal.
* @param node The local root
* @param depth The depth
* @param sb The string buffer to save theoutput
*/
private void preOrderTraverse(Node node, intdepth,
StringBuilder sb) {
for (int i = 1; i < depth; i++){
sb.append(" ");
}
if (node == null) {
sb.append("null");
} else {
sb.append(node.toString());
sb.append("");
preOrderTraverse(node.left, depth + 1, sb);
preOrderTraverse(node.right, depth + 1, sb);
}
}

/*

*/
/**
* Method to read a binary tree.
* @pre The input consists of a preordertraversal
* of the binary tree. Theline "null" indicates a null tree.
* @param scan the Scanner attached to the inputfile
* @return The binary tree
*/
public static BinaryTree1readBinaryTree1(Scanner scan) {
// Read a line and trim leading andtrailing spaces.
String data = scan.next();
if (data.equals("null")) {
return null;
} else {
BinaryTree1leftTree = readBinaryTree1(scan);
BinaryTree1rightTree = readBinaryTree1(scan);
return newBinaryTree1(data, leftTree, rightTree);
}
}
/**/
}
/**/

---BinarySearchTree---

import java.util.List;

import java.util.ArrayList;

/**
* A class to represent a binary search tree.
* @author Koffman and Wolfgang
*/
public class BinarySearchTree>
extendsBinaryTree1
implements SearchTree {
// Data Fields

/** Return value from the public add method.*/
protected boolean addReturn;
/** Return value from the public delete method.*/
protected E deleteReturn;

//Methods
/*

*/
/**
* Starter method find.
* @pre The target object must implement
* the Comparableinterface.
* @param target The Comparable object beingsought
* @return The object, if found, otherwisenull
*/
@Override
public E find(E target) {
return find(root, target);
}

/**
* Recursive find method.
* @param localRoot The local subtree?sroot
* @param target The object being sought
* @return The object, if found, otherwisenull
*/
private E find(Node localRoot, E target){
if (localRoot == null) {
return null;
}

// Compare the target with the datafield at the root.
int compResult =target.compareTo(localRoot.data);
if (compResult == 0) {
returnlocalRoot.data;
} else if (compResult < 0) {
returnfind(localRoot.left, target);
} else {
returnfind(localRoot.right, target);
}
}
/*

*/

/*

*/
/**
* Starter method add.
* @pre The object to insert must implementthe
* Comparableinterface.
* @param item The object being inserted
* @return true if the object is inserted,false
* if theobject already exists in the tree
*/
@Override
public boolean add(E item) {
root = add(root, item);
return addReturn;
}

/**
* Recursive add method.
* @post The data field addReturn is set true ifthe item is added to
* the tree, false ifthe item is already in the tree.
* @param localRoot The local root of thesubtree
* @param item The object to be inserted
* @return The new local root that now containsthe
* inserteditem
*/
private Node add(Node localRoot, Eitem) {
if (localRoot == null) {
// item is not in thetree ? insert it.
addReturn = true;
return newNode(item);
} else if(item.compareTo(localRoot.data) == 0) {
// item is equal tolocalRoot.data
addReturn = false;
return localRoot;
} else if(item.compareTo(localRoot.data) < 0) {
// item is less thanlocalRoot.data
localRoot.left =add(localRoot.left, item);
return localRoot;
} else {
// item is greater thanlocalRoot.data
localRoot.right =add(localRoot.right, item);
return localRoot;
}
}
/*

*/

/*

*/
/**
* Starter method delete.
* @post The object is not in the tree.
* @param target The object to be deleted
* @return The object deleted from thetree
* or null ifthe object was not in the tree
* @throws ClassCastException if target does notimplement
* Comparable
*/
public E delete(E target) {
root = delete(root, target);
return deleteReturn;
}

/**
* Recursive delete method.
* @post The item is not in the tree;
* deleteReturn isequal to the deleted item
* as it was stored inthe tree or null
* if the item was notfound.
* @param localRoot The root of the currentsubtree
* @param item The item to be deleted
* @return The modified local root that does notcontain
* theitem
*/
private Node delete(Node localRoot,E item) {
if (localRoot == null) {
// item is not in thetree.
deleteReturn =null;
return localRoot;
}

// Search for item to delete.
int compResult =item.compareTo(localRoot.data);
if (compResult < 0) {
// item is smaller thanlocalRoot.data.
localRoot.left =delete(localRoot.left, item);
return localRoot;
} else if (compResult > 0) {
// item is larger thanlocalRoot.data.
localRoot.right =delete(localRoot.right, item);
return localRoot;
} else {
// item is at localroot.
deleteReturn =localRoot.data;
if (localRoot.left ==null) {
// If thereis no left child, return right child
// whichcan also be null.
returnlocalRoot.right;
} else if(localRoot.right == null) {
// If thereis no right child, return left child.
returnlocalRoot.left;
} else {
// Nodebeing deleted has 2 children, replace the data
// withinorder predecessor.
if(localRoot.left.right == null) {
// The left child has no right child.
// Replace the data with the data in the
// left child.
localRoot.data = localRoot.left.data;
// Replace the left child with its left child.
localRoot.left = localRoot.left.left;
return localRoot;
} else{
// Search for the inorder predecessor (ip) and
// replace deleted node's data with ip.
localRoot.data = findLargestChild(localRoot.left);
return localRoot;
}
}
}
}
/*

*/

/*

*/
/**
* Find the node that is the
* inorder predecessor and replace it
* with its left child (if any).
* @post The inorder predecessor is removed fromthe tree.
* @param parent The parent of possibleinorder
* predecessor(ip)
* @return The data in the ip
*/
private E findLargestChild(Node parent){
// If the right child has no rightchild, it is
// the inorder predecessor.
if (parent.right.right == null) {
E returnValue =parent.right.data;
parent.right =parent.right.left;
return returnValue;
} else {
returnfindLargestChild(parent.right);
}
}
/**/


/** To be implemented by Students.
* Determine if an item is in the tree
* @param target Item being sought in tree
* @return true If the item is in the tree,false otherwise
*/
public boolean contains(E target) {
return false;
}

/** To be implemented by Students.
* Removes target from tree.
* @param target Item to be removed
* @return true if the object was in the tree,false otherwise
* @post target is not in the tree
*/
public boolean remove(E target) {
return false;
}
}
/**/

-----BinaryTreeTest----

public class BinarySearchTreeTest {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
//create a binary search tree
BinarySearchTree bstNames= new BinarySearchTree();
String[] names = {"house", "kiss","dog", "cat", "man" };
System.out.println(bstNames.toString());
System.out.println("---------------------");
for (int i = 0; i < 5; i++) {
bstNames.add(names[i]);
System.out.println("Afteradding " + names[i] + "==>");
System.out.println(bstNames.toString());
System.out.println("---------------------");
}

//verify the BST structure usinginorder traversal
System.out.println("**************");
System.out.println("Inorder traversalof names tree: ");
//To be implemented by students inclass BinarySearchTree
//System.out.println(bstNames.inorderToString());

}

}