cc150_4_6.java

package cc150_4_6;



public class NodeSuccessor<Key extends Comparable<Key>> {

	private Node root;
	class Node{
		private Key key;
		public Node left;
		public Node right;
		public Node parent;
		
		public Node(Key data){
			this.key = data;
		}
	}
	
	public NodeSuccessor(Key[] keys, int flag){
		if(flag ==1){
			for(Key key: keys)
				put(key);
			}
		else{
			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);
			{
				Node temp = new Node(key);
				temp.parent = x;
				return temp;
			}
		if(Integer.valueOf(key.toString())%2 ==0) {
			x.left = put(x.left,key);
			x.left.parent = x;
			
		} 
		else {
			x.right = put(x.right,key);
			x.right.parent = x;
			}
		return x;
	}
	
	

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

	public void printTree(Node head){
		if(head == null) return;
		printTree(head.left);
		System.out.print(head.key + ", ");
		printTree(head.right);
		
	}
	
	
	public Node successor(Node node){
		
		System.out.println("current node is:"+node.key);
		if(node == null) return null;
		Node cur;
		if(node.right != null){
			
			cur = node.right;
			while(cur.left != null)
				cur = cur.left;
			return cur;
		}
		else{
			
			cur = node;
			
			while(cur.parent != null){
				
				if(cur.parent.left == cur)
					return cur.parent;
				cur = cur.parent;
				
			}
		}
		
		return null;
	}
	
	
	
	public static void main(String[] args) {
		/*	_______7______
	       /              \
	    __4__          __10
	   /     \        /     \
	  3              8       11
	 /             
	1           		
	 \
	  2
	
	
	*/
	Integer[] data = { 7, 10, 4, 3, 1, 2, 8, 11 };
	NodeSuccessor<Integer> test = new NodeSuccessor<Integer>(data,2);
	test.printTree(test.root);
	System.out.println("");
//	System.out.println(test.root.left.left.parent.key);
	System.out.println(test.successor(test.root.left.left).key);
	

    }
	

}