BinaryTree1

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

/*

*/ /** * 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

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 */

/*

*/ /** * 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) */

/*

*/ /** * 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 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; } } /**/

BinarySearchTreeTest

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

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 the class BinarySearchTree: depthOfMinValueRecursive): returns the depth of the node in the calling BST which contains the minimum value. Use recursion. depthOfMinValuelterative(): returns the depth of the node in the calling BST which contains the minimum value. Do not use recursion. equalStruct(BinarySearchTree bst2): Check if the calling BST and the bst2 have the same structure. Test your methods in another class BinarySearchTreeTest that uses the class BinarySearchTree and completes a number of operations on a single BinarySearchTree objects and multiple BinarySearchTree objects. 3. 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. Major Steps Understand the related classes I gave you in previous lectures (Lec#17, Lec#18). i. BinaryTree1.java, BinarySearchTree.java, SearchTree.java, ReadBinaryTree1.java, BinarySearchTreeTest.java Revise the class BinarySearchTree. Add necessary methods. At one method at a time. Test it in BinarySearchTreeTest