Java Help! Figure 1 displays a simple binary tree. In a binary tree, each node h

Question

Java Help!

Figure 1 displays a simple binary tree. In a binary tree, each node has, at most, 2 child nodes. Although we have not learned about this data structure yet, code for a SimpleTreeNode has been provided in the Stack Homework project available on Canvas. A SimpleTreeNode contains a value and it also contains refernces to two other SimpleTreeNodes: the left child and right child. So, for example, in Figure 1, the root node has a value of 1 and its left child is the 2 node and its right child is the 3 node. Similarly, the left child of the 2 node is the 4 node and the right child is the 5 node.

Test code has been provided in the TreePrintTester class to create the binary tree shown in Figure 1. This class will create a StackBasedTreePrinter, passing the root node of the tree into the constructor, and will then call the printTree method.

1. This method print out all the nodes of the tree exact;y pnce, using a stack implementation, starting with the root node.

·     *    To solve this problem, you will first need to put the root node (passed in via the constructor) onto the stack.

·       * You then need to implement some type of loop where the first step involves popping an item off the stack and printing it out.

·       * The remaining steps involve knowing what should be put on the stack next.

·    *     Please note that your code needs to work for any arbitrary binary tree, not just the specific tree shown in Figure 1. That is, I don’t want to just see a bunch of print statements where you hard-code the path from the root node into the print statement. So, for example, I don’t want to see something like this:

System.out.println(getRootNode().getLeftChildTreeNode().getRightChildTreeNode().getLeftChildTreeNode())

(Below are the Programs set out)

______________SimpleTreeNode__________

package problem1;

public class SimpleTreeNode<E> {
/************* CLASS VARIABLES ********************************************/
private E value = null; //Element value to be held in this node
private SimpleTreeNode<E> leftChildTreeNode = null;
private SimpleTreeNode<E> rightChildTreeNode = null;

/************* GETTERS AND SETTERS******************************************/
/**
* @return the value
*/
protected E getValue() {
  return value;
}
/**
* @param value the value to set
*/
protected void setValue(E value) {
  this.value = value;
}
/**
* @return the leftChildTreeNode
*/
protected SimpleTreeNode<E> getLeftChildTreeNode() {
  return leftChildTreeNode;
}
/**
* @param leftChildTreeNode the leftChildTreeNode to set
*/
protected void setLeftChildTreeNode(SimpleTreeNode<E> leftChildTreeNode) {
  this.leftChildTreeNode = leftChildTreeNode;
}
/**
* @return the rightChildTreeNode
*/
protected SimpleTreeNode<E> getRightChildTreeNode() {
  return rightChildTreeNode;
}
/**
* @param rightChildTreeNode the rightChildTreeNode to set
*/
protected void setRightChildTreeNode(SimpleTreeNode<E> rightChildTreeNode) {
  this.rightChildTreeNode = rightChildTreeNode;
}

/************* CONSTRUCTORS **************************************************/
public SimpleTreeNode(E value){
  setValue(value);
}
/************* METHODS ******************************************************/
@Override
public String toString() {
  return getValue().toString();
}
}

_____________StackBasedTreePrinter_________

package problem1;

import java.util.Stack;

/**
* Seraches through all of TreeNodes in a
* @author tpolk
*
*/
public class StackBasedTreePrinter<E>{
/************** CLASS VARIABLES ******************************************/
SimpleTreeNode<E> rootNode = null;
Stack<SimpleTreeNode<E>> stack = null;

/************** GETTERS AND SETTERS **************************************/
/**
* @return the rootNode
*/
protected SimpleTreeNode<E> getRootNode() {
  return rootNode;
}
/**
* @param rootNode the rootNode to set
*/
protected void setRootNode(SimpleTreeNode<E> rootNode) {
  this.rootNode = rootNode;
}
/**
* @return the stack
*/
protected Stack<SimpleTreeNode<E>> getStack() {
  if (stack == null){
   stack = new Stack<SimpleTreeNode<E>>();
  }
  return stack;
}

/************** CONSTRUCTORS *******************************************/
/**
* Creates a StackBasedTreeSearcher using the root tree node passed in.
* This assumes that the full tree to be searched has already been created.
* @param root
*/
public StackBasedTreePrinter(SimpleTreeNode<E> root){
  setRootNode(root);
}

/************** METHODS ************************************************/
/**
* Uses a stack to print out all of the nodes in a tree, starting at the root node
*/
public void printTree(){
  
  //THIS IS THE METHOD YOU NEED TO IMPLEMENT FOR PROBLEM 1A AND 1B. ONCE YOU HAVE TESTED YOUR CODE
  //TO VERIFY IT WORKS, COPY AND PASTE JUST THIS METHOD INTO YOUR HOEWORK SUBMISSION AS INDICATED
  //IN THE HOMEWORK INSTRUCTIONS. YOU ALSO NEED TO COPY AND PASTE THE OUTPUT INTO THE HOMEWORK
  //AS INDICATED IN THE INSTRUCTIONS (I.E., PROBLEM 1B)
}
}

_______________________TreePrintTester_________________---

package problem1;

public class TreePrintTester {

public static void main(String[] args) {
  //first create an entire tree that looks like this:
  //                         1
  //                      2     3
  //                    4   5      6
  //                   7   8    9    10
  //                          11 12

  SimpleTreeNode<String> tempNode = null;//used to temporarily hold a node
  SimpleTreeNode<String> root = new SimpleTreeNode<String>("1");
  root.setLeftChildTreeNode(new SimpleTreeNode<String>("2"));
  root.setRightChildTreeNode(new SimpleTreeNode<String>("3"));
  //now set node 2's children
  tempNode = root.getLeftChildTreeNode();//this is the 2 node
  tempNode.setLeftChildTreeNode(new SimpleTreeNode<String>("4"));
  tempNode.setRightChildTreeNode(new SimpleTreeNode<String>("5"));
  //now set node 3's children
  tempNode = root.getRightChildTreeNode();//this is the 3 node
  tempNode.setRightChildTreeNode(new SimpleTreeNode<String>("6"));//no left child for this node
  //now set node 4's children
  tempNode = root.getLeftChildTreeNode().getLeftChildTreeNode();//this is the 4 node
  tempNode.setLeftChildTreeNode(new SimpleTreeNode<String>("7"));//no right child for this node
  //now set node 5's children
  tempNode = root.getLeftChildTreeNode().getRightChildTreeNode();//this is the 5 node
  tempNode.setLeftChildTreeNode(new SimpleTreeNode<String>("8"));//no right child for this node
  //now set node 6's children
  tempNode = root.getRightChildTreeNode().getRightChildTreeNode();//this is the 6 node
  tempNode.setLeftChildTreeNode(new SimpleTreeNode<String>("9"));
  tempNode.setRightChildTreeNode(new SimpleTreeNode<String>("10"));
  //now set node 9's children
  tempNode = root.getRightChildTreeNode().getRightChildTreeNode().getLeftChildTreeNode();//this is the 9 node
  tempNode.setLeftChildTreeNode(new SimpleTreeNode<String>("11"));
  tempNode.setRightChildTreeNode(new SimpleTreeNode<String>("12"));
  
  StackBasedTreePrinter<String> stackPrinter = new StackBasedTreePrinter<String>(root);
  stackPrinter.printTree();
}

}

Explanation / Answer

Here is the code for you:

public void printTree(){
  
//THIS IS THE METHOD YOU NEED TO IMPLEMENT FOR PROBLEM 1A AND 1B. ONCE YOU HAVE TESTED YOUR CODE
//TO VERIFY IT WORKS, COPY AND PASTE JUST THIS METHOD INTO YOUR HOEWORK SUBMISSION AS INDICATED
//IN THE HOMEWORK INSTRUCTIONS. YOU ALSO NEED TO COPY AND PASTE THE OUTPUT INTO THE HOMEWORK
//AS INDICATED IN THE INSTRUCTIONS (I.E., PROBLEM 1B)
SimpleTreeNode<E> current = rootNode;   //Sets the root as current node.
while(true)
{
    while(current != null)   //Till current is not null.
    {
        stack.push(current);   //Pushes the curent node to stack.
        current = current.getLeftChildTreeNode();   //Make the left child current.
    }  
   if(current == null && !stack.empty()) //If current is null, and stack is not empty.
    {
        SimpleTreeNode<E> temp = stack.pop();   //Pop the top item of the stack.
        System.out.println(temp);   //Print the popped item.
        current = temp.getRightChildTreeNode();
    }
    if(current == null && stack.empty())//If there are no nodes to parse, and the stack is empty.
        return;
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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