JAVA

How do I implement a SearchTree class to match my BinarySearchTree and BinaryTree Classes in JAVA:

BINARY SEARCH TREE

import java.util.List; import java.util.ArrayList;

public class BinarySearchTree > extends BinaryTree implements SearchTree {

protected boolean addReturn; protected E deleteReturn;

@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 < 0) { return find(localRoot.left, target); } else { return find(localRoot.right, target); } }

@Override public boolean add(E item) { root = add(root, item); return addReturn; }

private Node add(Node localRoot, E item) { if (localRoot == null) { addReturn = true; return new Node(item); } else if (item.compareTo(localRoot.data) == 0) { addReturn = false; return localRoot; } else if (item.compareTo(localRoot.data) < 0) { localRoot.left = add(localRoot.left, item); return localRoot; } else { // item is greater than localRoot.data localRoot.right = add(localRoot.right, item); return localRoot; } }

public E delete(E target) { root = delete(root, target); return deleteReturn; }

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

public boolean remove(E target) { return delete(target) != null; }

public boolean contains(E target) { return find(target) != null; }

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); } } public E deletePrime(E target) { root = deletePrime(root, target); return deleteReturn; } private Node deletePrime(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 = deletePrime(localRoot.left, item); return localRoot; } else if (compResult > 0) { // item is larger than localRoot.data. localRoot.right = deletePrime(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 successor. if (localRoot.right.left == null) { // The right child has no left child. // Replace the data with the data in the // right child. localRoot.data = localRoot.right.data; // Replace the right child with its right child. localRoot.right = localRoot.right.right; return localRoot; } else { // Search for the inorder successor (is) and // replace deleted node's data with is. localRoot.data = findSmallestChild(localRoot.right); return localRoot; } } } }

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

public List toList() { List result = new ArrayList(); toList(result, root); return result; }

private void toList(List result, Node node) { if (node == null) { return; } toList(result, node.left); result.add(node.data); toList(result, node.right); }

}

BINARY TREE CLASS:

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

public class BinaryTree 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 BinaryTree() { root = null; }

protected BinaryTree(Node root) { this.root = root; }

public BinaryTree(E data, BinaryTree leftTree, BinaryTree 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 BinaryTree getLeftSubtree() { if (root != null && root.left != null) { return new BinaryTree(root.left); } else { return null; } }

public BinaryTree getRightSubtree() { if (root != null && root.right != null) { return new BinaryTree(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 < 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); } }

public static BinaryTree readBinaryTree(BufferedReader bR) throws IOException { // Read a line and trim leading and trailing spaces. String data = bR.readLine().trim(); if (data.equals("null")) { return null; } else { BinaryTree leftTree = readBinaryTree(bR); BinaryTree rightTree = readBinaryTree(bR); return new BinaryTree(data, leftTree, rightTree); } }

public String preorderToString() { StringBuilder stb = new StringBuilder(); preorderToString(stb, root); return stb.toString(); }

private void preorderToString(StringBuilder stb, Node root) { stb.append(root); if (root.left != null) { stb.append(" "); preorderToString(stb, root.left); } if (root.right != null) { stb.append(" "); preorderToString(stb, root.right); } }

public String postorderToString() { StringBuilder stb = new StringBuilder(); postorderToString(stb, root); return stb.toString(); }

private void postorderToString(StringBuilder stb, Node root) { if (root.left != null) { postorderToString(stb, root.left); stb.append(" "); } if (root.right != null) { postorderToString(stb, root.right); stb.append(" "); } stb.append(root); }

public String inorderToString() { StringBuilder stb = new StringBuilder(); inorderToString(stb, root); return stb.toString(); }

private void inorderToString(StringBuilder stb, Node root) { if (root.left != null) { stb.append("("); inorderToString(stb, root.left); stb.append(") "); } stb.append(root); if (root.right != null) { stb.append(" ("); inorderToString(stb, root.right); stb.append(")"); } } }