Implement the code using Java. Binary Tree Programming problem: Create and test
ID: 3904020 • Letter: I
Question
Implement the code using Java.
Binary Tree Programming problem:
Create and test a Binary Search Tree class that stores names in String format. This class will closely parallel the IntTreeSearch code discussed in class and in Canvas.
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 NameTreeSearchby calling add.
4)Produce this exact output:
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).
**For this problem use the following files: IntTreeNode, IntTreeSearch, IntTreeTest and modify IntTreeTest for this problem.**
public class IntTreeNode {
public int data;
public IntTreeNode left;
public IntTreeNode right;
// can only create a root node
public IntTreeNode(int data) {
this(data, null, null);
}
// Full ctor
public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
public class IntTreeSearch {
private IntTreeNode overallRoot;
public IntTreeSearch() {
this.overallRoot = null;
}
public void add(int anum) {
this.overallRoot = this.add(this.overallRoot, anum);
}
private IntTreeNode add(IntTreeNode root, int anum) {
if (root == null) {
root = new IntTreeNode(anum);
}
else if (anum <= root.data) {
root.left = add(root.left, anum);
}
else {
root.right = add(root.right, anum);
}
return root;
}
public void print() {
print(this.overallRoot);
}
private void print(IntTreeNode root) {
if (root != null) {
// recursive case
print(root.left);
System.out.print(" " + root.data);
print(root.right);
}
}
public void printSideways() {
this.printSideways(this.overallRoot, 0);
}
private void printSideways(IntTreeNode root, int indent) {
if (root != null) {
printSideways(root.right, indent+1);
for (int i=0; i
System.out.print(" ");
}
System.out.println(" " + root.data);
printSideways(root.left, indent+1);
}
}
}
import java.util.Random;
import java.util.Stack;
public class IntTreeTest {
public static void main(String[] args) {
// Final Exam : Create tree of names
// NameTreeNode namesRoot = createNameTree();
// NameTreeSearch theNamesTree = new NameTreeSearch();
//
// String[] names = {"Beth", "Sue", "Dave", "Pat", "Mike", "Dawn", "Cindi", "Gina"};
// for (String name : names) {
// theNamesTree.add(name);
// }
// theNamesTree.printSideways();
// theNamesTree.print();
}
}
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();
}
}