cc150_4_8.java

package cc150_4_8;


public class CheckSubtree<Key extends Comparable<Key>> {
	private Node root;
	class Node{
		private Key key;
		public Node left;
		public Node right;
		
		public Node(Key data){
			this.key = data;
		}
	}
	
	
	public CheckSubtree(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) 
		{
			Node temp = new Node(key);
			return temp;
		}
		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 boolean isSubtree(Node n1, Node n2){
		if(n2 == null) return true;
		if(n1 == null) return false;
		if(isIdentical(n1,n2)) return true;
		
		return isSubtree(n1.left,n2)||isSubtree(n1.right,n2);
	}
	
	
	
	private boolean isIdentical(Node n1, Node n2) {
		// TODO Auto-generated method stub
		if(n1 ==null && n2 == null) return true;
		if(n1==null || n2 == null) return false;
		if(n1.key != n2.key) return false;
		
		return isIdentical(n1.left,n2.left) && isIdentical(n1.right,n2.right);
	}

	public static void main(String[] args) {

	Integer[] data = { 7, 10, 4, 3, 1, 2, 8, 11 };
	CheckSubtree<Integer> test = new CheckSubtree<Integer>(data);
	Integer[] sub1 = { 3, 1, 2, 8, 11 };
	CheckSubtree<Integer> subtr1 = new CheckSubtree<Integer>(sub1);
	Integer[] sub2 = {};
	CheckSubtree<Integer> subtr2 = new CheckSubtree<Integer>(sub2);
	
	test.printTree(test.root);	
	
	test.printTree(subtr1.root);
	test.printTree(subtr2.root);
	
	System.out.println("");
	System.out.println(test.isSubtree(test.root, subtr1.root));

	System.out.println(test.isSubtree(test.root, subtr2.root));
	
	
	
	}

}