Implement the class shown on the following slides. The class implements a binary
ID: 3750023 • Letter: I
Question
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
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 Java’s 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 beExplanation / Answer
// Fameetha Alambasha
// Program to Implement Binary Tree
Public Class BinaryTree {
// Implements a Binary tree of Strings
Private Class Node {
Private Node right;
Private Node left;
Private Node parent;
Private String data;
Private Node(Node L, String d, Node r, Node p) {
left = L;
right = r;
data = d;
parent = p;
}
}
Private Node root;
Public BinaryTree() {
root = null; // Empty binary tree - root points to nothing ie., Null
}
//Inserting a new Node
Public BinaryTree(String d) {
// this refer to currect object or current reference
this.data = d; // Node value
this.left = null; //Left pointer points to nothing
this.right = null; // right pointer points to nothing
}
Public BinaryTree(BinaryTree b1, String d, BinaryTree b2) {
if(b1 == null) { // To check of Tree 1 is empty. If so, return Tree 2
return b2;
}
if(b2 == null) { // To check Tree 2 is empty. If so, return Tree 1
return b1;
}
b1.data += b2.data; // Merging the data value of both Tree 1 and Tree 2
b1.left = BinaryTree(b1.left, d, b2.left); // recursive i.e, repatedly callling the same function to form left side of tree
b1.right = BinaryTree(b2.right, d, b2.right); // repeatedly calling same function to form right side of tree
return b1; // returning the merged binary tree
}
}