Question

In: Computer Science

You will be inserting values into a generic tree, then printing the values inorder, as well...

You will be inserting values into a generic tree, then printing the values inorder, as well as printing the minimum and maximum values in the tree. Given main(), write the methods in the 'BSTree' class specified by the // TODO: sections. There are 5 TODOs in all to complete.

Ex: If the input is

like
ferment
bought
tasty
can
making
apples
super
improving
juice
wine
-1

the output should be:

Enter the words on separate lines to insert into the tree, enter -1 to stop

The Elements Inorder: apples - bought - can - ferment - improving - juice - like - making - super - tasty - wine - 

The minimum element in the tree is apples

The maximum element in the tree is wine

import java.util.Scanner;

public class Main {

   public static void main(String[] args) {

       BSTree<String> tree = new BSTree<String>();
      
       Scanner scrn = new Scanner(System.in);
       System.out.println("Enter the words on separate lines to insert into the tree, enter -1 to stop");
      
       String word = scrn.nextLine();
       while(!word.equals("-1")) {
           tree.addElement(word);
           word = scrn.nextLine();
       }
       System.out.println();
      
       tree.printElements();
      
       System.out.println("\nThe minimum element in the tree is " + tree.findMin());
       System.out.println("\nThe maximum element in the tree is " + tree.findMax());

   }

}

public class BSTreeNode<T> {

   private T element;
   private BSTreeNode<T> left, right;

   public BSTreeNode(T element) {
       this.element = element;
       this.left = null;
       this.right = null;
   }

   public T getElement() {
       return element;
   }

   public void setElement(T element) {
       this.element = element;
   }

   public BSTreeNode<T> getLeft() {
       return left;
   }

   public void setLeft(BSTreeNode<T> left) {
       this.left = left;
   }

   public BSTreeNode<T> getRight() {
       return right;
   }

   public void setRight(BSTreeNode<T> right) {
       this.right = right;
   }
      
}

public class BSTree<T> {

   private BSTreeNode<T> root = null;

   // TODO: Write an addElement method that inserts generic Nodes into
   // the generic tree. You will need to use a Comparable Object

   // TODO: write the method printElements
       // It should check that the tree isn't empty
       // and prints "The Tree is empty" if it is
       // otherwise prints "The Elements Inorder: "
       // and calls the inorder method


  
   // TODO: write the inorder method that traverses
       // the generic tree and prints the data inorder

   // TODO: write the findMin method that returns the
       // minimum value element in the tree

   // TODO: write the findMin method that returns the
       // maximum value element in the tree

}

Solutions

Expert Solution

Please find the code for the above program below:

BSTree.java Class :

public class BSTree<T> {

private BSTreeNode<T> root = null;

@SuppressWarnings("unchecked")
public void addElement(String word) {
if (root == null) { // must handle case of empty tree first
root = new BSTreeNode<T>((T)word);
return;
}
BSTreeNode<T> loc = root; // start search downward at root
while (true) {
if (word.compareTo(loc.getElement().toString()) < 0) { // look left
if (loc.getLeft()!= null) loc = loc.getLeft();
else
{
   BSTreeNode<T> leftNode = new BSTreeNode<T>((T) word);
   loc.setLeft(leftNode);
   break;
}
}
else if (word.compareTo(loc.getElement().toString()) > 0) { // look right
if (loc.getRight() != null) loc = loc.getRight();
else
{
   BSTreeNode<T> rightNode = new BSTreeNode<T>((T) word);
   loc.setRight(rightNode);
   break;
}
}
else break; // found! Don't insert
}
   }

// TODO: write the method printElements
// It should check that the tree isn't empty
// and prints "The Tree is empty" if it is
// otherwise prints "The Elements Inorder: "
// and calls the inorder method
public void printElements()
{
   if(root == null)
   {
       System.out.println("The Tree is empty");
   }
   else
   {
       System.out.println("The Elements Inorder: ");
       inorder();
   System.out.println();
   }
         
}
  
// TODO: write the inorder method that traverses
// the generic tree and prints the data inorder
public void inorder()
{
   inorderTraversal(root);
}

// inorderT: recursive function that does the work
private void inorderTraversal(BSTreeNode<T> t) {
if (t != null) {
   inorderTraversal(t.getLeft());
System.out.print(t.getElement() + " ");
inorderTraversal(t.getRight());
}
}

// TODO: write the findMin method that returns the
// minimum value element in the tree
public String findMin()
{
   BSTreeNode<T> currentNode = root;
   while(currentNode.getLeft()!=null)
   {
       currentNode = currentNode.getLeft();
   }
     
   return currentNode.getElement().toString();
}

// TODO: write the findMin method that returns the
// maximum value element in the tree
public String findMax()
{
   BSTreeNode<T> currentNode = root;
   while(currentNode.getRight()!=null)
   {
       currentNode = currentNode.getRight();
   }
     
   return currentNode.getElement().toString();
}

}

