Java实现的二叉搜索树

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为二叉排序树。 

 

定义了一个STreeNode，

 

package com.woxiaoe.collection.tree;
/**
 * 
 * @author 小e
 *
 * 2010-4-9 下午08:10:25
 */
public class STreeNode<T> {
	
	private T nodeValue;
	private STreeNode<T> left;
	private STreeNode<T> right;
	private STreeNode<T> parent;
	
	public STreeNode(T value) {
		this.nodeValue = value; 
	}
	
	public STreeNode(T nodeValue, STreeNode<T> parent) {
		this.nodeValue = nodeValue;
		this.parent = parent;
	}

	public T getNodeValue() {
		return nodeValue;
	}
	public void setNodeValue(T nodeValue) {
		this.nodeValue = nodeValue;
	}
	public STreeNode<T> getLeft() {
		return left;
	}
	public void setLeft(STreeNode<T> left) {
		this.left = left;
	}
	public STreeNode<T> getRight() {
		return right;
	}
	public void setRight(STreeNode<T> right) {
		this.right = right;
	}
	public STreeNode<T> getParent() {
		return parent;
	}
	public void setParent(STreeNode<T> parent) {
		this.parent = parent;
	}
	
	
	
}

 

 STree

 

package com.woxiaoe.collection.tree;

import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 二叉排序树
 * @author 小e
 *
 * 2010-4-9 下午08:09:14
 */
public class STree<T> implements Collection<T> {
	private int treeSize;
	private STreeNode<T> root;
	
	public STree() {
		this.treeSize = 0;
		root = null;
	}

	@Override
	public boolean add(T t) {
		STreeNode<T> node = root,newNode,parent = null;
		int result = 0;
		while(node != null){
			parent = node;
			result = ((Comparable<T>)node.getNodeValue()).compareTo(t);
			if(result == 0){
				return false;
			}
			if(result > 0){//往左
				node = node.getLeft();
			}else{
				node = node.getRight();
			}
		}
		newNode = new STreeNode<T>(t);
		if(parent == null){//第一个进来的元素
			root = newNode;
		}else if(result > 0){
			parent.setLeft(newNode);
		}else{
			parent.setRight(newNode);
		}
		newNode.setParent(parent);
		treeSize ++;
		return true;
	}
	@Override
	public boolean addAll(Collection<? extends T> c) {
		boolean flag = false;
		for (Iterator iterator = c.iterator(); iterator.hasNext();) {
			T t = (T) iterator.next();
			add(t);
			flag = true;
		}
		return flag;
	}

	@Override
	public void clear() {
		// TODO Auto-generated method stub
		
	}

