Binary Tree Template Write your own version of a class template that will create
ID: 2247006 • Letter: B
Question
Binary Tree Template
Write your own version of a class template that will create a binary tree that can hold values of any data type. Demonstrate the class with a driver program.
Be sure to include methods for insertion, removal, and searching of nodes.
Include a method for printing the tree out in order.
You'll need public and private versions of these methods. The public versions will call the private versions. The private versions will use recursion.
To be explicit, the type of binary tree is a binary search tree.
Explanation / Answer
import java.util.Scanner;
import java.io.*;
class binarytree //Binary class
{
binarytree left, right;
int data;
/* Constructor */
public binarytree()
{
left = null;
right = null;
data = 0;
}
/* Parameterised Constructor */
public binarytree(int n)
{
left = null;
right = null;
data = n;
}
//Fn to set left node
public void setLeft(binarytree n)
{
left = n;
}
//Fn to set Right node
public void setRight(binarytree n)
{
right = n;
}
public binarytree getLeft()// getter for left node
{
return left;
}
public binarytree getRight() //getter for right node
{
return right;
}
public void setData(int d)
//setter for node
{
data = d;
}
public int getData()
//setter for node
{
return data;
}
}
class bintr
{
private binarytree root;
public bintr()
{
root = null;
}
public boolean isEmpty()
{
return root == null;
}
public void insert(int data)
{
root = insert(root, data);
}
private binarytree insert(binarytree node, int data)
{
if (node == null)
node = new binarytree(data);
else
{
if (node.getRight() == null)
node.right = insert(node.right, data);
else
node.left = insert(node.left, data);
}
return node;
}
public int countNodes()
{
return countNodes(root);
}
private int countNodes(binarytree r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}
public boolean search(int val)
{
return search(root, val);
}
private boolean search(binarytree r, int val)
{
if (r.getData() == val)
return true;
if (r.getLeft() != null)
if (search(r.getLeft(), val))
return true;
if (r.getRight() != null)
if (search(r.getRight(), val))
return true;
return false;
}
public void inorder()
{
inorder(root);
}
private void inorder(binarytree r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
public void preorder()
{
preorder(root);
}
private void preorder(binarytree r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
public void postorder()
{
postorder(root);
}
private void postorder(binarytree r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
}
/* Class BinaryTree */
public class BinaryTree
{
//Driver Function for binary tree
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
bintr bt = new bintr();
System.out.println("Binary Tree Test ");
char ch;
do
{// MENU
System.out.println(" Binary Tree Operations ");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. count nodes");
System.out.println("4. check empty");
int choice = scan.nextInt(); //Taking choice
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
bintr.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ bintr.search( scan.nextInt() ));
break;
case 3 :
System.out.println("Nodes = "+ bintr.countNodes());
break;
case 4 :
System.out.println("Empty status = "+ bintr.isEmpty());
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display tree */
System.out.print(" Post order : ");
bintr.postorder();
System.out.print(" Pre order : ");
bintr.preorder();
System.out.print(" In order : ");
bintr.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.