简单的二叉搜索树 java实现

二叉搜索树java实现，不具备平衡功能(非平衡二叉搜树)

节点类 BinNode

package tree;

public class BinNode <T>
{
	private T data;
	private BinNode<T> left;
	private BinNode<T> right;
	
	
	public BinNode()
	{
		
	}
	
	int height()
	{
		return 0;
	}
	
	public BinNode(T data)
	{
		this.data = data;
	}
	
	public void setValue(T data)
	{
		this.data = data;
	}
	
	public T value()
	{
		return data;
	}
	public void setLeft(BinNode left)
	{
	  this.left = left;	
	}
	
	public void setRight(BinNode right)
	{
		this.right = right;
	}
	
	public BinNode left()
	{
		return left;
	}
	public BinNode right()
	{
		return right;
	}
}

树类 BinarySerachTree

package tree;

import java.util.Iterator;
import java.util.Random;

import list.LinkList;

/**
 * 二叉查找树
 * 左子树<根<=右子树
 * 插入
 * 删除
 * 查找
 * 
 * a节点是否为b的祖先
 * b是否为a的子节点//找b的路径 然后看其中是否有a 直接在a中查找
 * 
 * 非递归遍历
 * 前序 VLR
 * 中序 LVR
 * 后序 LRV
 * 
 * 如何保证多线程安全?  不保证
 * @author junfeng.chen
 *
 */
public class BinarySerachTree<T> implements Iterator
{
	private BinNode<Comparable> root;
    private int count;
	public BinarySerachTree()
	{
	}
	
	public int height()
	{
		if(root!=null)
		{
			BinNode left = 	root.left();
			BinNode right = root.right();
			int hleft = getHeight(left);
			int hright = getHeight(right);
			int height = hleft>hright?hleft:hright;
			return height+1;
		}
		return 0;
	}
	
	private int getHeight(BinNode root)
	{
		if(root!=null)
		{
			BinNode left=root.left();
			BinNode right = root.right();
			int hleft = getHeight(left);
			int hright = getHeight(right);
			int height = hleft>hright?hleft:hright;
			return height+1;
		}
		else
		{
		  return 0;
		}

	}
	public int count()
	{
		return count;
	}
	@SuppressWarnings("unchecked")
	public	void add(Comparable data)
	{
		if(data==null)
			return;
		if(root==null)
		{
			root = new BinNode<Comparable>();
			root.setValue(data);
		}
		else
		{
			BinNode node = new BinNode();
			node.setValue(data);
			BinNode<Comparable> pnode = findPNode(root,data);
			if(pnode.value().compareTo(data)>0)//data<pnode -->left
				pnode.setLeft(node);
			else
				pnode.setRight(node);
		}
		count++;
	}
	
	@SuppressWarnings("unchecked")
	private BinNode findPNode(BinNode<Comparable> root,Comparable data)
	{
		/**
		 * 与根比较 
		 * if data>=root
		 * 则查看右子树 如果右子树不存在 则返回根
		 *                     否则 在右子树中查找
		 *else
		 * 则查找左子树  如果左子树存在 则返回根
		 *                      否则 在左子树中查找                    
		 */
		BinNode left = root.left();
		BinNode right = root.right();
		Comparable value_root = root.value();
		if(data.compareTo(value_root)>=0)//右子树
		{
			if(right==null)
				return root;
			else
			{
				return findPNode(right,data);
			}
		}
		else//左子树
		{
			if(left==null)
				return root;
			else
				return findPNode(left,data);	
		}
		
	}
	
	public boolean exists(Comparable data)
	{
		/**
		 * 找到一个与之相等的值
		 * 未找到相等的节点
		 * 给定一个节点 查找指定值
		 * 
		 * 
		 * if data== node.value
		 *   return true;
		 * if data>node.value
		 *  if(node.left!=null)
		 *   return  find in node.left
		 *  else
		 *   return false;
		 *  else
		 *   if (node.right !=null)
		 *   return find in node.right;
		 *   else
		 *   return false;
		 * 
		 * 
		 */
		BinNode node = findNode(root,data);
		return node!=null;
	}
	
