Implement the class shown on the following slides. The class implements a binary tree. At the top of the file include a comment that lists your name. Add a comment for each private method or private instance variable you add

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()

Using Java, Not C or other programming languages.

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