Need some help for this method which is public BinaryTree(String t, String open,
ID: 3757247 • Letter: N
Question
Need some help for this method which is public BinaryTree(String t, String open, String close, String empty)
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
root = null;
}
public BinaryTree(String d) {
// create a tree with a single node
root = new Node(null, d, null, root);
}
public BinaryTree(BinaryTree b1, String d, BinaryTree b2) {
// merge the trees b1 AND b2 with a common root with data d
root = new Node(null, d, null, root); // creating new Node
root.left = b1.root;
root.right = b2.root;
b1.root.parent = root;
b2.root.parent = root;
}
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
*/
}
}
Stri open The tee wil beExplanation / Answer
Sorry, Couldn't post the JAVA code as my eclipse kept on crashing. (i dunno why). But here is the algorithm on which it works. If any difficulty understanding, comment me I will be there.
//Assumed open close and empty to be of one character
1. define a private function BinaryTree BTBuilder(String t, String open, String close, String empty) //Recursive Function
2. if(t.charAt(0)==empty.charAt(0) --> return null; //Base Case for recursive Function
//If false then root exist
//Checking for left Node
Node left;
3. if(t.charAt(1) == empty.charAt(0) ---> Node left = null;) // left node empty
//else left node exist and it will be an opening string.
4.using for loop find its appropriate closing string and save the index of the closing string.
5. Make a substring of opening and closing string and pass it in the recursive function.
i.e ---> left = BTBuilder(substring,open,close,empty) // it will give the value of left node.
6. Next ptr after the previous closing string will the value of the root. Store it the Node root.
7.Next ptr after root will be String for right Node.
//Checking for the right node
8.Now similarly like the left node, if (t.charAt(ptr) == empty.charAt(0)) {right = null;} // ptr is index after root
9.else do a recursive function for the right substring like done for the left.
right = BTBuilder(substring,open,close,empty);
//Initializations
10. root.left = left;
11. root.right = right;
12. return root;
13. finish of the BTBuilder
14. run it in the constructor
15. end
I hope it is helpful and understandable and very sorry for the code. It was verying frustating as I was half way through the code when it starts crashing.Because of the time limit, I cant redo it, Please comment for any help and all the best.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.