Question

This is in java and you are not allowed to use Java API classes for queues,...

This is in java and you are not allowed to use Java API classes for queues, stacks, arrays, arraylists and linkedlists. You have to write your own implementations for them.

You should construct a BST by inserting node values starting with a null tree. You can re-use the code for the insert method given in the sample code from the textbook. -insert method is provided below

Your code should have a menu driven user interface at the command line with the following options:

>> Enter choice [1-7] from menu below:

Insert node (prompts the user to enter node value and then inserts it into the BST)

Print tree (in-order) (You can reuse the code on page 164, Fig. 4.59 of the text) -code is provided below

Print number of leaves in tree (subpart a)

Print the number of nodes in T that contain only one child (subpart b)

Print the number of nodes in T that contain only two children (subpart c)

Print the level order traversal of the tree (subpart d)

Exit program

Your program should not exit until 7) is selected. Use this tree interface for the following subparts of this question:

Write methods in Java for each of the following operations. You can put the codes for each subpart in the same Java program, under different methods.

numLeaves method that returns the number of leaves in T                          (2 points)           

numOneChildNodes method that returns the number of nodes in T that contain only one child                                                                                                                                                  (2 points)

numTwoChildrenNodes method that returns the number of nodes in T that contain only two children                                                                                                                    (2 points)

levelOrder method that prints the level order traversal of the tree. A level order traversal first lists the root, then nodes at depth 1, followed by nodes at depth 2 and so on.                                                                                                                                                                                               (20 points)

An example of level-order traversal is given below:

Level order traversal:

8

3 10

1 6 14

4 7 13

You can print your output on a single line, like, 8 3 10 1 6 14 4 7 13

__________________________________________________________________________________________________________________________

//insert method

private AvlNode<AnyType> insert( AnyType x, AvlNode<AnyType> t )

{

if( t == null )

return new AvlNode<>( x, null, null );

int compareResult = x.compareTo( t.element );

if( compareResult < 0 )

t.left = insert( x, t.left );

else if( compareResult > 0 )

t.right = insert( x, t.right );

else

; // Duplicate; do nothing

return balance( t );

}

// print tree method

public void printTree( )

{

if( isEmpty( ) )

System.out.println( "Empty tree" );

else

printTree( root );

}

/* Internal method to print a subtree in sorted order. @param t the node that roots the subtree. */

private void printTree( BinaryNode<AnyType> t )

{

if( t != null )

{

printTree( t.left );

System.out.println( t.element );

printTree( t.right );

}

}

Homework Answers

Answer #1

Here is the Solution to get all requirements what you asked.With the addition what you asked i wrote the programme for "Breadth First Search(BFS)", "Depth First Search(DFS)",Height of Tree, Inorder, PreOrder and PostOrder Traversals also i written.Check once and use with your requirements.


import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class BinarySearchTree {
       class IntTreeNode{
           public int data;
       public IntTreeNode left;
       public IntTreeNode right;
      
       // constructs a leaf node with given data
       public IntTreeNode(int data) {
       this(data, null, null);
       }
      
       // constructs a branch node with given data, left subtree,
       // right subtree
       public IntTreeNode(int data, IntTreeNode left,
       IntTreeNode right) {
       this.data = data;
       this.left = left;
       this.right = right;
       }
       }
       private IntTreeNode overallRoot;

   // pre : max > 0
   // post: constructs a sequential tree with given number of
   // nodes
   public BinarySearchTree() {
   overallRoot=null;
   }

   // post: prints the tree contents using a preorder traversal
   public void printPreorder() {
   System.out.print("preorder:");
   printPreorder(overallRoot);
   System.out.println();
   }

   // post: prints the tree contents using a preorder traversal
   // post: prints in preorder the tree with given root
   private void printPreorder(IntTreeNode root) {
   if (root != null) {
   System.out.print(" " + root.data);
   printPreorder(root.left);
   printPreorder(root.right);
   }
   }

   // post: prints the tree contents using a inorder traversal
   public void printInorder() {
   System.out.print("inorder:");
   printInorder(overallRoot);
   System.out.println();
   }

   // post: prints in inorder the tree with given root
   private void printInorder(IntTreeNode root) {
   if (root != null) {
   printInorder(root.left);
   System.out.print(" " + root.data);
   printInorder(root.right);
   }
   }

   // post: prints the tree contents using a postorder traversal
   public void printPostorder() {
   System.out.print("postorder:");
   printPostorder(overallRoot);
   System.out.println();
   }

   // post: prints in postorder the tree with given root
   private void printPostorder(IntTreeNode root) {
   if (root != null) {
   printPostorder(root.left);
   printPostorder(root.right);
   System.out.print(" " + root.data);
   }
   }

   // post: prints the tree contents, one per line, following an
   // inorder traversal and using indentation to indicate
   // node depth; prints right to left so that it looks
   // correct when the output is rotated.
   public void printSideways() {
   printSideways(overallRoot, 0);
   }

   // post: prints in reversed preorder the tree with given
   // root, indenting each line to the given level
   private void printSideways(IntTreeNode root, int level) {
   if (root != null) {
   printSideways(root.right, level + 1);
   for (int i = 0; i < level; i++) {
   System.out.print(" ");
   }
   System.out.println(root.data);
   printSideways(root.left, level + 1);
   }
   }
   public int height(){
       return height(overallRoot);
   }
   private int height(IntTreeNode root){
       if(root==null){
           return 0;
       }else{
           return 1+Math.max(height(root.left),height(root.right));
       }
   }
   public void printLevelOrder(){
       int h=height(overallRoot);
       for(int i=0;i<=h;i++){
           printLevelOrder(overallRoot,i);
           System.out.println();
       }
   }
   private void printLevelOrder(IntTreeNode root,int level){
       if(root!=null){
           if(level==0)
               System.out.print(root.data+" ");
           else{
               printLevelOrder(root.left,level-1);
               printLevelOrder(root.right,level-1);
           }
       }
   }
   public void add(int value){
       overallRoot=add(overallRoot,value);
   }
   private IntTreeNode add(IntTreeNode root,int value){
       if(root==null)
           root=new IntTreeNode(value);
       else{
           if(value<=root.data)
               root.left=add(root.left,value);
           else
               root.right=add(root.right,value);
       }
       return root;
   }
   public void BFS(){
       BFS(overallRoot);
   }
   private void BFS(IntTreeNode root){
       if(root==null)
           return;
       Queue<IntTreeNode> q=new LinkedList<IntTreeNode>();
       q.add(root);
       while(!q.isEmpty()){
           IntTreeNode node=q.remove();
           if(node.left!=null)
               q.add(node.left);
           if(node.right!=null)
               q.add(node.right);
           System.out.print(" "+node.data);
       }
   }
   public void DFS(){
       DFS(overallRoot);
   }
   private void DFS(IntTreeNode root){
       if(root==null)
           return;
       Stack<IntTreeNode> s=new Stack<IntTreeNode>();
       s.push(root);
       while(!s.isEmpty()){
           IntTreeNode node=s.pop();
           if(node.right!=null)
               s.push(node.right);
           if(node.left!=null)
               s.push(node.left);
           System.out.print(" "+node.data);
       }
   }
   public int countLeaves(){
       return countLeaves(overallRoot);
   }
   private int countLeaves(IntTreeNode root) {
           if (root == null) {
               return 0;
           } else if (root.left == null && root.right == null) {
               return 1;
           } else {
               return countLeaves(root.left) + countLeaves(root.right);
           }
   }
   public int countNodesWithExactlyOneChild(){
       return countNodesWithExactlyOneChild(overallRoot);
   }
   private int countNodesWithExactlyOneChild(IntTreeNode root){
   if(root == null) return 0;
   return (havingOneChild(root) ? 1 : 0) +
   countNodesWithExactlyOneChild(root.left) +
   countNodesWithExactlyOneChild(root.right);

   }
   private boolean havingOneChild(IntTreeNode node) {
   if(node != null && ((node.left == null && node.right != null) ||
   (node.left != null && node.right == null))) {
   return true;
   }
   return false;
   }

   public int countNodesWithExactlyTwoChild(){
       return countNodesWithExactlyTwoChild(overallRoot);
   }
   private int countNodesWithExactlyTwoChild(IntTreeNode root){
   if(root == null) return 0;
   return (havingTwoChild(root) ? 1 : 0) +
   countNodesWithExactlyTwoChild(root.left) +
   countNodesWithExactlyTwoChild(root.right);

   }
   private boolean havingTwoChild(IntTreeNode node) {
   if(node != null && (node.left != null && node.right != null)) {
   return true;
   }
   return false;
   }
   public static void main(String[] args) {
           BinarySearchTree bst=new BinarySearchTree();
           Scanner scanner=new Scanner(System.in);
           int input=0;
           while (input!=7 || input==0){
               System.out.println("Please enter one of the Following:\n1.Insert Node\n"
                       + "2.Print Tree\n"
                       + "3.Print Number of Leaves in Tree\n"
                       + "4.Print the number of nodes in T that contain only one child\n"
                       + "5.Print the number of nodes in T that contain only two children\n"
                       + "6.Print the level order traversal of the tree\n"
                       + "7.Exit Program");
   input=scanner.nextInt();
   switch (input){
   case 1 :
       System.out.print("Enter the element:");
       int element=scanner.nextInt();
       bst.add(element);
   break;
   case 2 :
       bst.printSideways();
   break;
   case 3 :
       System.out.println("No of Leaves:"+bst.countLeaves());
   break;
   case 4 :
   System.out.println("No of Leaves with One Child:"+bst.countNodesWithExactlyOneChild());
   break;
   case 5 :
   System.out.println( "No of Leaves with Two Child:"+bst.countNodesWithExactlyTwoChild());
   break;
   case 6 :
       bst.printLevelOrder();
   break;
   case 7 :
   System.exit(0);
   break;
   }
   }
          
       }
  
}

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default. In the end of the insert method, set the root node of your red black tree to be black. Implement the rotate() and recolor() functions, and create tests for them in a separate class. import java.util.LinkedList; public class BinarySearchTree<T extends Comparable<T>> { protected static class Node<T> { public...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
do a code trace on how a key gets deleted package interview; import java.util.*; public class...
do a code trace on how a key gets deleted package interview; import java.util.*; public class binarySearchTree { Node root; void insert(int key) { root = insertRec(root,key); } void delete(int key) { root = deleteRec(root,key); } Node insertRec(Node root, int key) { if(root == null) { root = new Node(key); return root; } if(key < root.key) { root.leftChild = insertRec(root.leftChild,key); } else if(key > root.key){ root.rightChild = insertRec(root.rightChild,key); } return root; } Node deleteRec(Node root, int key) { if(root ==...
IN JAVA!! You may be working with a programming language that has arrays, but not nodes....
IN JAVA!! You may be working with a programming language that has arrays, but not nodes. In this case you will need to save your BST in a two dimensional array. In this lab you will write a program to create a BST modelled as a two-dimensional array. The output from your program will be a two-dimensional array.   THEN: practice creating another array-based BST using integers of your choice. Once you have figured out your algorithm you will be able...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted below) Implement the following methods using recursion: int depth() // returns the length of the deepest path from root to any leaf int node_count() // returns the number of nodes in the tree void insert(int n) // inserts value n into the tree BinarySearchTree2C clone() // returns a clone (deep copy) of the tree Add code to the main method to test these methods....
Java Program: You will be inserting values into a generic tree, then printing the values inorder,...
Java Program: 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...
Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None:...
Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None: """This method adds new value to the tree, maintaining BST property. Duplicates must be allowed and placed in the right subtree.""" Example #1: tree = BST() print(tree) tree.add(10) tree.add(15) tree.add(5) print(tree) tree.add(15) tree.add(15) print(tree) tree.add(5) print(tree) Output: TREE in order { } TREE in order { 5, 10, 15 } TREE in order { 5, 10, 15, 15, 15 } TREE in order {...
This is the java code that I have, but i cannot get the output that I...
This is the java code that I have, but i cannot get the output that I want out of it. i want my output to print the full String Form i stead of just the first letter, and and also print what character is at the specific index instead of leaving it empty. and at the end for Replaced String i want to print both string form one and two with the replaced letters instead if just printing the first...
In this code, I build a single-linked list using a node class that has been created....
In this code, I build a single-linked list using a node class that has been created. How could I change this code to take data of type T, rather than int. (PS: ignore the fact that IOHelper.getInt won't work for the type T... ie second half of main). Here's my code right now: public class SLList { public SLNode head = null; public SLNode tail = null; public void add(int a) {// add() method present for testing purposes SLNode newNode...