cc150_4_4.java

package cc150_4_4;

import java.util.LinkedList;


public class ComDepth<Key extends Comparable<Key>>  {
	
	public Node root;
	public class Node{
		private Key key;
//		Default layer is 1
		private int layer =1;
		private Node left;
		private Node right;
		
		public Node(Key data){
			this.key = data;
			
		}
		
	}
	public ComDepth(Key[] keys){
		for(Key key: keys)
			put(key);
	}
	
	public void put(Key key){
		root = put(root,key);
	}
	
	public Node put(Node x, Key key){
		if(x == null) return new Node(key);
		int cmp = key.compareTo(x.key);
		if(cmp < 0) x.left = put(x.left,key);
		else if(cmp > 0) x.right = put(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 LinkedList CalDepth(LinkedList rst,Node root2, int idx){
		
		
			
		if(idx>=rst.size()) return rst;
		
//		if(idx == -1) rst.add(root2);
		System.out.println("Current node:"+ root2.key);
		
		if(root2.left != null){
			root2.left.layer = root2.layer +1;
			rst.add(root2.left);
		}
		if(root2.right!= null){
			root2.right.layer = root2.layer +1;
			rst.add(root2.right);
		}
		
//		System.out.println("Index node:"+ idx);
		if(idx>=rst.size()-1) {return rst;}
		else{
		return CalDepth(rst, (Node) rst.get(idx+1),idx+1);
		}
		
		
		
	}
	
	public void Pringlayer(LinkedList deplist, int layer){
		Node temp;
		int flag = 0;
		while(!deplist.isEmpty()){
			temp = (Node) deplist.pop();
			if(temp.layer == layer){
				System.out.print(temp.key+" ");
				flag ++;
			}
		}
		if(flag >0){
		System.out.println(" ");
	
		}
		else{
			System.out.println("Layer is too large");
		}
	}

	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Integer data[] = {7,4,9,2,5,8,10,1,3,6,11,0,15};
		/*						7
		 *                     / \
		 *                    /   \ 
		 *		     
		 *                  4       9
		 *                 / \     / \
		 *                2   5   8   10
		 *               / \   \       \
		 *              1   3   6       11
		 *             /				 \
		 *            0					 15 
		 */            
		ComDepth<Integer> test = new ComDepth<Integer>(data);
		test.printTree(test.root);
		System.out.println("");
		
	    LinkedList rst = new LinkedList();
	    rst.add(test.root);
	    rst = test.CalDepth(rst, test.root, 0);
	    
	    test.Pringlayer(rst, 4);

		

	}	

}