Homework SourseThis is in java and you are not allowed to use Java API clas
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 );
}
}
| Level order traversal: 8 3 10 1 6 14 4 7 13 |
Solution
public class Node
{
public Node left, right; // Intentionally left public for east access
public int data;
/* Empty node Constructor */
public Node(){
left = null;
right = null;
data = 0;
}
/* Node with value Constructor */
public Node(int n){
left = null;
right = null;
data = n;
}
}
public class Tree
{
private Node root;
public Tree(){
root = null;
}
//option 1
public Node insert(int data){
return root = insert(root, data);
}
private Node insert(Node node, int data){
if (node == null){
return node = new Node(data);
}
else{
if (data < node.data)
node.left = insert(node.left, data);
else if(data > node.data)
node.right = insert(node.right, data);
// in case data==node.getData() Duplicate; do nothing
}
return node;
}
//option 2
public void printTree(){
if(root == null)
System.out.println(\"Tree is empty\");
else
printTree(root);
System.out.println();
}
private void printTree(Node node){
if(node != null){
printTree(node.left);
System.out.print(node.data+\" \");
printTree(node.right);
}
}
//option 3
public int numLeaves(){
return numLeaves(root);
}
private int numLeaves(Node node){
if (node == null)
return 0;
if (node.left == null && node.right == null)
return 1;
else
return numLeaves(node.left) + numLeaves(node.right);
}
//option 4
public int numOneChildNodes() {
return numOneChildNodes(root);
}
private int numOneChildNodes(Node node){
if(root == null)
return 0;
if(root.left == null && root.right == null)
return 0;
if(root.left == null || root.right == null)
return 1 + numOneChildNodes(root.left) + numOneChildNodes(root.right);
else
return numOneChildNodes(root.left) + numOneChildNodes(root.right);
}
//option 5
public int numTwoChildrenNodes() {
return countTwoChildren(root);
}
private int countTwoChildren(Node node){
if(node==null)
return 0;
if(node.left!=null && node.right!=null)
return 1 + countTwoChildren(node.left) + countTwoChildren(node.right);
return countTwoChildren(node.left) + countTwoChildren(node.right);
}
//option 6
public void levelOrder(){
int height = calculateHeight(root);
for (int i=1; i<=height; i++)
printLevel(root, i);
System.out.println();
}
private int calculateHeight(Node root){
if (root == null)
return 0;
else{
int leftHeight = calculateHeight(root.left);
int rightHeight = calculateHeight(root.right);
if (leftHeight > rightHeight)
return(leftHeight+1);
else
return(rightHeight+1);
}
}
private void printLevel (Node root ,int level){
if (root == null)
return;
if (level == 1)
System.out.print(root.data + \" \");
else if (level > 1){
printLevel(root.left, level-1);
printLevel(root.right, level-1);
}
}
}
import java.util.Scanner;
public class MainClass{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
Tree tree = new Tree(); // Creating object of tree
while (true){
System.out.println(\"1. Insert node \");
System.out.println(\"2. Print tree\");
System.out.println(\"3. Print number of leaves in tree\");
System.out.println(\"4. Print the number of nodes in T that contain only one child\");
System.out.println(\"5. Print the number of nodes in T that contain only two children\");
System.out.println(\"6. Print the level order traversal of the tree\");
System.out.println(\"7. Exit program\");
int choice = scan.nextInt();
switch (choice){
case 1 :
System.out.println(\"Enter node value\");
tree.insert(scan.nextInt());
break;
case 2 :
tree.printTree();
break;
case 3 :
System.out.println(tree.numLeaves());
break;
case 4 :
System.out.println(tree.numOneChildNodes());
break;
case 5 :
System.out.println(tree.numTwoChildrenNodes());
break;
case 6 :
tree.levelOrder();
break;
case 7 :
System.exit(0);
break;
default :
System.out.println(\"Invalid Input\");
break;
}
}
}
}