	private BinNode findNode(BinNode root,Comparable data)
	{
		/*if(data.compareTo(root.value())==0)
			return root;
		if(data.compareTo(root.value())>0)
		{
			if(root.right()!=null)
				return findNode(root.right(),data);
			else
				return null;
		}
		else
		{
			if(root.left()!=null)
				return findNode(root.left(),data);
			else
				return null;
		}*/
		
		boolean found = false;
		BinNode<Comparable> serach_node = root;
		while(!found&&serach_node!=null)
		{
			if(serach_node.value().compareTo(data)>0)
				serach_node = serach_node.left();
			else if(serach_node.value().compareTo(data)<0)
				serach_node = serach_node.right();
			else
				found = true;
		}
		if(found)
		return serach_node;
		else
		return null;
		
		
	}
	
	private BinNode findNode(BinNode<Comparable> root,Comparable data,LinkList<Comparable> path_list)
	{
		path_list.append(root.value());
		if(data.compareTo(root.value())==0)
			return root;
		if(data.compareTo(root.value())>0)
		{
			if(root.right()!=null)
				return findNode(root.right(),data,path_list);
			else
				return null;
		}
		else
		{
			if(root.left()!=null)
				return findNode(root.left(),data,path_list);
			else
				return null;
		}
	}
	
	/**
	 * 
	 * 
	 * 删除一个节点
	 * 分为3种情况
	 * 1.删除的节点为叶节点，只要将该节点父节点的对应指针设为空即可
	 * 2.该节点有一个子节点，将该节点的位置又其子节点代替
	 * 3.该节点有两个子节点，则该节点的位置用其中序后继代替
	 * @param data
	 */
	public void delete(Comparable data)
	{
		boolean found = false;
		boolean is_left = false;
		BinNode<Comparable> parent = null;
		BinNode<Comparable> serach_node = root;
		while(!found&&serach_node!=null)
		{
			if(serach_node.value().compareTo(data)>0)
			{
				parent = serach_node;
				serach_node = serach_node.left();
				is_left =true;
			}
			else if(serach_node.value().compareTo(data)<0)
			{
				parent = serach_node;
				serach_node = serach_node.right();
				is_left=false;
			}
			else
				found = true;
		}
		
		if(!found)
			return;
		this.count--;
		
		if(parent==null)
		{
			deleteRoot();
			return;
		}
	
		
		BinNode left=serach_node.left();
		BinNode right=serach_node.right();	
		if(left==null&&right==null)//被删节点为叶节点
		{
				if(is_left)
					parent.setLeft(null);
				else
					parent.setRight(null);
		}
		else if(left!=null&&right!=null)//被删节点的左右子节点都存在
		{
			//查找中序后继
			//从右节点开始一直向左查找直到该节点没有左子树为止
			//while node.left!=null node = node.left
			if(right.left()==null)//右子节点为目标后继节点
			{
					if(is_left)
						parent.setLeft(right);
					else
						parent.setRight(right);
				right.setLeft(serach_node.left());
			}
			else//右节点之左右节点均存在的情况
			{
				BinNode node_parent=right;
				BinNode node=node_parent.left();
				while(node.left()!=null)//找没有左节点的后继
				{
					node_parent=node;
					node=node.left();
				}
				node_parent.setLeft(node.right());
			
					if(is_left)
				    	parent.setLeft(node);
					else
						parent.setRight(node);
				node.setRight(serach_node.right());
				node.setLeft(serach_node.left());
					
			}	
		}else//被删节点只有左节点或右节点
		{
				if(is_left)
				{
						if(left!=null)
						{
						  parent.setLeft(serach_node.left());
						  serach_node.setLeft(null);
						}
						else
						{
							parent.setLeft(serach_node.right());
							serach_node.setRight(null);
						}
				}
				else
				{
					if(left!=null)
					{
						parent.setRight(serach_node.left());
						serach_node.setLeft(null);
					}
					else
					{
						parent.setRight(serach_node.right());
						serach_node.setRight(null);
					}
				}
				
			}

	}
	
	private void deleteRoot()
	{
		BinNode left=root.left();
		BinNode right=root.right();	
		if(left==null&&right==null)
		{
			root=null;
			return;
		}
		
	if(left==null&&right!=null)
		root = right;
	else if(left!=null&&right==null)
		root = left;
	else
	{
	  if(right.left()==null)
	  {
		  root = right;
		  root.setLeft(left);
	  }else
	  {
		  BinNode node = right.left();
		  BinNode node_parent = right;
		  while(node.left()!=null)
		  {
			  node_parent=node;
			  node=node.left();
		  }
		  node_parent.setLeft(node.right());
		  node.setRight(right);
		  node.setLeft(left);
		  root=node;
//		  root.setRight(right);
//		  root.setLeft(left);
		

	  }
		
	}
			
	}
	
