Please use Java. Thank you. : Create and test a Binary Search Tree class that st
ID: 3903663 • Letter: P
Question
Please use Java. Thank you.
: Create and test a Binary Search Tree class that stores names in String format.
These are the classes you are going to create (and their IntTreeSearch equivalents in parentheses):
NameTreeNode (IntTreeNode): Stores data for the node, a String, and the left and right subtree nodes. Add a one-argument and three-argument constructor. NameTreeSearch (IntTreeSearch): Implement these methods:
public NameTreeSearch() {
}
public void add(String aName) {
}
private NameTreeNode add(NameTreeNode root, String aName) { // Hint: Think Comparable
}
public void print() { // Inorder traversal } private void print(NameTreeNode root) {
}
public void printSideways() {
}
private void printSideways(NameTreeNode root, int indent) {
}
NameTreeTest (IntTreeTest): Provide a test program that does these things: 1) Declares an array of names
2) Initialize array to these values: {"Beth", "Sue", "Dave", "Pat", "Mike", "Dawn", "Cindi", "Gina"}
3) Iterate the array and add the names to your NameTreeSearch by calling add.
4) Produce this exact output:
Problems Javadoc Declaration SearchConsole aHierarchy terminated> IntTreeTest [Java Application] /System/Library/Frameworks/JavaVM.framework Versi Sue Pat Mike Gina Dawn Dave Cindi Beth Beth Cindi Dave Dawn Gina Mike Pat Sue The first uses the printSideways method and the second uses the print) method that uses Inorder traversal (and proves the binary tree is sorted). (20 pts)Explanation / Answer
Below is your code. Please do rate this answer positive, If i was able to help you. Let me know if you have any issues in comments
NameTreeNode.java
public class NameTreeNode {
public String data; // data stored at this node
public NameTreeNode left; // reference to left subtree
public NameTreeNode right; // reference to right subtree
// Constructs a leaf node with the given data.
public NameTreeNode(String data) {
this(data, null, null);
}
// Constructs a leaf or branch node with the given data and links.
public NameTreeNode(String data, NameTreeNode left, NameTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
NameTreeSearch.java
public class NameTreeSearch {
private NameTreeNode overallRoot;
public NameTreeSearch() {
overallRoot = null;
}
public void add(String aName) {
overallRoot = add(overallRoot, aName);
}
private NameTreeNode add(NameTreeNode root, String aName) { // Hint: Think
// Comparable
if (root == null) {
// base case: we have fallen off the tree,
// so the new value should go here
root = new NameTreeNode(aName);
} else if (root.data.compareTo(aName) > 0) {
// recursive case: this value is smaller so it goes to the left.
// Notice we must re-assign root.left to store the value returned.
root.left = add(root.left, aName);
} else if (root.data.compareTo(aName) < 0) {
// recursive case: this value is larger so it goes to the right.
// Notice we must re-assign root.right to store the value returned.
root.right = add(root.right, aName);
} // else it's a duplicate; so don't add it
return root;
}
public void print() { // Inorder traversal } private void print(NameTreeNode
// root) {
print(overallRoot);
System.out.println();
}
private void print(NameTreeNode root) {
if (root != null) {
print(root.left);
System.out.print(root.data + " ");
print(root.right);
}
}
public void printSideways() {
printSideways(overallRoot, 0);
}
private void printSideways(NameTreeNode root, int indent) {
if (root == null) {
} else {
// root != null
printSideways(root.right, indent + 1);
for (int i = 1; i <= indent * 4; i++) {
System.out.print(" ");
}
System.out.println(root.data);
printSideways(root.left, indent + 1);
}
}
}
NameTreeTest.java
public class NameTreeTest {
public static void main(String[] args) {
String names[] = { "Beth", "Sue", "Dave", "Pat", "Mike", "Dawn", "Cindi", "Gina" };
NameTreeSearch nmSearch = new NameTreeSearch();
for (int i = 0; i < names.length; i++) {
nmSearch.add(names[i]);
}
nmSearch.printSideways();
nmSearch.print();
}
}
Output
Sue
Pat
Mike
Gina
Dawn
Dave
Cindi
Beth
Beth Cindi Dave Dawn Gina Mike Pat Sue