cc150_4_5.java

package cc_150_4_5;

import java.util.Stack;



public class CheckTree<Key extends Comparable<Key>> {
	
	private Node root;
	public class Node{
		private Key key;
		private Node left;
		private Node right;
		
		public Node(Key data){
			this.key = data;
		}
		
	}

	public CheckTree(Key[] keys, int BT){
		if(BT==1){
		for(Key key: keys)
			put(key);
		}
		else if(BT == 2){
			for(Key key: keys)
			BTput(key);		
		}
	}
	
	
	
	public void put(Key key){
		
		root = put(root,key);
	}
	
	public Node put(Node x, Key key){
		if(x == null) {
//			System.out.println("Put Key new Node: "+key);
			return new Node(key);}
		
		if(Integer.valueOf(key.toString())%2 ==0) {
			x.left = put(x.left,key);
			
		} 
		else {
			x.right = put(x.right,key);
			
			}
		return x;
	}
	
	

	
	public void BTput(Key key){
		root = BTput(root,key);
	}
	
	public Node BTput(Node x, Key key){
		if(x == null) return new Node(key);
		int cmp = key.compareTo(x.key);
		if(cmp < 0) x.left = BTput(x.left,key);
		else if(cmp > 0) x.right = BTput(x.right,key);
		return x;
	}
	
	

	public void printTree(Node head){
		if(head == null) return;
		printTree(head.left);
		System.out.print(head.key + ", ");
		printTree(head.right);
		
	}
	
	
	public boolean isBT(){

		Stack<Node> stack = new Stack<>();
		
		Node cur = this.root;
		Key temp = null;
		
		while(cur !=null || !stack.isEmpty()){
			while(cur != null){
				stack.push(cur);
				cur = cur.left;
			}
			
			if(!stack.isEmpty()){
				cur = stack.pop();
				if(temp !=null && cur.key.compareTo(temp)<0){
					return false;
				}
				temp = cur.key;
				cur = cur.right;
			}
		}
		
		
		return true;
	}


	public static void main(String[] args) {
	/*	_______7______
	       /              \
	    __10__          ___3
	   /      \        /    \
	   4                     1
	   /             /
	   2          1  11 		*/
	Integer[] data = { 7, 10, 4, 3, 1, 2, 8, 11 };
	CheckTree<Integer> test = new CheckTree<Integer>(data,1);
	test.printTree(test.root);
	System.out.println("");
	System.out.println(test.root.key);
	
	/*	_______7______
	       /              \
	    __4__          __10
	   /     \        /     \
	  3              8       11
	 /             
	1           		
	 \
	  2
	
	
	*/
	CheckTree<Integer> testbt = new CheckTree<Integer>(data,2);
	test.printTree(testbt.root);
	System.out.println("");
	System.out.println(testbt.root.key);
	System.out.println(test.isBT());
    }
	

}