Please solve the next program while using the main method provide and make sure to get the EXACT output provide as well.

Again, start with the tree.java program and make a tree from characters typed by the user. This time, make a complete treeone that is completely full except possibly on the right end of the bottom row. The characters should be ordered from the top down and from left to right along each row, as if writing a letter on a pyramid. (This arrangement does not correspond to any of the three traversals we discussed in this chapter.) Thus, the string ABCDEFGHIJ would be arranged as A B C D E F G H I J One way to create this tree is from the top down, rather than the bottom up as in the previous two Programming Projects. Start by creating a node which will be the root of the final tree. If you think of the nodes as being numbered in the same order the letters are arranged, with 1 at the root, then any node numbered n has a left child numbered 2*n and a right child numbered 2*n+1. You might use a recursive routine that makes two children and then calls itself for each child. The nodes dont need to be created in the same order they are arranged on the tree. As in the previous Programming Projects, you can jettison the search-tree routines from the Tree class.

You must use this main method to solve this question:

public static void main(String[] args) throws IOException

{

int value;

System.out.print("Enter character string for tree: ");

String str = getString();

Tree theTree = new Tree(str);

while(true)

{

System.out.print("Enter first letter of ");

System.out.print("show or traverse: ");

int choice = getChar();

switch(choice)

{

case 's':

theTree.displayTree();

break;

case 't':

System.out.print("Enter type 1, 2 or 3: ");

value = getInt();

theTree.traverse(value);

break;

default:

System.out.print("Invalid entry ");

} // end switch

} // end while

} // end main()

The output MUST be this one below, in form and content. Thank you

Enter character string for tree: ABCDEFGHIJ

Enter first letter of show or traverse: s

......................................................

(A)

(B) (C)

(D) (E) (F) (G)

(H) (I) (J) --- --- --- --- ---

......................................................

Enter first letter of show or traverse: t

Enter type 1, 2 or 3: 1

Preorder traversal: (A)(B)(D)(H)(I)(E)(J)(C)(F)(G)

Enter first letter of show or traverse: t

Enter type 1, 2 or 3: 2

Inorder traversal: (H)(D)(I)(B)(J)(E)(A)(F)(C)(G)

Enter first letter of show or traverse: t

Enter type 1, 2 or 3: 3

Postorder traversal: (H)(I)(D)(J)(E)(B)(F)(G)(C)(A)

Enter first letter of show or traverse: