testbst.java

一个平时的小test,about arraylist and BinarySearchTree class的不同． 想知道他们之间不同的可以看看

import java.io.*;

class TreeNode<T1 extends Comparable<T1>,T2>
{
	private T1 key;
	private T2 val;
	public TreeNode <T1,T2>left;
	public TreeNode <T1,T2>right;
	public TreeNode()
	{
	}
 	public TreeNode(T1 key,T2 val)
	{
		this.key=key;
		this.val=val;
		left=null;
		right=null;
	}
	public void set(T1 key,T2 val)
	{
		
		this.key=key;
		this.val=val;
	}
	public T1 getKey()
	{
		return key;
	}
	public T2 getVal()
	{
		return val;
	}
	public void addNode(TreeNode<T1,T2> newNode)
	{
		if((newNode.getKey()).compareTo(key)<0)
		{
			if (left==null) 
			{
				left=newNode;
			}
			else
			{	left.addNode(newNode);
			}
		}
		else
			if((newNode.getKey()).compareTo(key)>0)
			{
				if(right==null)
				{
					right=newNode;
				}
				else
				{
					right.addNode(newNode);
				}
				
			}
		else
		{
			val=newNode.getVal();
		}
	}
	public void printNodes()
	{
		if(left!=null)
			left.printNodes();
		System.out.println("key:"+key+";value:"+val);
		if(right!=null)
			right.printNodes();
	}
}
class BinarySearchTree<T1 extends Comparable<T1>,T2>
{
	private TreeNode <T1,T2>root;
	public BinarySearchTree()
	{
		root=null;
	}
	public boolean find(T1 key)
	{
		TreeNode<T1,T2> current=root;
		while(current!=null)
		{
			int d=(current.getKey()).compareTo(key);
			if(d==0) return true;
			else if(d>0) current= current.left;
			else current=current.right;
		}
		return false;
	}
	public void put(T1 key,T2 val)
	{
		TreeNode<T1,T2> newNode=new TreeNode<T1,T2>();
		newNode.set(key,val);
		if(root==null) root=newNode;
		else root.addNode(newNode);
	}
	public T2 get(T1 key)
	{
		TreeNode<T1,T2> current=root;


		if(find(key)!=false)
		{	
			
			return (T2)current.getVal();
		}
		else
		{
			return null;
		}
	}
	public void print()
	{
		if(root!=null)
		 root.printNodes();
	}
}



public class TestBST
{
	public static void main(String arg[]) throws IOException
	{
		BinarySearchTree<String,String> bst=new BinarySearchTree<String,String>();
		bst.put("AA","100");
		bst.put("BB","88");
		bst.put("CC","66");
		bst.print();
		bst.put("DD","77");
		System.out.println("after it");
		bst.put("AA","55");
		bst.print();
		System.out.println("the value of the key AA is :");
		System.out.println("value:"+bst.get("AA"));
	}
}