PS : The code was tested with the test case mentioned in the question. Please run another test case at your end.

Thankyou


Related Solutions

(10 pts) Construct a (2,3) B tree starting from an empty tree, inserting the following values:...
(10 pts) Construct a (2,3) B tree starting from an empty tree, inserting the following values: 30, 50, 32, 10, 25, 35, 40, 50, 70, 80. Show your work. (10 pts) Using the result of the (2,3) B tree in question 8 above, insert the following into the tree: 45, 22, 6, 99
Just Implement Inorder, Preorder and Postorder of Tree Data Structure in given code below. Thank You....
Just Implement Inorder, Preorder and Postorder of Tree Data Structure in given code below. Thank You. #include<bits/stdc++.h> using namespace std; struct Node{     int data;     Node* left;     Node* right; }; Node* createNode(int value){     Node* newNode = new Node();     newNode->data = value;     newNode->left = NULL;     newNode->right = NULL;     return newNode; } Node* insert(Node *currentNode, int value){     if(currentNode==NULL){         currentNode = createNode(value);     }else if(value <= currentNode->data){         currentNode->left = insert(currentNode->left,value);     }else{        ...
C++ AVL tree My AVL tree function void inorder(AVLNode* t) { if (t == NULL) return;...
C++ AVL tree My AVL tree function void inorder(AVLNode* t) { if (t == NULL) return; inorder(t->left); cout << t->data.cancer_rate << " "; inorder(t->right); } void inorder() { inorder(root); } Will Print my cancer city rate Inorder example) 3.1 5.8 19.8 My question is how can I add a decreasing index to this function example) 3) 3.1 2)5.8 1)19.8
Please ready a program should output Inorder Tree Traversal without recursion and without stack!, output in...
Please ready a program should output Inorder Tree Traversal without recursion and without stack!, output in ALGOL W programming only. Thumbs down for wrong answers Make a program to perform Heap Sort, must run in Alice programming only. Only correct answers needed should be in given language
C++ Assume you need to test a function named inOrder. The function inOrder receives three int...
C++ Assume you need to test a function named inOrder. The function inOrder receives three int arguments and returns true if and only if the arguments are in non-decreasing order: that is, the second argument is not less than the first and the third is not less than the second. Write the definition of driver function testInOrder whose job it is to determine whether inOrder is correct. So testInOrder returns true if inOrder is correct and returns false otherwise. ....
C++ code (just fuction) Binary Search Tree (BTS) 1) Algorithm for all traversals (inorder, preorder, postorder,...
C++ code (just fuction) Binary Search Tree (BTS) 1) Algorithm for all traversals (inorder, preorder, postorder, level order), done nonrecursively 2)Ability to provide the result of traversing a tree in all traversals (inorder, preorder, postorder, level order)
Draw each binary tree that is the maximum heap that results from inserting one by one in the order given the values 20, 15, 25, 30, 45, 18, 10, 12, 16.
In Java-Draw each binary tree that is the maximum heap that results from inserting one by one in the order given the values 20, 15, 25, 30, 45, 18, 10, 12, 16. Note that your tree diagram should show the heap after the maximum heap property has been restored. Submit nine diagrams.Next, draw each binary tree that is the maximum heap as each maximum value is deleted from the above tree and after the maximum heap property has been restored....
1.) Consider inserting values 15, 22 and 29 in the order given into a hash table...
1.) Consider inserting values 15, 22 and 29 in the order given into a hash table of size 7 with hash function h(x) = x mod 7. What will be the locations be the respective locations for 15, 22 and 29 in the hash table if quadratic probing is used to resolve colisions? a. 1, 2, 4 b. 1, 2, 3 c. 1, 2, 0 d. 1, 1, 1 2.) Consider the following sequences of addqs and removeqs, what order...
Consider inserting values 15, 22 and 29 in the order given intoa hash table of...
Consider inserting values 15, 22 and 29 in the order given into a hash table of size 7 with hash function h(x) = x mod 7. What will be the locations be the respective locations for 15, 22 and 29 in the hash table if quadratic probing is used to resolve colisions?a.1, 2, 4b.1, 2, 3c.1, 2, 0d.1, 1, 1
use postorder and inorder tree traversals to make preorder traversal. #!/usr/bin/env python3 # encoding: UTF-8 """Turning...
use postorder and inorder tree traversals to make preorder traversal. #!/usr/bin/env python3 # encoding: UTF-8 """Turning in-order and post-order tree traversals into pre-order""" def get_preorder(inorder: str, postorder: str) -> str: """Return pre-order traversal of a tree based on its in-order and post-order traversals""" #Complete the following function #raise NotImplementedError
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT