[Solved]Binarytreejava File Contains Implementation Binary Tree However Signatures Following Metho Q37124310
The BinaryTree.java file contains an implementation of BinaryTree. However, signatures for the following methods are providedbut their bodies are not defined.
• width(): should compute and return the width of the tree.
• breadthFirstTraverse(): should traverse the tree inbreadth-first order and return a string that represents thebreadth-first traversal sequence of the tree.
• postOrderTraverse():should traverse the tree in post order andreturn a string that represents the post order depth firsttraversal sequence of the tree.
• inOrderTraverse():should traverse the tree in order and returna string that represents the in order depth first traversalsequence of the tree.
You need to implement the bodies of the aforementioned methodsso that they perform the computation in accordance with what theyare meant for. For this task you must use your own implementationof queue, that can grow in size when necessary. You must NOT makeany other modifications in BinaryTree.java.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
import java.util.List;
import java.util.ArrayList;
public class BinaryTree<T>{
BinaryNode<T> root = null;
private T nullSymbol = null;
/**
* Default constructor
*/
public BinaryTree(){
}
/**
* This constructor is useful for testpurposes,
* not meant for use in general.
*
* Constructs a binary tree from a given validbreadth-first traversal sequence.
* @param seq is an array containing breadth-firsttraversal sequence of the nodes of a tree.
*/
public BinaryTree(T[] seq){
initFromBfsSequence(seq);
}
/**
* This constructor is useful for testpurposes,
* not meant for use in general.
*
* Constructs a binary tree from a given validbreadth-first traversal sequence.
* A given special symbol (nullSymbol) inthe sequence is interpreted as absence of node.
* During construction of the tree, whensuch a special symbol is encountered,
* that is considered to be an absent node,and thus no corresponding node is added to the tree.
*
* @param seq is an array containingbreadth-first traversal sequence of the nodes of a tree.
* @param nullSymbol is a special symbolin the given sequence that denotes absence of a node.
*/
public BinaryTree(T[] seq, T nullSymbol){
this.nullSymbol = nullSymbol;
initFromBfsSequence(seq);
}
private void initFromBfsSequence(T[] seq){
if(seq.length == 0)
throw newIllegalArgumentException(“Cannot build tree from emptysequence”);
if(seq[0].equals(nullSymbol))
throw newIllegalArgumentException(“Symbol for root cannot benullSymbol”);
List<BinaryNode<T>>nodes = new ArrayList<BinaryNode<T>>(seq.length);
this.root = newBinaryNode<T>(seq[0]);
nodes.add(root);
for(int i = 0; i <seq.length; i++){
if(nodes.get(i)== null){
handelNullParentNode(nodes, i,seq.length);
}else{
handleNonNullParentNode(nodes, i,seq);
}
}
}
// This method will handle the null nodes in theiteration of nodes.get(i) in initFromBfsSequence method.
private voidhandelNullParentNode(List<BinaryNode<T>> nodes,
intnullNodeIndex, int seqLength){
int leftIndex = (nullNodeIndex * 2)+ 1; // finding the left child index from formula
if(leftIndex < seqLength){
nodes.add(null);
intrightIndex = (nullNodeIndex * 2) + 2; // finding the right childindex from formula
if(rightIndex< seqLength){
nodes.add(null);
}
}
}
// This method will handle the non-null nodes inthe iteration of nodes.get(i) in initFromBfsSequence method.
private voidhandleNonNullParentNode(List<BinaryNode<T>>nodes,
int parentIndex, T[]seq){
int leftIndex = (parentIndex * 2) +1;
if(leftIndex < seq.length){//need to check if the index falls outdise of the list index
BinaryNode<T> leftNode = null;
if(!seq[leftIndex].equals(nullSymbol)){
leftNode = newBinaryNode<T>(seq[leftIndex]);
}
nodes.get(parentIndex).leftNode = leftNode;
nodes.add(leftNode);
intrightIndex = (parentIndex * 2) + 2;
if(rightIndex< seq.length){
BinaryNode<T> rightNode = null;
if(!seq[rightIndex].equals(nullSymbol)){
rightNode = newBinaryNode<T>(seq[rightIndex]);
}
nodes.get(parentIndex).rightNode =rightNode;
nodes.add(rightNode);
}
}
}
public int height(){
if (root == null) return0;
return root.height();
}
public int width(){
// TODO: Modify this method-body tocompute and return the width
// of the tree.
System.out.println(“Feature notimplemented yet, returning 0”);
return 0;
}
public String breadthFirstTraverse(){
// TODO: Modify this method-body toreturn a string corresponding
// to the bread-first-traversal ofthe tree
System.out.println(“Feature notimplemented yet, returning empty string”);
return “”;
}
public String preOrderTraverse(){
returnroot.preOrderTraverse().trim();
}
public String postOrderTraverse(){
returnroot.postOrderTraverse().trim();
}
public String inOrderTraverse(){
returnroot.inOrderTraverse().trim();
}
class BinaryNode<T>{
private T data = null;
private BinaryNode<T>leftNode = null;
private BinaryNode<T>rightNode = null;
public BinaryNode(T data){
this.data =data;
}
public String toString(){
return “” +data;
}
public BinaryNode<T>getLeftNode(){
returnthis.leftNode;
}
public BinaryNode<T>getRightNode(){
returnthis.rightNode;
}
public voidsetLeftNode(BinaryNode<T> node){
this.leftNode =node;
}
Expert Answer
Answer to The BinaryTree.java file contains an implementation of Binary Tree. However, signatures for the following methods are pr… . . .
OR
