Objective Replacing recursive calls programming technique wi

Objective: Replacing recursive calls programming technique with using Stack data structure

Modify the StringTree.java to add method to traversal the tree using java.util.Stack instead of recursion. Use the same inventory.txt file as input for the database. At the end, display the tree use this method.

Provided PowerPoint:

Binary (Search) Trees Traversal

Inorder traversal:

With inorder traversal, the left subtree of current node is visit first, then the current node then finally the right subtree of current node. The inorder traversal displays all the nodes in a BST in increase order.

Postorder traversal:

With postorder traversal, the left subtree is visit first, then the right subtree and finally the current node itself.

Preorder Traversal:

With preorder traversal, the current node is visited first, then the left subtree and finally the right subtree.

Provided Code:

/** Source code example for \"A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)\"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/

/** ADT for binary tree nodes */
public interface BinNode {
/** Get and set the element value */
public E element();
public void setElement(E v);

/** @return The left child */
public BinNode left();

/** @return The right child */
public BinNode right();

/** @return True if a leaf node, false otherwise */
public boolean isLeaf();
}

//********************************************************************
// StringTree.java   
//
//********************************************************************

import java.util.*;

public class StringTree
{
private Node root;

//----------------------------------------------------------------
// Creates an initially empty tree.
//----------------------------------------------------------------
public StringTree()
{
root = null;
}

//----------------------------------------------------------------
// Adds a string to the tree.
//----------------------------------------------------------------
public void addString (String str)
{
root = addStringToSubTree(str, root);
}

//----------------------------------------------------------------
// Adds a string to the subtree with the given root node
//----------------------------------------------------------------
private Node addStringToSubTree (String str, Node node)
{
Node result = node;
if (node == null)
result = new Node(str);
      
// If the new string comes before the string in the node, add
// the new string to the left child. Otherwise, add it to the
// right child.
else
if (str.compareTo(node.value) < 0)
node.left = addStringToSubTree(str, node.left);
else
node.right = addStringToSubTree(str, node.right);

return result;
}

//----------------------------------------------------------------
// Prints the result of a depth-first traversal of the tree using
// recursion.
//----------------------------------------------------------------
public void traverseWithRecursion()
{
traverseWithRecursion(root);
}

//----------------------------------------------------------------
// Prints the elements in the specified tree using recursion.
//----------------------------------------------------------------
private void traverseWithRecursion (Node node)
{
if (node != null)
{
traverseWithRecursion (node.left);

System.out.print (node.value+\" \");

traverseWithRecursion (node.right);
}
}
}

//********************************************************************
// Node for a binary tree of Strings.
//********************************************************************
class Node
{
public String value;
public Node left;
public Node right;

public Node (String value)
{
this.value = value;
this.left = left;
this.right = right;
}
}

/** Source code example for \"A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)\"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/

/** The Dictionary abstract class. */
public interface Dictionary {

/** Reinitialize dictionary */
public void clear();

/** Insert a record
@param k The key for the record being inserted.
@param e The record being inserted. */
public void insert(Key k, E e);

/** Remove and return a record.
@param k The key of the record to be removed.
@return A maching record. If multiple records match
\"k\", remove an arbitrary one. Return null if no record
with key \"k\" exists. */
public E remove(Key k);

/** Remove and return an arbitrary record from dictionary.
@return the record removed, or null if none exists. */
public E removeAny();

/** @return A record matching \"k\" (null if none exists).
If multiple records match, return an arbitrary one.
@param k The key of the record to find */
public E find(Key k);

/** @return The number of records in the dictionary. */
public int size();
}

/** Source code example for \"A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)\"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/

/** Binary tree node implementation: Pointers to children
@param E The data element
@param Key The associated key for the record */
class BSTNode implements BinNode {
private Key key; // Key for this node
private E element; // Element for this node
private BSTNode left; // Pointer to left child
private BSTNode right; // Pointer to right child

/** Constructors */
public BSTNode() {left = right = null; }
public BSTNode(Key k, E val)
{ left = right = null; key = k; element = val; }
public BSTNode(Key k, E val,
BSTNode l, BSTNode r)
{ left = l; right = r; key = k; element = val; }

/** Get and set the key value */
public Key key() { return key; }
public void setKey(Key k) { key = k; }

/** Get and set the element value */
public E element() { return element; }
public void setElement(E v) { element = v; }

/** Get and set the left child */
public BSTNode left() { return left; }
public void setLeft(BSTNode p) { left = p; }

/** Get and set the right child */
public BSTNode right() { return right; }
public void setRight(BSTNode p) { right = p; }

/** @return True if a leaf node, false otherwise */
public boolean isLeaf()
{ return (left == null) && (right == null); }
}

Text file:

CT16C1288B
DT14B1225F
MI15B1250A
MI15B1251A
HO03N1095A
HY07D1095BQ
KI04D2593C
DG12A1240AQ
HY03G2593BQ
TO30A1310A
HO03N1095AQ
HO01H1351C
HO01H1350C
FT18A1288B
LR15A1000A
BM12E1000A
VW02B3113A
NI23H1230AQ
LX03D2503A
LX03D2502A
LX03D2502A
VW22A3113B
VW22B3113A

Solution

import java.util.*;
public class StringTree
{
private Node root;
//----------------------------------------------------------------
// Creates an initially empty tree.
//----------------------------------------------------------------
public StringTree()
{
root = null;
}
//----------------------------------------------------------------
// Adds a string to the tree.
//----------------------------------------------------------------
public void addString (String str)
{
root = addStringToSubTree(str, root);
}
//----------------------------------------------------------------
// Adds a string to the subtree with the given root node
//----------------------------------------------------------------
private Node addStringToSubTree (String str, Node node)
{
Node result = node;
if (node == null)
result = new Node(str);
  
// If the new string comes before the string in the node, add
// the new string to the left child. Otherwise, add it to the
// right child.
else
if (str.compareTo(node.value) < 0)
node.left = addStringToSubTree(str, node.left);
else
node.right = addStringToSubTree(str, node.right);
return result;
}
//----------------------------------------------------------------
// Prints the result of a depth-first traversal of the tree using
// recursion.
//----------------------------------------------------------------
public void traverseWithRecursion()
{
traverseWithRecursion(root);
}
//----------------------------------------------------------------
// Prints the elements in the specified tree using recursion.
//----------------------------------------------------------------
private void traverseWithRecursion (Node node)
{
if (node != null)
{
traverseWithRecursion (node.left);
System.out.print (node.value+\" \");
traverseWithRecursion (node.right);
}
}
private void traverseWithStack(){
   Stack<Node> dataStack = new Stack<Node>();
   Node node = root;
     
   //first node to be visited will be the left one
   while (node != null) {
       dataStack.push(node);
       node = node.left;
   }
   // traverse
   while (dataStack.size() > 0) {
     
       // visit the top node
       node = dataStack.pop();
       System.out.print(node.data + \" \");
       if (node.right != null) {
           node = node.right;
             
           // the next node to be visited is the leftmost
           while (node != null) {
               dataStack.push(node);
               node = node.left;
           }
       }
   }
}
}