Jva Needed! · * To solve this problem, you will first need to add the root node

Question

Jva Needed!

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

·     *    You then need to implement some type of loop where the first step involves printing off the next item in the list. By next, I mean that, if you have already printed off item 0, then the next item would be item 1. If you have already printed off item 1, then the next item would be item 2, etc. (HINT:   you will need to keep track of which items in the list you have already printed off and which ones have not been printed yet.)

·       * The remaining steps involve knowing what should be put on the list next and how to work your way systematically through the list.

·        * Please note that your code needs to work for any arbitrary binary tree, not just the specific tree shown in Figure 1.

·         *The purpose of this assignment is to get you to think more abstractly about the List data structure and how you might use it to efficiently traverse all the nodes in a tree.

Below are programs, needed for this problem

_______ListBasedTreePrinter______

package problem2;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
* Prints all of the nodes in a tree made of SimpleTreeNodes. Just need to
* pass in the root tree node. Uses a List to keep track of the nodes as
* it pricesses the tree.
* @author tpolk
*
*/
public class ListBasedTreePrinter<E>{
/************** CLASS VARIABLES ******************************************/
SimpleTreeNode<E> rootNode = null;
List<SimpleTreeNode<E>> list = null;

/************** GETTERS AND SETTERS **************************************/
/**
* @return the rootNode
*/
private SimpleTreeNode<E> getRootNode() {
  return rootNode;
}
/**
* @param rootNode the rootNode to set
*/
private void setRootNode(SimpleTreeNode<E> rootNode) {
  this.rootNode = rootNode;
}
/**
* @return the stack
*/
private List<SimpleTreeNode<E>> getList() {
  if (list == null){
   list = new ArrayList<SimpleTreeNode<E>>();
  }
  return list;
}

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

/************** METHODS ************************************************/
/**
* Uses a list 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 2A AND 2B. ONCE YOU HAVE TESTED YOUR CODE
  //TO VERIFY IT WORKS, COPY AND PASTE JUST THIS METHOD INTO YOUR HOMEWORK 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 2B)
}
}

_______-SimpleTreeNode__________

package problem2;

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();
}
}

_________TreePrintTester_________________

package problem2;

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"));
  
  ListBasedTreePrinter<String> stackPrinter = new ListBasedTreePrinter<String>(root);
  stackPrinter.printTree();
}

}

Explanation / Answer

Here is the code for printTree method:

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())
        return;
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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