In: Computer Science
Java code for a binary tree that does the following:
Display a menu to the user and request for the desired
option.
Based on the user’s input, request for additional information as
follows:
o If the user wants to add a node, request for the name (or ID) of
the new node to be added as
well as the name of the desired parent of that node.
If the parent node already has two children, the new node cannot
be added since this
is a binary tree (and each node can only have at most two
children).
Display an appropriate message to the user.
Display the menu again for the user to make another choice.
If the parent node already has one child, add the new node as the
second child (right
child) of the parent node. Use recursion to traverse the tree to
the parent node.
Display the new tree with the new node added. This should be done
using a
recursive method in your project ( method printTree() ).
Display the menu.
If the parent node has no children, use recursion to add the new
node as the first child
(left child) of the parent node.
Display the new tree with the new node added.
Display the menu.
o If the user wants to know the size of the tree (i.e., the number of nodes in the whole tree or a
sub-tree), request for the name or ID of the node that is the root
of the desired tree (or sub-
tree). The size of a tree or sub-tree is the number of its children
and other ‘descendants’
(including any leaf nodes) plus one (the root node itself).
Recursively count the number of nodes in the tree (or sub-tree)
and display this with
an appropriate message.
Display the tree (or subtree) whose size was just
displayed.
Display the menu.
o If the user wants to find a node, request for the name or ID of
the node to search for in the
tree.
Search for the node in the tree using recursive calls. If the
node is found, display an
appropriate message; otherwise, indicate that the node does not
exist in the tree.
Display the menu.
o If the user wants to exit, terminate the program.
A sample output (to be followed exactly) is included below.
Example Output
A B C
B D E
D H I
H
I
E J K
J
K
C F G
F L
L
G
There are 12 nodes in this tree.
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->.3
Please enter an integer
k
Please enter an integer
6
Invalid input!
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->1
Please input the node you want to add->
M
Please input the parent node of M->
A
Parent already has 2 children.
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->1
Please input the node you want to add->
M
Please input the parent node of M->
F
Node successfully added!
A B C
B D E
D H I
H
I
E J K
J
K
C F G
F L M
L
M
G
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->2
Please input the root node->
A
There are 13 nodes in that tree
A B C
B D E
D H I
H
I
E J K
J
K
C F G
F L M
L
M
G
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->2
Please input the root node->
C
There are 5 nodes in that tree
C F G
F L M
L
M
G
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->3
Please input the node you want to find->
G
Node G found!
G
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->3
Please input the node you want to find->
U
Node U does not exist.
Please select one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->0
Design Requirements
The main class (with the main method) in your application should be
named BinaryTreeDemo. It is provided in
its entirety below and should not be changed.
public class BinaryTreeDemo {
public static void main(String[] args) {
Controller controller = new Controller();
controller.manipulateTree();
}
}
You should have another class – Controller – whose object is used
to call methods to create the initial tree and
then manipulate it depending on the user’s selections from the
menu. The constructor for the Controller class
does the following:
instantiates an object of the TreeDataStructure class (this
object is the root of the tree), and
calls one of the Controller class methods: “createTree()” (given
below).
public void createTree() {
root.addChild("B", "A");
root.addChild("C", "A");
root.addChild("D", "B");
root.addChild("E", "B");
root.addChild("F", "C");
root.addChild("G", "C");
root.addChild("H", "D");
root.addChild("I", "D");
root.addChild("J", "E");
root.addChild("K", "E");
root.addChild("L", "F");
root.printTree();
System.out.println("There are " + root.size() + " nodes in this
tree.\n");
}
The Controller class should also have a method (manipulateTree())
which contains the code to loop as long as
the user wants to, and perform the tasks desired by the user. The
Controller class should also have a method to
display the menu to the user.
The TreeDataStructure class should implement the ITreeDataStructure
interface (which is provided below).
Your TreeDataStructure class should have two constructors: one
which accepts only one String parameter (used
to create the root node which has no parent) and a second one which
accepts 2 parameters: a String (the ID of
the new node being created, and an ITreeDataStructure object (the
parent of this new node). The methods
addChild(), find(), printTree(), and size() in the
TreeDataStructure class must be implemented using recursion.
public interface ITreeDataStructure {
/**
* This method checks to see if a node with the parentID exists in
the tree.
* If not, it returns false after printing an appropriate message.
If the
* node exists, the method checks to see if it already has two
children. If
* it does the method returns false. Otherwise, it either adds the
new node
* as the parent node’s left child (if the parent has no children)
or as the
* right child (if the parent already has one child). A recursive
approach is
* used.
*
* @param ID The ID of the new node to be added to the tree.
* @param parentID The ID of the parent of the new node.
* @return true if new node was added successfully, false
otherwise.
*/
public boolean addChild(String ID, String parentID);
/**
* This method looks within the tree to find if “value” (the ID of
the node
* to be found) is contained in that subtree. As the search
progresses down
* the tree different nodes will be calling find().
*
* @param value a string (ID of a node) to be found in the
tree
* @return the node, if found.
*/
public ITreeDataStructure find(String value);
/**
* Returns the parent of this node.
*
* @return the parent of this node.
*/
public ITreeDataStructure getParent();
/**
* Returns the size of the tree.
*
* @return the size of the tree (or subtree) starting from this
node
* all the way down to the leaf nodes.
*/
public int size();
/**
* Returns a string with the IDs of this node and its immediate
children (if
* any) all on one line.
*
* @return a string with the IDs of this node and its immediate
children (if
* any).
*/
public String toString();
/**
* Returns the ID of this node.
*
* @return the String ID of this node.
*/
public String getId();
/**
* Uses recursion (and the toString() method) to print (on a line)
each
* node's ID and those of any children it has.
*/
public void printTree();
}
PROGRAM :
import java.util.HashMap;
import java.util.Map;
import java.util.*;
interface INode {
public boolean addChild(String ID, String parentID);
public INode find(String value);
public INode getParent();
public int size();
public String toString();
public String getId();
public void printTree();
public void printInInorder();
}
class TreeDataStructure implements INode {
private String data;
private TreeDataStructure left, right, parent;
public TreeDataStructure(){} // no argument constructor
public TreeDataStructure(String data) // one argument
constructor
{
this.data = data;
left = right = parent = null;
}
private TreeDataStructure newNode(String data)
{
TreeDataStructure temp = new TreeDataStructure(data);
return temp;
}
@Override
public boolean addChild(String ID, String parentID) {
return addNode(this, ID, parentID);
}
public boolean addNode(TreeDataStructure root, String id, String
parentId)
{
if(root==null)
return false;
if(root.data.equals(parentId))
{
if(root.left == null)
{
TreeDataStructure temp = newNode(id);
root.left = temp;
temp.parent = root;
return true;
}
else if (root.right == null)
{
TreeDataStructure temp = newNode(id);
root.right = temp;
temp.parent = root;
return true;
}
else {
System.out.println("Parent already has 2 children.");
return false;
}
}
return addNode(root.left, id, parentId) || addNode(root.right, id,
parentId);
}
@Override
public INode find(String value) {
INode node = findNode(this, value);
return node;
}
private TreeDataStructure findNode(TreeDataStructure root, String
node)
{
if(root != null){
if(root.data.equals(node)){
return root;
} else {
TreeDataStructure foundNode = findNode(root.left, node);
if(foundNode == null) {
foundNode = findNode(root.right, node);
}
return foundNode;
}
} else {
return null;
}
}
@Override
public INode getParent() {
return this.parent;
}
@Override
public int size() {
return getSize(this);
}
private int getSize(TreeDataStructure node)
{
if(node == null)
return 0;
return getSize(node.left) + getSize(node.right) + 1;
}
@Override
public String getId() {
return this.data;
}
@Override
public void printTree() {
print(this);
}
private void print(TreeDataStructure node) {
if (node == null)
return;
System.out.print(node.data);
if (node.left != null)
System.out.print(node.left.data);
if (node.right != null)
System.out.print(node.right.data);
System.out.println();
this.print(node.left);
this.print(node.right);
}
@Override
public void printInInorder()
{
printInorder(this);
}
public void printInorder(TreeDataStructure root)
{
if(root==null)
return;
System.out.print(root.data);
printInorder(root.left);
printInorder(root.right);
}
}
public class BinaryTree
{
public static void main(String args[])
{
TreeDataStructure root = new TreeDataStructure("A");
root.addChild("B", "A");
root.addChild("C", "A");
root.addChild("D", "B");
root.addChild("E", "B");
root.addChild("F", "C");
root.addChild("G", "C");
root.addChild("H", "D");
root.addChild("I", "D");
root.addChild("J", "E");
root.addChild("K", "E");
root.addChild("L", "F");
root.printTree();
System.out.println("There are " + root.size() + " nodes in this
tree.");
int input = 0;
Scanner scanner = new Scanner(System.in);
do {
System.out.println("Please select from one of the following
options:");
System.out.println("1. Add Node");
System.out.println("2. Tree Size");
System.out.println("3. Find Node");
System.out.println("0. Exit");
System.out.print("->");
input = scanner.nextInt();
switch (input)
{
case 1:
System.out.println("Please input the node you want to
add->");
String id = scanner.next();
System.out.println("Please input the parent node of " + id +
"->");
String parentId = scanner.next();
if(root.addChild(id, parentId)) {
System.out.println("Node successfully added!");
root.printTree();
}
break;
case 2:
System.out.println("Please input the root node->");
id = scanner.next();
INode temp = root.find(id);
if(temp != null) {
System.out.println("There are " + temp.size() + " nodes in that
tree");
temp.printInInorder();
System.out.println();
}
else
System.out.println("Root node " + id + " not present in the
tree!");
break;
case 3:
System.out.println("Please input the node you want to look
for->");
id = scanner.next();
if(root.find(id)!=null)
System.out.println("Node " + id + " found!");
else
System.out.println("Node " + id + " does not exist.");
break;
default:
System.out.println("Enter correct input data!!!");
break;
}
}while (input != 0);
}
}
THANK YOU!! Please vote