	@Override
	public boolean contains(Object o) {
		if(findNode((T) o) != null){
			return true;
		}
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Iterator iterator = c.iterator(); iterator.hasNext();) {
			T t = (T) iterator.next();
			if(findNode(t) == null){
				return false;
			}
		}
		return true;
	}

	@Override
	public boolean isEmpty() {
		return treeSize == 0;
	}

	@Override
	public Iterator<T> iterator() {
		return new IteratorImpl();
	}

	@Override
	public boolean remove(Object o) {
		STreeNode<T> node = findNode((T)o);
		if(node == null){
			return false;
		}
		treeSize --;
		return removeNode(node);
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int size() {
		return treeSize;
	}

	@Override
	public Object[] toArray() {
		Object[] array = new Object[treeSize];
		int index = 0;
		for (Iterator iterator = this.iterator(); iterator.hasNext();) {
			T o = (T) iterator.next();
			array[index++] = o;
		}
		return array;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
		return null;
	}
	
	private STreeNode<T> findNode(T item){
		STreeNode<T> node = root;
		int value = 0;
		while(node != null){
			value = ((Comparable<T>)node.getNodeValue()).compareTo(item);
			if(value == 0){
				return node;
			}else if(value > 0){
				node = node.getLeft();
			}else{
				node = node.getRight();
			}
		}
		return null;
	}
	/**
	 * 删除节点
	 * @param node
	 * @return
	 */
	private boolean removeNode(STreeNode<T> node){
		STreeNode<T> pNode,rNode;//node的父节点，和node的子节点
		/**
		 * 情况一，当节点至少有一棵空子树
		 */
		if(node.getLeft() == null || node.getRight() == null){
			pNode = node.getParent();
			
			if(node.getLeft() == null){
				rNode = node.getRight();
			}else{
				rNode = node.getLeft();
			}
			
			if(rNode != null){
				rNode.setParent(pNode);//将r的父节点指向p
			}
			
			if(pNode == null){//node为root节点
				root = rNode;
			}else if(((Comparable<T>)pNode.getNodeValue()).compareTo(node.getNodeValue()) < 0){
				pNode.setRight(node);
			}else{
				pNode.setLeft(node);
			}
		}else{
			rNode = node.getRight();
			pNode = node;
			
			/**
			 * 找到node的右子树中最大于node的最小值
			 */
			while(rNode.getLeft() != null){
				pNode = rNode;
				rNode = rNode.getLeft();
			}
			/**
			 * 交换值
			 */
			node.setNodeValue(rNode.getNodeValue());
			
			if(pNode == node){//node 的下一结点 没有节点
				node.setRight(rNode.getRight());//
			}else{
				pNode.setLeft(rNode.getRight());
			}
			/**
			 * 将rNode的右子树 的 parent 接到pNode下
			 */
			if(rNode.getRight() != null){
				rNode.getRight().setParent(pNode);
			}
			
		}
		return true;
	}
	/**
	 * 取最大值
	 * @return
	 */
	public T maxValue(){
		STreeNode<T> node = root;
		while(node.getRight() != null){
			node = node.getRight();
		}
		
		return node == null?null:node.getNodeValue();
	}
	
	public T minValue(){
		STreeNode<T> node = root;
		while(node.getLeft() != null){
			node = node.getLeft();
		}
		return node == null?null:node.getNodeValue();
	}
	
	public STreeNode<T> getRoot() {
		return root;
	}

	public void setRoot(STreeNode<T> root) {
		this.root = root;
	}
	
	private class IteratorImpl implements Iterator<T>{
		STreeNode<T> nextNode,returnNode,pNode;
		public IteratorImpl() {
			nextNode = root;
			//选择最小节点
			if(nextNode != null){
				while(nextNode.getLeft() != null){
					nextNode = nextNode.getLeft();
				}
			}
			
		}
		@Override
		public boolean hasNext() {
			// TODO Auto-generated method stub
			return nextNode != null;
		}

		@Override
		public T next() {
			if(nextNode == null){
				throw new NoSuchElementException("没有该元素");
			}
			returnNode = nextNode;
			if(nextNode.getRight() != null){
				nextNode = nextNode.getRight();
				while(nextNode.getLeft() != null){
					nextNode = nextNode.getLeft();
				}
			}else{
				/**
				 * 如果右子树为空，沿着父节点的引用，直至查到当前节点nextNode作为pNode的左节点是停止
				 * pNode就为就为下一个要访问的点
				 */
				
				pNode = nextNode.getParent();
				//但pNode不是根结点 且 当前节点为 pNode的右节点
				while(pNode != null && nextNode == pNode.getRight()){
					nextNode = pNode;
					pNode = pNode.getParent();
				}
				
				nextNode = pNode;
			}
			
			return returnNode.getNodeValue();
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException("不支持该方法 ");
		}
		
	}
}																				

测试类

 

package com.woxiaoe.collection.tree;

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

import junit.framework.TestCase;

/**
 * 二叉排序树测试
 * @author 小e
 *
 * 2010-4-9 下午08:32:55
 */
public class STreeTest extends TestCase {
	
	STree<Integer> tree = new STree<Integer>();
	int[] data = new int[]{40,30,65,25,35,50,10,26,33,29,34};
	@Override
	protected void setUp() throws Exception {
		Random r = new Random();
		int value;
		int len = data.length;
		for(int i = 0; i < len; i++){
			value = r.nextInt(100);
			//tree.add(value);
			tree.add(data[i]);
		}
		
	}
	
	public void testSTree(){
		LNR(tree.getRoot());
	}
	public void testFind(){
		for(int i = 0; i < 15; i++){
			System.out.println("i" + i + "\t" + tree.contains(i));
		}
		
	}
	/**
	 * 测试删除节点
	 */
	public void testDelete(){
		System.out.println("删除前:");
		LNR(tree.getRoot());
		tree.remove(40);
		System.out.println("删除节点30：" );
		LNR(tree.getRoot());
	}
	
	public void testMaxAndMin(){
		System.out.println("max:" + tree.maxValue());
		System.out.println("min:" + tree.minValue());
	}
	/**
	 * 测试迭代
	 */
	public void testTreeIterator(){
		for (Iterator iterator = tree.iterator(); iterator.hasNext();) {
			Integer i = (Integer) iterator.next();
			System.out.print(i + " ");
		}
	}
	
	/**
	 * 中序排列
	 * @param node
	 */
	public void LNR(STreeNode node){
		if(node == null){
			return;
		}
		LNR(node.getLeft());
		visit(node);
		LNR(node.getRight());
	}
	private void visit(STreeNode node){
		System.out.print(node.getNodeValue() + " ");
	}
	
	
}

 

 Output

10 25 26 29 30 33 34 35 40 50 65 i0 false i1 false i2 false i3 false i4 false i5 false i6 false i7 false i8 false i9 false i10 true i11 false i12 false i13 false i14 false 删除前: 10 25 26 29 30 33 34 35 40 50 65 删除节点30： 10 25 26 29 30 33 34 35 50 65 max:65 min:10 10 25 26 29 30 33 34 35 40 50 65