import java.io.*; public class BinaryTree { private Node root = null; private in

Question

import java.io.*;

public class BinaryTree {

private Node root = null;

private int size = 0;

private static class Node {

private Character element;

private Node left, right, parent;

Node(Character e) {

element = e;

}

public Character getElement() {

return element;

}

public Node leftChild() {

return left;

}

public Node rightChild() {

return right;

}

public Node parent() {

return parent;

}

}

BinaryTree (String fileName) {

}

Node getRoot() {

return root;

}

/*public String inOrderTraversalRecursive(Node n) {

// insert your code here

}

public String preOrderTraversalRecursive(Node n) {

// insert your code here

}

public String stairCaseTraversalNonRecursive(Node n) {

// insert your code here

}

public int numberOfLeavesRecursive(Node n) {

// insert your code here

}*/

public static void main(String[] args) {

//Sample test statements; we can also create a tester

// class to test your program.

BinaryTree myTree = new BinaryTree("B1.txt");

/*System.out.println("Inorder traversal: " + myTree.inOrderTraversalRecursive(myTree.getRoot()));

System.out.println("Preorder traversal: " + myTree.preOrderTraversalRecursive(myTree.getRoot()));

System.out.println("Staircase traversal: "+ myTree.stairCaseTraversalNonRecursive(myTree.getRoot()));

System.out.println("Number of leaves: "+ myTree.numberOfLeavesRecursive(myTree.getRoot()));*/

}

}

BELOW IS THE B1 TEXT - Test input file

G 2

S 1
V 0
U 10
Q 00
J 11
E 110
H 000
D 001

1 Description Implement a class in Java named BinaryTree containing the following methods. Partial code and a sample input file is provided. Please download from the Canvas and use them. 1. BinaryTree(String fileName); This constructor reads a binary tree encoding from an input file fileName and builds the unique binary tree. If the tree has n nodes, then the file has lines, one line for every node. Each line contains two elements the first element is the node content and the second element is the path from the root to this node. This path is represented using Os and 1s. A 0 represents 'left and a 1 represents 'right. Following is a binary tree and its corresponding file representation. For the root node, we store a 2 next to it M 2 K 1 A 0 T 10 Y 00 P 11 Z 110 2. public String inOrderTraversalRecursive (Node n); This is a recursive method which returns the inorder traversal of a binary tree. For example, for the above binary tree, the return string must be Y AM TKZ P 3. public String pre0rderTraversalRecursive(Node n); This is a recursive method which returns the preorder traversal of a binary tree. For example, for the above binary tree, the return string must be M A Y KT P Z. 4, public String starcas eTraversa?NonRecursive(Node n); This is a non-recursive method which returns the staircase traversal of a binary tree, as discussed in the class. For example, for the above binary tree, the return string must be M AKYTP Z. Hint: a ueue is required 5. public int numberOfLeavesRecursive(Node n); This is a recursive method which returns the number of leaves in the tree. For example, for the above binary tree, the method must return 3 Unless stated, in the programs of this course you are not allowed to use any existing Java library and/or external packages for solving the problem. You should write everything from the scratch. You will receive zero if your program does not compile or it is found that you have copied code from some other source without any reference 2 Deliverable Upload the file BinaryTree.java only. You are not allowed to submit any other file. Your java code should be properly indented and nicely commented. Feel free to use additional helper methods, if required.

Explanation / Answer

import java.io.*;

public class BinaryTree {

private Node root = null;

private int size = 0;

private static class Node {

private Character element;

private Node left, right, parent;

Node(Character e) {

element = e;

}

public Character getElement() {

return element;

}

public Node leftChild() {

return left;

}

public Node rightChild() {

return right;

}

public Node parent() {

return parent;

}

}

BinaryTree (String fileName) {

}

Node getRoot() {

return root;

}

public String inOrderTraversalRecursive(Node n) {

// insert your code here
if(n==null)
return;
inOrderTraversalRecursive(n.leftChild());
System.out.println(n.getElement());
inOrderTraversalRecursive(n.rightChild());

}

public String preOrderTraversalRecursive(Node n) {

// insert your code here
if(n==null)
return;
System.out.println(n.getElement());
preOrderTraversalRecursive(n.leftChild());
preOrderTraversalRecursive(n.rightChild());
}

public String stairCaseTraversalNonRecursive(Node n) {

// insert your code here
Queue<Node> queue = new LinkedList<Node>();
queue.add(n);
while (!queue.isEmpty())
{
Node temp = queue.poll();//to remove present head
System.out.print(temp.data + " ");
if (temp.leftChild() != null) {
queue.add(temp.left);
}
if (temp.rightChild() != null) {
queue.add(tempNode.right);
}
}
}

public int numberOfLeavesRecursive(Node n) {

// insert your code here
if(n==null)
return 0;
if(n.leftChild()==null && n.rightChild()==null)
return 1;
numberOfLeavesRecursive(n.leftChild())+numberOfLeavesRecursive(n.rightChild());

}

public static void main(String[] args) {

//Sample test statements; we can also create a tester

// class to test your program.

BinaryTree myTree = new BinaryTree("B1.txt");

/*System.out.println("Inorder traversal: " + myTree.inOrderTraversalRecursive(myTree.getRoot()));

System.out.println("Preorder traversal: " + myTree.preOrderTraversalRecursive(myTree.getRoot()));

System.out.println("Staircase traversal: "+ myTree.stairCaseTraversalNonRecursive(myTree.getRoot()));

System.out.println("Number of leaves: "+ myTree.numberOfLeavesRecursive(myTree.getRoot()));*/

}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.