---BinaryTree1---

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

public class BinaryTree1 implements Serializable {

protected static class Node implements Serializable {

public E data; public Node left; public Node right;

public Node(E data) { this.data = data; left = null; right = null; }

@Override public String toString() { return data.toString(); } } protected Node root;

public BinaryTree1() { root = null; } protected BinaryTree1(Node root) { this.root = root; }

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

public BinaryTree1 getLeftSubtree() { if (root != null && root.left != null) { return new BinaryTree1(root.left); }

else { return null; } }

public BinaryTree1 getRightSubtree() { if (root != null && root.right != null) { return new BinaryTree1(root.right); }

else { return null; } }

public E getData() { if (root != null) { return root.data; } else { return null; } }

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

private void preOrderTraverse(Node node, int depth, StringBuilder sb) { for (int i = 1; i

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;

public class BinarySearchTree> extends BinaryTree1 implements SearchTree { @Override public E find(E target) { return find(root, target); }

private E find(Node localRoot, E target) { if (localRoot == null) { return null; }

int compResult = target.compareTo(localRoot.data); if (compResult == 0) { return localRoot.data; } else if (compResult

private Node add(Node localRoot, E item) { if (localRoot == null) { 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)

private Node delete(Node localRoot, E item) { if (localRoot == null) { // item is not in the tree. deleteReturn = null; return localRoot; }

int compResult = item.compareTo(localRoot.data); if (compResult 0) { /localRoot.right = delete(localRoot.right, item); return localRoot; } else { deleteReturn = localRoot.data; if (localRoot.left == null) { return localRoot.right; } else if (localRoot.right == null) { return localRoot.left; } else { if (localRoot.left.right == null) { localRoot.data = localRoot.left.data; localRoot.left = localRoot.left.left; return localRoot; } else { localRoot.data = findLargestChild(localRoot.left); return localRoot; } } } } private E findLargestChild(Node parent) { if (parent.right.right == null) { E returnValue = parent.right.data; parent.right = parent.right.left; return returnValue; } else { return findLargestChild(parent.right); } } public boolean contains(E target) { return false; } public boolean remove(E target) { return false; } }

-----BinaryTreeTest----

public class BinarySearchTreeTest { public static void main(String[] args) { 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("---------------------"); } System.out.println("**************"); System.out.println("Inorder traversal of names tree: "); //To be implemented by students in class BinarySearchTree //System.out.println(bstNames.inorderToString()); } }

CIS2168 005-006 Assignment 5 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 BinaryTreel 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 '1n 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 n'. 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 charactern'. 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