---BinaryTree1--- import java.io.BufferedReader; import java.io.IOException; imp

Question

---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 < 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 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 < 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) {
// item is equal to localRoot.data

addReturn = false;
return localRoot;
} else if (item.compareTo(localRoot.data) < 0) {

localRoot.left = add(localRoot.left, item);
return localRoot;
} else {

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

int compResult = item.compareTo(localRoot.data);
if (compResult < 0) {
localRoot.left = delete(localRoot.left, item);
return localRoot;
} else 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 < 5; i++) {
bstNames.add(names[i]);
System.out.println("After adding " + names[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

Explanation / Answer

BinaryTree1.java:

import java.io.Serializable;

import java.util.Scanner;

public class BinaryTree1<E> implements Serializable {

protected static class Node<E> implements Serializable {

public E data;

public Node<E> left;

public Node<E> right;

public Node(E data) {

this.data = data;

left = null;

right = null;

}

@Override

public String toString() {

return data.toString();

}

}

protected Node<E> root;

public BinaryTree1() {

root = null;

}

protected BinaryTree1(Node<E> root) {

this.root = root;

}

public BinaryTree1(E data, BinaryTree1<E> leftTree, BinaryTree1<E> rightTree) {

root = new Node<E>(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<E> getLeftSubtree() {

if (root != null && root.left != null) {

return new BinaryTree1<E>(root.left);

} else {

return null;

}

}

public BinaryTree1<E> getRightSubtree() {

if (root != null && root.right != null) {

return new BinaryTree1<E>(root.right);

} else {

return null;

}

}

int getDepth() {

return getDepth(root);

}

int getDepth(Node<E> startNode) {

if(startNode.left == null && startNode.right == null) {

return 0;

}

int leftHeight = 0;

int rightHeight = 0;

if(startNode.left != null) {

leftHeight = getDepth(startNode.left);

}

if(startNode.right != null) {

rightHeight = getDepth(startNode.right);

}

if(leftHeight > rightHeight) {

return 1 + leftHeight;

} else {

return 1 + rightHeight;

}

}

public int getSize() {

return getSize(root);

}

public int getSize(Node<E> startNode) {

if(startNode.left == null && startNode.right == null) {

return 1;

}

int count = 1;

if(startNode.left != null) {

count += getSize(startNode.left);

}

if(startNode.right != null) {

count += getSize(startNode.right);

}

return count;

}

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<E> 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 BinaryTree1<String> readBinaryTree1(Scanner scan) {

// Read a line and trim leading and trailing spaces.

String data = scan.next();

if (data.equals("null")) {

return null;

} else {

BinaryTree1<String> leftTree = readBinaryTree1(scan);

BinaryTree1<String> rightTree = readBinaryTree1(scan);

return new BinaryTree1<String>(data, leftTree, rightTree);

}

}

}


BinarySearchTree.java:

public class BinarySearchTree<E extends Comparable<E>> extends BinaryTree1<E> {

private boolean addReturn;

private E deleteReturn;

public E find(E target) {

return find(root, target);

}

private E find(Node<E> 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);

}

}

public boolean add(E item) {

root = add(root, item);

return addReturn;

}

private Node<E> add(Node<E> localRoot, E item) {

if (localRoot == null) {

addReturn = true;

return new Node<E>(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) {

localRoot.left = add(localRoot.left, item);

return localRoot;

} else {

localRoot.right = add(localRoot.right, item);

return localRoot;

}

}

public E delete(E target) {

root = delete(root, target);

return deleteReturn;

}

private Node<E> delete(Node<E> 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.left = delete(localRoot.left, item);

return localRoot;

} else 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<E> parent) {

if (parent.right.right == null) {

E returnValue = parent.right.data;

parent.right = parent.right.left;

return returnValue;

} else {

return findLargestChild(parent.right);

}

}

public String preOrderTraversal() {

return preOrderTraversal(root);

}

public String preOrderTraversal(Node<E> parent) {

String s = parent.data.toString();

if(parent.left != null) {

s += " " + preOrderTraversal(parent.left);

}

if(parent.right != null) {

s += " " + preOrderTraversal(parent.right);

}

return s;

}

public String inOrderTraversal() {

return inOrderTraversal(root);

}

public String inOrderTraversal(Node<E> parent) {

String s = "";

if(parent.left != null) {

s += " " + preOrderTraversal(parent.left);

}

s += parent.data.toString();

if(parent.right != null) {

s += " " + preOrderTraversal(parent.right);

}

return s;

}

public String postOrderTraversal() {

return postOrderTraversal(root);

}

public String postOrderTraversal(Node<E> parent) {

String s = "";

if(parent.left != null) {

s += " " + preOrderTraversal(parent.left);

}

if(parent.right != null) {

s += " " + preOrderTraversal(parent.right);

}

s += parent.data.toString();

return s;

}

public void copy(BinarySearchTree<E> parent) {

copy(parent.root);

}

public void copy(Node<E> parent) {

add(parent.data);

if(parent.left != null) {

copy(parent.left);

}

if(parent.right != null) {

copy(parent.right);

}

}

public boolean equals(BinarySearchTree<E> parent) {

return equals(root, parent.root);

}

public boolean equals(Node<E> node1, Node<E> node2) {

if(node2 == null && node1 == null) {

return true;

}

if(node2 == null || node1 == null) {

return false;

}

if(node1.data.compareTo(node2.data) != 0) {

return false;

}

return equals(node1.left, node2.left) && equals(node1.right, node2.right);

}

public E delete2(E itemToDelete) {

return delete2(root, itemToDelete);

}

public E delete2(Node<E> localRoot, E itemToDelete) {

if (localRoot == null) {

// item is not in the tree.

return null;

}

int compResult = itemToDelete.compareTo(localRoot.data);

if (compResult < 0) {

localRoot.left = delete(localRoot.left, itemToDelete);

return localRoot.data;

} else if (compResult > 0) {

localRoot.right = delete(localRoot.right, itemToDelete);

return localRoot.data;

} else {

if (localRoot.left == null) {

return localRoot.right.data;

} else if (localRoot.right == null) {

return localRoot.left.data;

} else {

if (localRoot.right.left == null) {

localRoot.data = localRoot.right.data;

localRoot.left = localRoot.right.left;

return localRoot.data;

} else {

localRoot.data = findSmallestChild(localRoot.right);

return localRoot.data;

}

}

}

}

private E findSmallestChild(Node<E> parent) {

if (parent.left.left == null) {

E returnValue = parent.left.data;

parent.left = parent.left.right;

return returnValue;

} else {

return findSmallestChild(parent.left);

}

}

public boolean contains(E target) {

return false;

}

public boolean remove(E target) {

return false;

}

}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.