Implement getPostorderIterator() in BinaryTree.java. After running Main.java, th

ID: 3706093 • Letter: I

Question

Implement getPostorderIterator() in BinaryTree.java. After running Main.java, the output should be should be: d e b g f c a

First 2 codes are StackPackage, next 5 codes are TreePackage, and Last is Main. I appreaciate the help. Thank you very much!!!

package StackPackage;

import java.util.Arrays;
import java.util.EmptyStackException;

public class ArrayStack<T> implements StackInterface<T>
{
private T[] stack;
private int topIndex; // index of top entry
private static final int DEFAULT_CAPACITY = 50;
private static final int MAX_CAPACITY = 10000;

public ArrayStack()
{
this(DEFAULT_CAPACITY);
}

public ArrayStack(int initialCapacity)
{
checkCapacity(initialCapacity);

@SuppressWarnings("unchecked")
T[] tempStack = (T[])new Object[initialCapacity];
stack = tempStack;
topIndex = -1;
}

@Override
public T pop()
{
if(isEmpty())
{
throw new EmptyStackException();
}
else
{
T top = stack[topIndex];
stack[topIndex] = null;
topIndex--;
return top;
}
}

@Override
public void push(T newEntry)
{
ensureCapacity();
stack[topIndex + 1] = newEntry;
topIndex ++;
}

@Override
public T peek()
{
if(isEmpty())
{
throw new EmptyStackException();
}
else
{
return stack[topIndex];
}
}

@Override
public boolean isEmpty()
{
return topIndex < 0;
}

@Override
public void clear()
{
for(int i = 0; i <= topIndex; i++)
{
stack[i] = null;
}
topIndex = -1;
}

private void ensureCapacity()
{
if(topIndex == stack.length - 1)
{
int newLength = 2 * stack.length;
checkCapacity(newLength);
stack = Arrays.copyOf(stack, newLength);
}
}

private void checkCapacity(int capacity)
{
if (capacity > MAX_CAPACITY)
{
throw new IllegalStateException("Attempt to create a stack whose capacity exceeds allowed maximum");
}
}

@Override
public char setResult(int result)
{
return 0;
}

@Override
public int getResult()
{
return 0;
}
}

package StackPackage;

public interface StackInterface<T>
{
public void push(T newEntry);
public T pop();
public T peek();
public boolean isEmpty();
public void clear();
public char setResult(int result);
public int getResult();
}

package TreePackage;

class BinaryNode<T>
{
private T data;
private BinaryNode<T> leftChild;
private BinaryNode<T> rightChild;

public BinaryNode()
{
this(null);
}

public BinaryNode(T dataPortion)
{
this(dataPortion, null, null);
}

public BinaryNode(T dataPortion, BinaryNode<T> newLeftChild, BinaryNode<T> newRightChild)
{
data = dataPortion;
leftChild = newLeftChild;
rightChild = newRightChild;
}

public T getData()
{
return data;
}

public void setData(T newData)
{
data = newData;
}

public BinaryNode<T> getLeftChild()
{
return leftChild;
}

public void setLeftChild(BinaryNode<T> newLeftChild)
{
leftChild = newLeftChild;
}

public boolean hasLeftChild()
{
return leftChild != null;
}

public BinaryNode<T> getRightChild()
{
return rightChild;
}

public void setRightChild(BinaryNode<T> newRightChild)
{
rightChild = newRightChild;
}

public boolean hasRightChild()
{
return rightChild != null;
}

public boolean isLeaf()
{
return (leftChild == null) && (rightChild == null);
}

/** counts the nodes in the subtree rooted at this node
* @return The number of nodes in the subtree rooted at this node
*/
public int getNumberOfNodes()
{
int leftNumber = 0;
int rightNumber = 0;

if (leftChild != null)
{
leftNumber = leftChild.getNumberOfNodes();
}

if (rightChild != null)
{
rightNumber = rightChild.getNumberOfNodes();
}
return 1 + leftNumber + rightNumber;
}

/** Computes the height of the subtree rooted at this node
* @return The height of the subtree rooted at this node
*/
public int getHeight()
{
return getHeight(this);
}

private int getHeight(BinaryNode<T> node)
{
int height = 0;
if(node != null)
{
height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild()));
}
return height;
}

/** Copies the subtree rooted at this node
* @return The root of a copy of the subtree rooted at this node.
*/
public BinaryNode<T> copy()
{
BinaryNode<T> newRoot = new BinaryNode<>(data);
if(leftChild != null)
{
newRoot.setLeftChild(leftChild.copy());
}
if(rightChild != null)
{
newRoot.setRightChild(rightChild.copy());
}
return newRoot;
}
}

package TreePackage;

import java.util.Iterator;
import java.util.NoSuchElementException;
import StackPackage.*;

