Binary Search Tree

1. Objectives This assignment will help you to:

Learn how to program using data structure Binary Search Tree

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 calling BinaryTree1 object.

size: this method will return the number of data items stored in the calling BinaryTree1 object.

Add the following member methods to the class BinarySearchTree:

preOrderTraversal(): returns the preorder traversal string of all items stored in the calling BinarySearchTree object. Must separate each two adjacent values by 2 spaces, not by newline character .

inOrderTraversal(): returns the inorder traversal string of all items stored in the calling BinarySearchTree object. Must separate each two adjacent values by 2 spaces, not by newline character .

postOrderTraversal(): returns the postorder traversal string of all items stored in the calling BinarySearchTree object. Must separate each two adjacent values by 2 spaces, not by newline character .

copy: copy each item in a given BinarySearchTree object to the calling BinarySearchTree object. Each item in the given BinearySearchTree object has to be added to the calling BinarySearchTree object.

equals: check if both the structure and the content of a given BinarySearchTree object is exactly the same as the calling BinarySearchTree object.

delete2: delete a given data item from the calling BinarySearchTree object. Must use the leftmost node data in the right subtree of the deleted node to replace the deleted item. That is to use the inorder-traversal successor of the deleted node to replace the item in the deleted node.

You must also write another class BinarySearchTreeTest that uses the class BinarySearchTree and completes a number of operations on a single BinarySearchTree objects and multiple BinarySearchTree objects. More specifically your BinarySearchTreeTest will create three BST collections of random integers. Use the first collection to test the implementation of all required methods except copy and equals. Then use the first and the second collections to test equals. Then use the second and the third to test copy.

3. Implementation Requirements

You must use the given classes BinaryTree1 and BinarySearchTree.

This requirement means that you cannot use Java API classes related to Binary Search Tree.

You cannot add new data fields into the given classes BinaryTree1 and BinarySearchTree.

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

You must write each method except method copy from scratch. It means that each of such methods cannot call the other methods that are already implemented in the given classes BinaryTree1 and BinarySearchTree.

Your class BinarySearchTreeTest must create 3 different BST collections of random integers.

4. Detailed Hints

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

public int size()

public int depth()

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

public boolean equals(BinarySearchTree bst2)

public void copy(BinarySearchTree bst2)

public String preOrderTraversal()

returns a string in this format: "45 27 15 21 36"

public String inOrderTraversal()

returns a string in the same format as preOrderTraversal

public String postOrderTraversal()

returns a string in the same format as preOrderTraversal

public E delete2(E item2Delete)

use the smallest in the right subtree to replace the deleted item

---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 implements Serializable { // Data Fields

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

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

// Methods /** * Returns a string representation of the node. * @return A string representation of the data fields */ @Override public String toString() { return data.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 specified root. * Should only be used by subclasses. * @param root The node that is the root of the tree. */ protected BinaryTree1(Node root) { this.root = root; }

/** * Constructs a new binary tree with data in its root,leftTree * as its left subtree and rightTree as its right subtree. */ public BinaryTree1(E data, BinaryTree1 leftTree, BinaryTree1 rightTree) { 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 either the root or * the left subtree is null */ public BinaryTree1 getLeftSubtree() { if (root != null && root.left != null) { return new BinaryTree1(root.left); } else { return null; } }

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

/** * Return the data field of the root * @return the data field of the root * or null if the 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 no children */ public boolean isLeaf() { return (root == null || (root.left == null && root.right == null)); }

@Override public String toString() { StringBuilder sb = new StringBuilder(); 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 the output */ private void preOrderTraverse(Node node, int depth, 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 preorder traversal * of the binary tree. The line "null" indicates a null tree. * @param scan the Scanner attached to the input file * @return The binary tree */ public static BinaryTree1 readBinaryTree1(Scanner scan) { // Read a line and trim leading and trailing spaces. String data = scan.next(); if (data.equals("null")) { return null; } else { BinaryTree1 leftTree = readBinaryTree1(scan); BinaryTree1 rightTree = readBinaryTree1(scan); return new BinaryTree1(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> extends BinaryTree1 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 Comparable interface. * @param target The Comparable object being sought * @return The object, if found, otherwise null */ @Override public E find(E target) { return find(root, target); }

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

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

*/

/*

*/ /** * Starter method add. * @pre The object to insert must implement the * Comparable interface. * @param item The object being inserted * @return true if the object is inserted, false * if the object 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 if the item is added to * the tree, false if the item is already in the tree. * @param localRoot The local root of the subtree * @param item The object to be inserted * @return The new local root that now contains the * inserted item */ private Node add(Node localRoot, E item) { if (localRoot == null) { // item is not in the tree insert it. addReturn = true; return new Node(item); } else if (item.compareTo(localRoot.data) == 0) { // item is equal to localRoot.data addReturn = false; return localRoot; } else if (item.compareTo(localRoot.data) < 0) { // item is less than localRoot.data localRoot.left = add(localRoot.left, item); return localRoot; } else { // item is greater than localRoot.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 the tree * or null if the object was not in the tree * @throws ClassCastException if target does not implement * Comparable */ public E delete(E target) { root = delete(root, target); return deleteReturn; }

/** * Recursive delete method. * @post The item is not in the tree; * deleteReturn is equal to the deleted item * as it was stored in the tree or null * if the item was not found. * @param localRoot The root of the current subtree * @param item The item to be deleted * @return The modified local root that does not contain * the item */ private Node delete(Node localRoot, E item) { if (localRoot == null) { // item is not in the tree. deleteReturn = null; return localRoot; }

// Search for item to delete. int compResult = item.compareTo(localRoot.data); if (compResult < 0) { // item is smaller than localRoot.data. localRoot.left = delete(localRoot.left, item); return localRoot; } else if (compResult > 0) { // item is larger than localRoot.data. localRoot.right = delete(localRoot.right, item); return localRoot; } else { // item is at local root. deleteReturn = localRoot.data; if (localRoot.left == null) { // If there is no left child, return right child // which can also be null. return localRoot.right; } else if (localRoot.right == null) { // If there is no right child, return left child. return localRoot.left; } else { // Node being deleted has 2 children, replace the data // with inorder 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 from the tree. * @param parent The parent of possible inorder * predecessor (ip) * @return The data in the ip */ private E findLargestChild(Node parent) { // If the right child has no right child, it is // the inorder predecessor. if (parent.right.right == null) { E returnValue = parent.right.data; parent.right = parent.right.left; return returnValue; } else { return findLargestChild(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("After adding " + names[i] + "==> "); System.out.println(bstNames.toString()); System.out.println("---------------------"); } //verify the BST structure using inorder traversal System.out.println("**************"); System.out.println("Inorder traversal of names tree: "); //To be implemented by students in class BinarySearchTree //System.out.println(bstNames.inorderToString()); } }