Notes

import java.util.*;

public class EXF5_37 {
public static Scanner scan = new Scanner(System.in);
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()){
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 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() { }

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 void postorder() { postorder(root); }
protected void postorder(BTNode n) {
if (n != null) {
postorder(n.left);
postorder(n.right);
visit(n);
}
}


public void insert() {
BTNode n = root;
Stack<BTNode> stk = new Stack<BTNode>();
char left,right;
// while (n != null) {
do {
System.out.print("Enter Left Child of " + n.key + " : ");
left=scan.next().charAt(0);
if (left!='0') n.left=new BTNode(left);
else n.left=null;
System.out.print("Enter Right Child of " + n.key + " : ");
right=scan.next().charAt(0);
if (right!='0') n.right=new BTNode(right);
else n.right=null;
if (n.right != null) stk.push(n.right); //stack right child
// stk.push(n); //then stack itself
if(n.left==null && n.right==null) {
n=stk.pop();
}
else n = n.left;

} while (n != null);//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;
// }
}
}



public static void main(String[] args) {
BT bt = new BT();
// bt.test();
// bt.postorder();
char ans='y';
for(;;){
System.out.print("Main MenunA. Insert NodenB. PreordernC. PostordernD. Inorder"
+ "nE. ExitnChoice: ");
char choice = scan.next().charAt(0);
char a=' ',b=' ',c=' ';
int i=0;
BTNode cn,bn,an=null,pn;
if (choice=='A' || choice=='a'){
do{
System.out.print("Enter root: ");
a=scan.next().charAt(0);
an=new BTNode(a);
bt.root=an;
bt.insert();
// if(i==0) {System.out.print("Enter root: ");
// a=scan.next().charAt(0);
// an=new BTNode(a);
// bt.root=an;}
// if(i>0) {System.out.print("Enter parent: ");
// a=scan.next().charAt(0);
// an=bt.search(a);
// }
// System.out.print("Enter left child: ");
// b=scan.next().charAt(0);
// bn=new BTNode(b);
// System.out.print("Enter right child: ");
// c=scan.next().charAt(0);
// cn=new BTNode(c);
// if(c=='0') cn=null;
// if(b=='0') bn=null;
// bt.addChild(an, bn, cn);
//
// i++;
System.out.print("Enter Again? (y/n)");
ans=scan.next().charAt(0);
if (ans=='n' || ans=='N') continue;
}while(ans == 'y' || ans =='Y');
}

else if (choice=='B' || choice=='b') {
bt.preorderIter();
System.out.print("nBack to main menu? (y/n)");
ans=scan.next().charAt(0);
if (ans=='y' || ans=='Y') continue;
else break;
}

else if (choice=='C' || choice=='c') {
bt.postorder();
System.out.print("nBack to main menu? (y/n)");
ans=scan.next().charAt(0);
if (ans=='y' || ans=='Y') continue;
else break;
}

else if (choice=='D' || choice=='d') {
bt.inorderIter();
System.out.print("nBack to main menu? (y/n)");
ans=scan.next().charAt(0);
if (ans=='y' || ans=='Y') continue;
else break;
}


else break;
}
}
}