I appreciate any help with the following Java code problem. Please Add the toStr

Question

I appreciate any help with the following Java code problem.

Please Add the toString method to the existing class BinarySearchTree below:

/**
* Class implementing a binary search tree.
*/
public class BinarySearchTree
{
/**
* Initializes the bst to empty creating a dummy root node.
*/
public BinarySearchTree()
{
root = new Node(); //dummy node as the root
root.setLeftChild(null);
root.setRightChild(null);
root.setInfo(-1);
}

/**
* Determines whether the bst is empty
*
* @return true if the bst is empty, false otherwise
*/
public boolean isEmpty()
{
return root.getLeftChild() == null;
}

/**
* Prints the bst elements using inorder traversal. This method invokes the
* private method inorderDisplay, passing to it the root of the actual tree.
*/
public void display()
{
inorderDisplay(root.getLeftChild());
System.out.println();
}

/**
* Determines if an item exists in the bst. This method invokes the private
* method search, passing to it the element to be found and the root
* of the actual tree.
*
* @param x element to be found.
* @return true if x is found in the bst, false otherwise.
*/
public boolean contains(int x)
{
return search(x, root.getLeftChild());
}

/**
* Adds the element x to the bst. This method invokes the private method
* insert, passing to it the element to be added to the bst and the root
* of the actual tree.
*
* @param x element to be added to the bst.
*/
public void add(int x)
{
if (root.getLeftChild() == null)
{
Node p = new Node();
p.setNode(x, null, null);
root.setLeftChild(p);
} else
insert(x, root.getLeftChild());
}

/**
* Finds the smallest element in the bst. This method invokes the overloaded
* method getMin, passing to it the root of the tree.
*
* @return the smallest element in the bst.
*/
public int getMin()
{
return getMin(root);
}
  
private Node root; //root of the bst. It's implemented as a dummy node.

/**
* Prints the elements of the subtree whose root is referenced by p. Uses
* inorder traversal.
*
* @param p root of subtree.
*/
private void inorderDisplay(Node p)
{
if (p != null)
{
inorderDisplay(p.getLeftChild());
System.out.print(p.getInfo() + " ");
inorderDisplay(p.getRightChild());
}
}

/**
* Finds if x is inserted in the subtree whose root is referenced by p. The
* search is conducted recursively, using the bst property: keys in the left
* subtree of a node are smaller than or equal to the key in the node, while
* the keys in the right subtree of the node are greater.
*
* @param x element to be found.
* @param p root of subtree.
* @return true if x is found in this subtree, false otherwise.
*/
private boolean search(int x, Node p)
{
if (p == null)
return false;
else if (x == p.getInfo())
return true;
else if (x < p.getInfo())
return search(x, p.getLeftChild());
else
return search(x, p.getRightChild());
}

/**
* Adds x to the subtree referenced by p. The search for the location to
* insert the new node is conducted recursively, using the bst property:
* keys in the left subtree of a node are smaller than or equal to the key
* in the node, while the keys in the right subtree of the node are greater.
*
* @param x element to be added to the subtree.
* @param p root of subtree.
*/
private void insert(int x, Node p)
{
if (x < p.getInfo())
if (p.getLeftChild() == null)
{
Node q = new Node();
q.setNode(x, null, null);
p.setLeftChild(q);
} else
insert(x, p.getLeftChild());
else if (p.getRightChild() == null)
{
Node q = new Node();
q.setNode(x, null, null);
p.setRightChild(q);
} else
insert(x, p.getRightChild());
}

/**
* Recursively finds the smallest element in the subtree referenced by p.
* The method uses this property of BSTs: the smallest value is stored in
* the leftmost node.
*
* @param p root of subtree.
* @return smallest element in the subtree referenced by p.
*/
private int getMin(Node p)
{
if (p.getLeftChild() == null)
return p.getInfo();
else
return getMin(p.getLeftChild());
}
}

Explanation / Answer

Following is the sample code to implement BST on Strings.

package javaapplication8;
import java.util.*;

public class JavaApplication8 {
public static void main(String[] args) {
Tree myTree = new Tree();
Scanner keyboard = new Scanner(System.in);
int input;
while(true){
System.out.println(" Select the option!");
System.out.println(" 1 - Enter the String");
System.out.println(" 2 - Search for a String");
System.out.println(" 3 - Display Tree : preorder");
System.out.println(" 4 - Exit");
input = keyboard.nextInt();
Scanner scanner = new Scanner(System.in);
if(input == 1){
System.out.println("Enter a new string: ");
String word = scanner.next().toUpperCase();
myTree.insert(word);
System.out.println("Inserted " + "'" + word + "'" + " into tree");
}else if(input == 2){
System.out.println("Enter a string to search: ");
}else if(input == 3){
System.out.println("Display Tree: ");
myTree.preOrder();
}else if(input == 4){
System.exit(0);//exit program
}
System.out.println(" Enter another option");
}   
}
}

//Tree Class

class Tree {
public TreeNode root;
public Tree(){
root = null;
}
public TreeNode returnRoot(){
return root;
}
public boolean isEmpty(){
return root == null;
}
public void insert(String value){
if(isEmpty()){
root = new TreeNode(value);
}else{
root.add(value);
}
}
public TreeNode getRoot(){
return root;
}
public void preOrder() {
preOrder(root);
}
// using the function ...
public void preOrder(TreeNode root) {
if (root != null) {
System.out.println(root.getWord()); // root
preOrder(root.getLeft()); // left
preOrder(root.getRight()); // right
}
}
}

//TreeNode class

class TreeNode {
private String word; // The data in this node.
private TreeNode left; // Pointer to the left subtree.
private TreeNode right; // Pointer to the right subtree.
public TreeNode(String s){
word = s;
left = null;
right = null;
}
public void add(String value) {
if (left == null) {   
left = new TreeNode(value);   
} else if( right == null){
right = new TreeNode(value);
} else {
if(countNodes(left) <= countNodes(right)){   
left.add(value);
} else {
right.add(value);
}   
}
}
//Count the nodes in the binary tree to which root points, and
public static int countNodes( TreeNode root ) {
if ( root == null ){
// The tree is empty. It contains no nodes.
return 0;
}else {
// Start by counting the root.
int count = 1;   
// Add the number of nodes in the left subtree.
count += countNodes(root.left);
// Add the number of nodes in the right subtree.
count += countNodes(root.right);
return count; // Return the total.
}
}
public TreeNode getLeft(){
return left;
}
public TreeNode getRight(){
return right;
}
public String getWord(){
return word;
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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