基于数组的二叉查找树 Binary Search Tree

转载  http://my.oschina.net/BreathL/blog/54734  

二叉查找树

     二叉查找树是一种支持动态查询的数据结构，所谓动态查寻结构：即在当数据集合内容发生改变时，集合内数据的排列组合不用重新构建。这样的数据结构在查询时需要不断变动的场景中是非常高效的，二叉查找树就是其中一个，并且它是SBT,AVL,红黑树的基础，一直有兴趣想要研究下。原理就不介绍了，可参考这个 。今天花了半天时间，自己完成了一个基于数组的Java实现。

实现的方法：INSERT、SEACH、DELETE

      先简单说明下这几个方法的实现原理：

 

SEARCH:

      查询方法的思路很简单，和二分查找相似，即从根节点开始查找，若待查找元素a小于根节点，则在该节点的左子树中继续查找，大于则去右子树中，等于便是找到了。

 

 

INSERT：

      插入方法，也是一个查询的过程，若根节点为空，则直接设置成跟节点，否则依如下方式与节点比较： 若小于节点值，将元素插入其左子树，若大于该节点值插入其右子树。若发现相等的则退出，算是排重。

DELETE：

      删除操作相对比较复杂，若要删除某一个节点 Z ，可能遇见三种情况： 

     一.    节点 Z 不包含任何子树；此时可直接删除，不影响数据的结构。

     二.    节点 Z  只有一个子子树，左子树或右子树；此时只需将 Z 的唯一的那个子树的根节点指向 Z 的父节点即可，此操作也不影响数据的。（但由于我是基于数组的，指针式通过数组的位置表示，所以某个节点指向变了，其所有子节点在数组中的位置都要变，不过好在这种变化是有规律的，我已在程序中注明。）

     三.     节点 Z 的左子树和右子树同时存在。这种情况最为复杂，首先找到 Z 左子树中值最大的节点，记为 H ，将代替 Z 在树种的位置，然后再以递归的方式删除节点 H.

 

 

package com.mycode.structures;

import java.util.Collection;

/**
 * 基于数组二叉查找树实现
 * @author Breath_L
 * @param <T>
 */
public class BSTree<T extends Comparable<T>> {
	private static final int DEFAULT_SIZE = 10;
	private T[] data;
	private Integer count;
	
	public Integer getCount(){
		return count;
	}
	
	public BSTree(int size){
		data = (T[]) new Object[size];
		count = 0;
	}
	
	public BSTree(){
		data = (T[]) new Object[DEFAULT_SIZE];
		count = 0;
	}
	
	/**
	 * 扩充容量
	 */
	private void expandSize(){
		T[] newDate = (T[]) new Object[data.length * 2];
		System.arraycopy(data, 0, newDate, 0, data.length);
		data = newDate;		
	}
	
	/**
	 * 判断二叉树中是否包含元素 one
	 * @param one
	 * @return 若找到了，返回该元素在数组中的位置，否则返回-1
	 */
	public int search(T one){
		if(data[0] == null){
			System.out.println("==> This BSTree is Empty!");
			return -1;
		}else{
			int index = 0;
			while(index < data.length && data[index] != null){
				int f = one.compareTo(data[index]);
				if(f == 0){                    //找到了返回其位置
					return index;
				}else if(f < 0){
					index = 2 * index + 1;
				}else{
					index = 2 * index + 2;
				}
			}
			return -1;
		}
	}
	
	/**
	 * 添加元素
	 * @param t
	 */
	public void add(T t){
		if(data[0] == null){
			data[0] = t;
			count++;
			return;
		}else{
			int index = 0;
			while(index < data.length){
				if(t.compareTo(data[index])<0){
					int left = 2 * index + 1;
					if(left >= data.length)
						expandSize();					
					if(data[left] == null){
						data[left] = t;
						break;
					}else{
						index = left;
					}
				}else if(t.compareTo(data[index]) > 0){
					int right = 2 * index + 2;
					if(right >= data.length)
						expandSize();
					if(data[right] == null){
						data[right] = t;
						break;
					}else{
						index = right;
					}
				}else{                        // 相同元素不处理，算是排重了
					break;
				}				
			}
		}
		count++;
	}
	
	public void addAll(Collection<T> all){
		for (T t:all){
			add(t);
		}
	}
	public void addAll(T[] all){
		for (T t:all){
			add(t);
		}
	}
	
	public void delete(T del){
		int del_index = this.search(del);
		if(del_index != -1){                    //等于-1 表示没有，便不做处理
			real_delete(del_index);
		}
	}
	
	/**
	 * 删除某个节点
	 * @param index：该节点在数组中的位置
	 * @return 
	 */
	private void real_delete(int index){
		int lc = 2*index + 1;
		int rc = 2*index + 2;
		if(data[lc] != null && data[rc] != null){        // 左子树、右子树同时存在的情况
			int left_max_child = findLeftMaxChild(index);
			data[index] = data[left_max_child];          //删除节点
			real_delete(left_max_child);                 //递归删除左子树中值最大的节点
		}else if(data[lc] == null && data[rc] == null){  // 都没有则直接删除
			data[index] = null;
		}else{ 
			if(data[lc] != null){
				replaceNodeWithChild(lc, lc-index);
			}else{
				replaceNodeWithChild(rc, rc-index);
			}
		}
	}
	
	/**
	 * 寻找某个节点的左子树中最大节点
	 * @param index 某个节点的位置
	 * @return 最大节点位置
	 */
	private int findLeftMaxChild(int index){
		int left = 2*index +1;
		int bigger = 2*left + 2;
		while( bigger < data.length && data[bigger] != null){			
			left = bigger;
			bigger = 2 * bigger + 2;			
		}
		return left;
	}
	
	/**
	 * 若子节点C替换了其父节点P，则C的所有子节点都需要被移动(由于数组的原因)，distance为C和P在数组中位置之差。
	 * 其所有子节点在数组中移动的距离为 distance*(2^x)，x为这些子节点与节点C的距离(相邻节点距离为1)；
	 * @param node
	 * @param distance
	 */
	private void replaceNodeWithChild(int node, int distance){
		int left = 2*node+1;
		int right = 2*node+2;
		int current_distance = distance*2;                   //每次递归距离*2 
		if(data[left] != null){
			data[left - current_distance] = data[left];
			replaceNodeWithChild(left,current_distance);     //递归遍历下个节点
		}
		if(data[right] != null){
			data[right - current_distance] = data[right];
			replaceNodeWithChild(right,current_distance);
		}
	}
}