Implement the class shown on the following slides. You can only use Java to solve this problem. You cannot use other language to do this work.

You need to implement BinaryTree() , BinaryTree(String d) ,BinaryTree(BinaryTree b1, String d, BinaryTree b2) ,BinaryTree(String t, String open, String close, String empty) , InorderIterator implements Iterator, PostorderIterator implements Iterator, Iterator inorder(), Iterator postorder() , String toString()

public class BinaryTree {

//Implements a Binary Tree of Strings

private class Node {

private Node left;

private String data;

private Node right;

private Node parent; // reference to the parent node

// the parent is null for the root node

private Node(Node L, String d, Node r, Node p) {

left = L;

data = d;

right = r;

parent = p;

}

}

private Node root;

public BinaryTree() {

// create an empty tree

}

public BinaryTree(String d) {

// create a tree with a single node

}

public BinaryTree(BinaryTree b1, String d, BinaryTree b2) {

// merge the trees b1 AND b2 with a common root with data d

}

public BinaryTree(String t, String open, String close, String empty) {

/*

* create a binary tree from the in order format discussed in class. Assume t is

* a syntactically correct string representation of the tree. Open and close are

* the strings which represent the beginning and end markers of a tree. Empty

* represents an empty tree. The example in class used ( ) and ! for open, close

* and empty respectively. The data in the tree will not include strings

* matching open, close or empty. All tokens (data, open, close and empty) will

* be separated By white space Most of the work should be done in a private

* recursive method

*/

}

public class InorderIterator implements Iterator {

// An iterator that returns data in the tree in an in order pattern

// the implementation must use the parent pointer and must not use an

// additional data structure

public InorderIterator() {

}

public boolean hasNext() {

}

public String next() {

}

public void remove() {

// optional method not implemented

}

}

public class PostorderIterator implements Iterator {

// An iterator that returns data in the tree in a post order pattern

// This implementation must use a stack and must not use the parent pointer

// You must use Javas stack class

public PostorderIterator() {

}

public boolean hasNext() {

}

public String next() {

}

public void remove() {

// optional method not implemented

}

}

public Iterator inorder() {

// return a new in order iterator object

}

public Iterator postorder() {

// return a new post order iterator object

}

public String toString() {

// returns the string representation of the tree using the in order format

// discussed in class. If the tree was created from a string use the

// the values of open, close and empty given to the constructor otherwise

// use (, ) and ! for open, close and empty respectively

// most of the work should be done in a recursive private method.

}

Stri open The tee wil be Stri open The tee wil be