Question

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 );

}

}

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;
   }
   }
          
       }
  
}