Create a new project called Homework12. The following code shows a simple Java i

Question

Create a new project called Homework12.
The following code shows a simple Java implementation of a Node class Node.java and the BinaryTree class BinaryTree.java (parts of the code is missing, you are to complete it). ===========.
For simplicity, this version stores Strings rather than Objects.

Node.java

public class Node {
protected String DataItem;
protected Node LeftSubTree;
protected Node RightSubTree;

public Node ( ){
this.DataItem = "";
this.LeftSubTree = null;
this.RightSubTree = null;
}

public Node ( String data){
this.DataItem = data;
this.LeftSubTree = null;
this.RightSubTree = null;
}

}

BinaryTree.java

public class BinaryTree {

private Node Root;
/**
* Constructor for objects of class BinaryTree
*/

public BinaryTree() {
Root = null;
}
public BinaryTree(String rootData) {
Root = new Node (rootData);
}

/**
* sets all Root entry to null
*
**/
public void destroy() {
Root = null;
}

/**
* checks whether BinaryTree is empty
*/
public boolean isEmpty() {
return (Root == null);
}

/**
* get an item of the BinaryTree
*/

public String Get(String o) {
String str = get (Root, o);
return (str);

}
public String get(Node Root, String o) {
if (!(Root == null))
{
if (o.equals(Root.DataItem)) {
return (Root.DataItem);
} else if (o.compareTo(Root.DataItem) < 0) {
return (get(Root.LeftSubTree, o));
} else {
return (get(Root.RightSubTree, o));
}
} else {
return null;
}
}

/**
* add an item to the BinaryTree
*/
public void Add(String o) {
Node parentNode;
Node newNode = new Node (o);
if (Root == null){
Root = newNode;
}
else{
parentNode = Root;
add(parentNode, newNode, o);
}
}

/**
* add an item to the BinaryTree
*/
public void add(Node LocalRoot, Node newNode, String o)
{
=======
=======
}
/**
* PreOrder Traversal of the BinaryTree
*/
public void PreOrder() {
preorder (Root);
}

public void preorder(Node Root) {
if (!(Root == null))
{
System.out.println("Visited" + Root.DataItem);
preorder(Root.LeftSubTree);
preorder(Root.RightSubTree);
}
else
System.out.println("Visited none: Tree is EMPTY");
}
}
Using a BinaryTree
Data structure classes are intended to be used in programs as utility classes which contain the data the program needs to work with. To use the BinaryTree class, you need to know how to write code to call the BianryTree operations, for example to add data to the BinaryTree.
Controller Class: The following class TreeTester.java shows how to use a BinaryTree to hold string objects. Calls to BinaryTree operations are shown in bold.
TreeTester.java (parts of the code is missing, you are to complete it).

public class TreeTester {

private BinaryTree tree;
private Node root;

public TreeTester(BinaryTree tree) {
this.tree = tree;
}

/**
* check to see if tree is empty
*/
public void isEmptyTree() {
if (tree.isEmpty())
System.out.println("Tree is EMPTY?");
else
System.out.println("Tree is NOT EMPTY?");
}

/**
* add item to tree
*/
public void populateTree(String str) {
System.out.println("Control class: Populate the Binary Tree");
tree.Add(str);
System.out.println("Added new string: " + str);
}

/**
* Preorder traversal of the tree
*/
public void traverseTreeInPreOrder() {
System.out.println("Control class: PreOrder traversal of the Binary Tree");
System.out.println("The PreOrder Travelsal is:");
tree.PreOrder();
}

/**
* search item in the tree
*/
public void searchInBinaryTree(String str) {
System.out.println("Control class: Searching the Binary Tree");
System.out.println("Found string " + tree.Get(str));
}
}

Create a Driver.java class (it contains main).
1. Create an instance of BinaryTree called bt.
2. Create a new instance of Controller Class called TreeTester called treetest with the BinaryTree bt created above.
3. Call the isEmptyTree method of your TreeTester. What was the result?
4. Call the populateTree method of your TreeTester with:
Jim, Dot, Amy, Ann, Guy, Eva, Jan, Ron, Kay, Jon, Kim, Tim, Roy, Tom