public class BinaryTree<T> implements BinaryTreeInterface<T>
{
protected BinaryNode<T> root;

public BinaryTree()
{
root = null;
}

public BinaryTree(T rootData)
{
root = new BinaryNode<>(rootData);
}

public BinaryTree(T rootData, BinaryTree<T> leftTree, BinaryTree<T> rightTree)
{
initializeTree(rootData, leftTree, rightTree);
}

@Override
public T getRootData()
{
if(!isEmpty())
{
return root.getData();
}
return null;
}

@Override
public int getHeight()
{
return root.getHeight();
}

@Override
public int getNumberOfNodes()
{
return root.getNumberOfNodes();
}

@Override
public Iterator<T> getPreorderIterator()
{
return null;
}

@Override
public Iterator<T> getPostorderIterator()
{
return null;
}

@Override
public void clear()
{
root = null;
}

@Override
public Iterator<T> getInorderIterator()
{
return new InOrderIterator();
}

@Override
public Iterator<T> getLevelOrderIterator()
{
return null;
}

@Override
public void setTree(T rootData)
{
setTree(rootData, null, null);
}

@Override
public void setTree(T rootData, BinaryTreeInterface<T> leftTree, BinaryTreeInterface<T> rightTree)
{
initializeTree(rootData, (BinaryTree<T>) leftTree, (BinaryTree<T>) rightTree);
}

private void initializeTree(T rootData, BinaryTree<T> leftTree, BinaryTree<T> rightTree)
{
root = new BinaryNode<>(rootData);

if((leftTree != null) && !leftTree.isEmpty())
root.setLeftChild(leftTree.root);
if((rightTree != null) && !rightTree.isEmpty())
{
if (rightTree != leftTree)
{
root.setRightChild(rightTree.root);
}
else
root.setRightChild(rightTree.root.copy());
}
if((leftTree != null) && (leftTree != this))
{
leftTree.clear();
}
if((rightTree != null) && (rightTree != this))
{
rightTree.clear();
}
}

@Override
public boolean isEmpty()
{
return root == null;
}

// traversal that doesn't use an iterator (for demonstration purposes only)
public void iterativeInorderTraverse()
{
StackInterface<BinaryNode<T>> nodeStack = new ArrayStack<>();
BinaryNode<T> currentNode = root;

while (!nodeStack.isEmpty() || (currentNode != null))
{
while (currentNode != null)
{
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
}

if (!nodeStack.isEmpty())
{
BinaryNode<T> nextNode = nodeStack.pop();

System.out.println(nextNode.getData());
currentNode = nextNode.getRightChild();
}
}
}

private class InOrderIterator implements Iterator<T>
{
private StackInterface<BinaryNode<T>> nodeStack;
private BinaryNode<T> currentNode;

public InOrderIterator()
{
nodeStack = new ArrayStack<>();
currentNode = root;
}

@Override
public boolean hasNext()
{
return !nodeStack.isEmpty() || (currentNode != null);
}

@Override
public T next()
{
BinaryNode<T> nextNode = null;

// find leftmost node with no left child
while(currentNode != null)
{
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
}

if(!nodeStack.isEmpty())
{
nextNode = nodeStack.pop();
currentNode = nextNode.getRightChild();
}
else
throw new NoSuchElementException();
return nextNode.getData();
}
}
}

package TreePackage;
public interface BinaryTreeInterface<T> extends TreeInterface<T>, TreeIteratorInterface<T>
{
/** Sets this binary tree to a new one-node binary tree
* @param rootData The object that is the data for the new tree's root*/
void setTree(T rootData);

/** Sets this binary tree to a new binary tree
* @param rootData The object that is the data for the new tree's root
* @param leftTree The left subtree of the new tree.
* @param rightTree The right subtree of the new tree. */
void setTree(T rootData, BinaryTreeInterface<T> leftTree, BinaryTreeInterface<T> rightTree);
}

package TreePackage;
public interface TreeInterface<T>
{
T getRootData();
int getHeight();
int getNumberOfNodes();
boolean isEmpty();
void clear();
}

package TreePackage;
import java.util.Iterator;
public interface TreeIteratorInterface<T>
{
Iterator<T> getPreorderIterator();
Iterator<T> getPostorderIterator();
Iterator<T> getInorderIterator();
Iterator<T> getLevelOrderIterator();

}

import TreePackage.BinaryTree;
import TreePackage.BinaryTreeInterface;
import TreePackage.TreeIteratorInterface;

import java.util.Iterator;

public class Main
{
public static void main(String[] args)
{
BinaryTreeInterface<String> dTree = new BinaryTree<>();
dTree.setTree("D", null, null);

BinaryTreeInterface<String> eTree = new BinaryTree<>();
eTree.setTree("E", null, null);

BinaryTreeInterface<String> gTree = new BinaryTree<>();
gTree.setTree("G", null, null);

BinaryTreeInterface<String> fTree = new BinaryTree<>();
fTree.setTree("F", null, gTree);

BinaryTreeInterface<String> bTree = new BinaryTree<>();
bTree.setTree("B", dTree, eTree);

BinaryTreeInterface<String> cTree = new BinaryTree<>();
cTree.setTree("C", fTree, null);

BinaryTreeInterface<String> aTree = new BinaryTree<>();
aTree.setTree("A", bTree, cTree);

Iterator<String> iterator = aTree.getInorderIterator();
while(iterator.hasNext())
{
System.out.print(iterator.next() + " ");
}
}
}

Explanation / Answer