	/**
	 * 中序遍历
	 * @param visitor
	 */
	public void inorder(Visitor visitor)
	{
		visit(root,visitor);
	}
	
	private void visit(BinNode<Comparable> node,Visitor visitor)
	{
		if(node!=null)
		{
			BinNode left = node.left();
			BinNode right = node.right();
			if(left!=null)
				visit(left,visitor);
			if(visitor!=null)
			visitor.visit(node.value());
			if(right!=null)
				visit(right,visitor);
		}
	}
	
//	private String getNodeString(BinNode node)
//	{
//		
//		return data;
//	}
	private void display(BinNode node)
	{
		BinNode left = node.left();
		BinNode right = node.right();
		String data=node.value()+"\t\t"+(left==null?" ":left.value().toString());
		data = data+"\t\t"+(right==null?" ":right.value().toString());
		System.out.println(data);
		if(left!=null)
			display(left);
		if(right!=null)
			display(right);
	}
	public void display()
	{
		String seprator ="\t\t";
		String head = "data"+seprator+"left"+seprator+"right";
		System.out.println(head);
		display(root);
	}
	
	public void deleteAll(Comparable data)
	{
		
	}
	
	public boolean isEmpty()
	{
		return root == null;
	}
	
	public LinkList getPath(Comparable data)
	{
		LinkList<Comparable> list = new LinkList<Comparable>();
		BinNode node = this.findNode(root, data, list);
		if(node!=null)
		return list;
		else
		{
			list.clear();
			return list;
		}
	}
	

	public boolean hasNext() {

		return false;
	}

	public Object next() {
		return null;
	}

	public void remove() 
	{
	
		
	}
	
	
	public static void main(String args[])
	{
		BinarySerachTree<Integer> tree = new BinarySerachTree<Integer>();

//		debug();
		String input = "";
		Random random = new Random();
		for(int i=0;i<20;i++)
		{
			int next = random.nextInt(15);	
			tree.add(next);
			input+=next+" ";
		}
		System.out.println(input);
		tree.inorder(new Visitor(){
			public void visit(Comparable obj) {
			System.out.print(" "+obj);
			}});

		LinkList list = new LinkList();
		for(int i=0;i<20;i++)
		{
			int next = random.nextInt(15);	
			list.append(next);
			tree.delete(next);
		}
		System.out.println();
		tree.inorder(new Visitor(){
			public void visit(Comparable obj) {
			System.out.print(" "+obj);
			}});
		System.out.println();
		printLinkList(list);
		System.out.println("tree.size = "+tree.count());
tree.display();
	}
	
	static void printLinkList(LinkList list)
	{
		Iterator it = list.iterator();
		while(it.hasNext())
		{
			System.out.print(it.next()+" ");
		}
//		System.out.println();
	}
	
	static void debug()
	{
		
		String s="5 4 10 1 14 13 14 11 8 8 6 9 7 8 7 2 8 11 11 5";
		BinarySerachTree<Integer> tree = new BinarySerachTree<Integer>();
		String ss[] = s.split(" ");
		for(int i=0;i<ss.length;i++)
		{
			tree.add(Integer.parseInt(ss[i]));
		}
		tree.inorder(new Visitor(){
			public void visit(Comparable obj) {
			System.out.print(" "+obj);
			}});
		
		System.out.println();
	   s="10 4 3 9 14 2 10 3 9 2 9 7 8 1 12 5 0 4 1 12";
	   ss=s.split(" ");
	   for(int i=0;i<ss.length;i++)
	   {
		   tree.delete(Integer.parseInt(ss[i]));
			tree.inorder(new Visitor(){
				public void visit(Comparable obj) {
				System.out.print(" "+obj);
				}});
			System.out.println("    delete "+ss[i]+" ------------->"+tree.count());
	   }
	}
}

visit 接口 Visitor

package tree;

public interface Visitor {
	
	void visit(Comparable obj);

}