Binary Search Tree

Overview

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

Add the following member methods to the class BinarySearchTree :

depthOfMinValue Recursive () : returns the depth of the node in the calling BST which contains the minimum value. Use recursion.

depthOfMinValue Iterative ()):: returns the depth of the node in the calling BST which contains the minimum value. Do not use recursion.

equal Struct (BinarySearchTree bst2): Check if the calling BST and the bst2 have the same structure.

Test your methods in another class BinarySearchTree Test that uses the class BinarySearchTree and completes a number of operations on a single BinarySearchTree object and multiple BinarySearchTree objects.

implementation Requirements

You must use the classes provided to you.

This requirement means that you cannot use Java API class for Binary Search Tree.

You must implement the required methods as stated in the BinarySearchTree class.

package bst4stu; /**/ import java.io.BufferedReader; import java.io.IOException; import java.io.Serializable; import java.util.Scanner; /** * Class for a binary tree that stores type E objects. * @author Koffman and Wolfgang **/ 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; //don't have to include this branch } if (rightTree != null) { root.right = rightTree.root; } else { root.right = null; //don't have to include this branch } } /** * 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); } } /**/ } /**/ 

/* The parent class of BinarySearchTree is the BinaryTree1 class * that was covered in Lec#17 and Lec#18. * The interface SearchTree implemented by BinarySearchTree was * also covered in Lec#17. * Both files SearchTree.java and BinaryTree1.java are included in the folder here. */ package bst4stu; /**/ 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; } } /**/ 

/** Test the basic implementation of BinarySearchTree. * It creates an empty binary search tree of Strings, insert 5 strings in array names, * print the BST tree data and structure before, after, and during insertion. */ package bst4stu; /** * @author cindy */ 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()); } }