Develop a Java application to implement a binary tree data structure. Atreedata structure starts from the top node, called theroot. Each node in the tree has a set of children, which are also nodes of the tree and can have children of their own, and so on. This keeps on going till we get to the bottom of the tree, to the “leaf” nodes. Each node in the tree, except for the root, has a parent. Abinarytree is a specialized form of a tree data structure in which each node in the tree hasat most two children.
A binary tree can be represented using the format in the example below. Each line contains at most three characters. The first character is the ID of the node itself. The next two characters are the child nodes. If a line has only 2 characters, then that node has only one child. If a line has one character only, then it is a leaf node (i.e., it has no children). Example
A B C
B D E
C F G
D H I
E J K
F L
G
H
I
J
K
L
The application should exhibit the following functionality (see the sample output provided):
·Display a menu to the user and request for the desired option.
- Based on the user’s input, request for additional information as follows:
oIf the user wants to add a node, request for the name / 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, userecursionto add the new node as the second child (right child) of the parent node.
·Display the new tree with the new node added. This should be done using arecursivemethod in your project (printTree() ).
·Display the menu options.
▪If the parent node has no children, userecursionto add the new node as the left child
of the parent node.
·Display the new tree with the new node added.
·Display the menu options.
oIf the user wants to know the size of the tree (i.e., the number of nodes in the tree or sub-tree), request for the name / ID of the node that is therootof the desired tree / 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. For example, the size of the sub-tree with root ‘B’ in Figure 2 above is 7.
▪Recursivelycount the number of nodes in the tree / sub-tree and display this with an appropriate message.
·Display the newly updated tree.
·Display the menu options.
oIf the user wants to find a node, request for the name / ID of the node to search for in the tree.
▪Searchrecursivelyfor the node in the tree; if the node is found, display an appropriate
message, otherwise, indicate that the node does not exist in the tree.
•Display the menu options.
oIf the user wants to exit, terminate the program.
A sample output (to be followed exactly) is included below.
Example Output
ABC
BDE
DHI
H
I
EJK
J
K
CFG
FL
L
G
There are 12 nodes in this tree.
Please select from 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->
P
Please input the parent node of P->
A
Parent already has 2 children.
Please select from 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->
P
Please input the parent node of P->
F
Node successfully added!
ABC
BDE
DHI
H
I
EJK
J
K
CFG
FLP
L
P
G
Please select from one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->2
Please input the root node->
F
There are 3 nodes in that tree
FLP
Please select from one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->3
Please input the node you want to look for->
P
Node P found!
P
Please select from one of the following options:
1. Add Node
2. Tree Size
3. Find Node
0. Exit
->3
Please input the node you want to look for->
N
Node N does not exist.
Please select from one of the following options: 1. Add Node
2. Tree Size
3. Find Node
0. Exit
->0
The main class in your application should be namedBinaryTree. This class should instantiate an instance of the second class – to be namedTreeDataStructure– and that instance should be used to call the appropriate methods to generate the initial tree, display the menu to the user and exhibit the functionality described above. Apart from the main method, the BinaryTree class should also have a method to print the menu options (void printMenu() ). You can copy and paste the code below into your main class to generate the initial tree.
public static voidmain(String[]args) {
TreeDataStructureroot=
root.addChild("B","A");
root.addChild("C","A");
root.addChild("D","B");
root.addChild("E","B");
newTreeDataStructure("A");
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");TheTreeDataStructureclass should implement theINodeinterface (which is provided below). The methodsaddChild(),find(),printTree(), andsize() in the TreeDataStructure class must be implementedrecursively.NOTE:Using recursion is one of the main objectives of this assignment. A solution that does not use recursion to implement the required functionality will earnzero points.Create an interface named INode within your package (following steps similar to how you would create a class) and copy and paste the interface code below into it.
public interfaceINode {
public booleanaddChild(StringID, StringparentID);
publicINode find(Stringvalue);
publicINode getParent();
public intsize();
publicString toString();
publicString getId();
public voidprintTree();
Hints
- It is important to store information about the parent of each node as part of that node’s internal structure. In addition, each node should have information about its’ children.
- You may represent the children of a node possibly using an array of nodes.