5. Call the traverseTreeInPreOrder method of your TreeTester to get the preorder traversal of your tree.

6. Call the searchInBinaryTree method of your TreeTester to find “Kim”. Trace the code and observe the nodes traversed to get to “Kim”.

Explanation / Answer

public class Node { protected String DataItem; protected Node LeftSubTree; protected Node RightSubTree; public Node ( ){ this.DataItem = ""; this.LeftSubTree = null; this.RightSubTree = null; } public Node ( String data){ this.DataItem = data; this.LeftSubTree = null; this.RightSubTree = null; } } public class BinaryTree { private Node Root; /** * Constructor for objects of class BinaryTree */ public BinaryTree() { Root = null; } public BinaryTree(String rootData) { Root = new Node(rootData); } /** * sets all Root entry to null * * */ public void destroy() { Root = null; } /** * checks whether BinaryTree is empty */ public boolean isEmpty() { return (Root == null); } /** * get an item of the BinaryTree */ public String Get(String o) { String str = get(Root, o); return (str); } public String get(Node Root, String o) { if (!(Root == null)) { if (o.equals(Root.DataItem)) { return (Root.DataItem); } else if (o.compareTo(Root.DataItem) < 0) { return (get(Root.LeftSubTree, o)); } else { return (get(Root.RightSubTree, o)); } } else { return null; } } /** * add an item to the BinaryTree */ public void Add(String o) { Node parentNode; Node newNode = new Node(o); if (Root == null) { Root = newNode; } else { parentNode = Root; add(parentNode, newNode, o); } } /** * add an item to the BinaryTree */ public void add(Node LocalRoot, Node newNode, String o) { /*compare the string to be inserted with the local root lexographically and insert new node in the left subtree if the new node is lexographically smaller else in the right sub tree, recursively*/ if ((o.compareTo(LocalRoot.DataItem)) < 0) { if (LocalRoot.LeftSubTree != null) { add(LocalRoot.LeftSubTree, newNode, o); } else { LocalRoot.LeftSubTree = newNode; } } else if ((o.compareTo(LocalRoot.DataItem)) > 0) { if (LocalRoot.RightSubTree != null) { add(LocalRoot.RightSubTree, newNode, o); } else { LocalRoot.RightSubTree = newNode; } } } /** * PreOrder Traversal of the BinaryTree */ public void PreOrder() { preorder(Root); } public void preorder(Node Root) { if (!(Root == null)) { System.out.println("Visited" + Root.DataItem); preorder(Root.LeftSubTree); preorder(Root.RightSubTree); } else { System.out.println("Visited none: Tree is EMPTY"); } } } public class TreeTester { private BinaryTree tree; private Node root; public TreeTester(BinaryTree tree) { this.tree = tree; } /** * check to see if tree is empty */ public void isEmptyTree() { if (tree.isEmpty()) { System.out.println("Tree is EMPTY?"); } else { System.out.println("Tree is NOT EMPTY?"); } } /** * add item to tree */ public void populateTree(String str) { System.out.println("Control class: Populate the Binary Tree"); tree.Add(str); System.out.println("Added new string: " + str); } /** * Preorder traversal of the tree */ public void traverseTreeInPreOrder() { System.out.println("Control class: PreOrder traversal of the Binary Tree"); System.out.println("The PreOrder Travelsal is:"); tree.PreOrder(); } /** * search item in the tree */ public void searchInBinaryTree(String str) { System.out.println("Control class: Searching the Binary Tree"); System.out.println("Found string " + tree.Get(str)); } } public class Driver { public static void main(String[] args) { BinaryTree bt = new BinaryTree(); TreeTester treetest = new TreeTester(bt); treetest.isEmptyTree(); String[] a = new String[] {"Jim", "Dot", "Amy", "Ann", "Guy", "Eva", "Jan", "Ron", "Kay", "Jon", "Kim", "Tim", "Roy", "Tom"}; for(String s:a) treetest.populateTree(s); treetest.traverseTreeInPreOrder(); treetest.searchInBinaryTree("Kim"); } } /* Q.Call the isEmptyTree method of your TreeTester. What was the result? A: Tree is EMPTY? */

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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