Notes

public class BTree {
public static class Stack<T> {
private int top = 0;
private final static int stackMax=20;
// highest index of stk array
private Object[] stk = new Object[stackMax+1];
//Elements must be cast back.
public Stack() { // constructor
}

public boolean isEmpty(){
if (top==0) return true;
else return false;
}

public void push(T el) {
if(top==stackMax)
System.out.println("Stack push overflow error");
else top=top+1;
stk[top]=el;
}

public T pop(){
if(isEmpty()){
System.out.println("Stack push underflow error");
return null;
}
else top=top-1;
return(T)stk[top+1];
}

public T top(){
if(isEmpty()){
// System.out.println("Stack empty");
return null;
}
else return (T)stk[top];
}
}
public static class Queue<T> {
private int head, tail;
public final static int queueMax=100;
// highest index of circular queue array
private Object[] que; //Elements must be cast back.
public Queue() { // constructor
que = new Object[queueMax + 1];
// at most queueMax - 1 elements
clear();
}

public void clear(){
head=tail=1;
}

public boolean isEmpty() {
if (head == tail)
return true;
else
return false;
}

public boolean isFull() {
if (((head == (tail + 1)) || (head == 1)) && (tail==queueMax))
return true;
else
return false;
}

public void enqueue(T el) {
if(isFull()) System.out.print("Overflow");
else {
que[tail]=el;
tail=tail+1;
if (tail>queueMax) tail=1;
}
}

public T dequeue(){
if(isEmpty()) {
System.out.print("underflow");
return null;
}
else {
T deqElt = (T) que[head];
head=head+1;
if (head>queueMax) head=1;
return deqElt;
}
}
// other methods

public void printAll() { // you can use this for toString()
while(!isEmpty()){
System.out.print(dequeue()+ " ");
}
}
}

public static class BTNode {
protected char key;
protected BTNode left, right;

public BTNode() {
key = 0; left = right = null;
}

public BTNode(char i) {
this(i,null,null);
}

public BTNode(char i, BTNode l, BTNode r) {
key = i; left = l; right = r;
}
}

public static class BT { // same package as BTNode
protected BTNode root = null;
public BT() { }

public void breadthFirst() {
BTNode p = root;
Queue<BTNode> q = new Queue<BTNode>();
if (p != null) {
q.enqueue(p);
while (!q.isEmpty()) {
p = q.dequeue();
visit(p);
if (p.left != null) q.enqueue(p.left);
if (p.right != null) q.enqueue(p.right);
}
}
}

protected void visit(BTNode n) {
System.out.print( n.key + " " );
}

public void test(){
BTNode I = new BTNode('I');
BTNode H = new BTNode('H', I, null);
BTNode G = new BTNode('G');
BTNode F = new BTNode('F');
BTNode E = new BTNode('E',F,G);
BTNode D = new BTNode('D',E,H);
BTNode C = new BTNode('C');
BTNode B = new BTNode('B', C, null);
BTNode A = new BTNode('A', B, D);
root = A;
}

public void preorderIter() {
BTNode n = root;
Stack<BTNode> stk = new Stack<BTNode>();
if (n != null) {
stk.push(n);
while (!stk.isEmpty()) {
n = stk.pop();
visit(n);
if (n.right != null) stk.push(n.right); //right subtree
if (n.left != null) stk.push(n.left); //after left subtree
}
}
}

public void inorderIter() {
BTNode n = root;
Stack<BTNode> stk = new Stack<BTNode>();
while (n != null) {
while (n != null) {
if (n.right != null) stk.push(n.right); //stack right child
stk.push(n); //then stack itself
n = n.left;
} //traverse left subtree
n = stk.pop(); //no left child
while (!stk.isEmpty() && (n.right == null)) {
visit(n); //visit it and all
n = stk.pop();
} //nodes w/o right child
visit(n); //1st node w/ right child or last node
if (!stk.isEmpty()) n = stk.pop(); //traverse right subtree
else n = null;
}
} //end iteration or return

}



public static void main(String[] args) {
BT bt = new BT();
bt.test();
bt.inorderIter();

}
}