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()){
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 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 addChild(BTNode p, BTNode l, BTNode r){
if(l!=null && r!=null) {
p.left=l;
p.right=r;
}
else if(l==null && r!=null) {
p.left=null;
p.right=r;
}
else if(l!=null && r==null) {
p.left=l;
p.right=null;
}
else {
p.left=null;
p.right=null;
}
}

public BTNode search( int k ) {
BTNode n = root;
while (n != null){
if ( k == n.key )
return n; // found
else{
if ( k < n.key )
n = n.left; // search left subtree
else
n = n.right; }
}// search right subtree
return null; // not found
}

}



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{
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;
}
}
}