算法起步之二叉搜索树

        学习二叉搜索树之前，我们先复习一下树的相关知识，数是几种经典的数据结构之一，树其实就是维护了一对多的关系，一个节点可以有多个孩子，但是每个节点至多只有一个双亲。如何去描述存储一棵树呢，这里方法有很多，数组、链表、十字链表等等。这里我们主要研究二叉树，二叉树是树的一种特殊形式，节点至多只有两棵子树，有左右之分次序不能任意颠倒。二叉树还有一个性质就是叶子节点的个数=度为2的节点+1 。二叉搜索树又叫二叉排序树或二叉查找树。他比二叉树又加个1个性质，就是左子树存储的数值不能超过其双亲存储的值，而右子树存储的值则不能小于其双亲存储的值。记住这个性质，你就学会了二叉搜索树。二叉树是我们接下来研究的红黑树，B树，平衡树的基础。可见二叉树的重要性，而二叉查找树是里面最简单的树，学习二叉排序树主要掌握他的插入、查找（找指定值，最大值，最小值）、删除即可，这里三个方法只有删除稍微麻烦一点。算法导论上说二叉查找树的删除有点棘手，看到这里心里还有点害怕，感觉要碰上难题了，结果没想象的那么难，但当学红黑树时，书上又说红黑树的删除稍微复杂一些，当看完以后心里瞬间千万只草泥马在奔跑，这哪是一个等级的，红黑树跟二叉搜索树的难度，我们可以用拼魔方的第二层与第三层的难度来比拟，至少我是这样感觉。所以学习二叉搜索树时大家一点都不用担心。还有一点是，我感觉研究树形结构跟玩魔方有很多的相似的地方，如果你是个魔方高手，我相信理解起来应该非常简单。

       首先我写了一个类来存储二叉树，其实就是一个链表 一个双亲，两个孩子，还有存储的值，很标准的一个javabean：

class Data{
	private Data parent;
	private int value;
	private Data left;
	private Data right;
	public Data getParent() {
		return parent;
	}
	public void setParent(Data parent) {
		this.parent = parent;
	}
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public Data getLeft() {
		return left;
	}
	public void setLeft(Data left) {
		this.left = left;
	}
	public Data getRight() {
		return right;
	}
	public void setRight(Data right) {
		this.right = right;
	}
}

       插入操作：插入操作跟查询操作其实是差不多的，都是按照二叉查找树的性质来维护的。插入时与节点对比，大的话就放在右节点上，小就放在左节点。在插入之前先进行迭代的对比即可。

public void insert(Data tree,Data v){
		if(tree==null){
			return;
		}
		Data flag=tree;
		Data present=flag;
		while(flag!=null){
			present=flag;
			if(v.getValue()>present.getValue()){
				flag=flag.getRight();
			}else {
				flag=flag.getLeft();
			}
		}
		v.setParent(present);
		if (v.getValue()>present.getValue()) {
			present.setRight(v);
		}else {
			present.setLeft(v);
		}
	}

         搜索操作：搜索操作可以用递归也可以用迭代，只是迭代的效率要比递归的效率好。还是完全的二叉查找树性质的应用。

	public Data search(Data tree,int value){
		 Data present=tree;
		 while(present!=null&&value!=present.getValue()){
			 if(value>present.getValue()){
				 present=present.getRight();
			 }else {
				present=present.getLeft();
			}
		 }
		return present;
	}

        在这里还有两个方法可以需要说一下，就是求从树的一个节点开始的最大的值和最小的值。

public Data min(Data d){
		while(d.getLeft()!=null){
			d=d.getLeft();
		}
		return d;
	}
	public Data max(Data d){
		while(d.getRight()!=null){
			d=d.getRight();
		}
		return d;
	}

             删除操作：一共有三种情况其中前两种情况非常简单。直接贴图，比较直观。

          此图出自算法导论z是我们将要删除的值。a情况是z无子节点直接删除就可，b情况是z有一个子节点，需要我们将z的子节点取代就可以，而c则是z有2个子节点，我们按照一定的方式取出一个节点来取代z就可以。

         大家可以跟着我说的，这样去分析，a情况是拿null来替换z。b情况是拿z的子节点去替换z。而c情况是按照一定方法找到的节点去替换z。说道这里相比有程序设计思想的人可以看出我们可以提取一个方法出来就是一个替换方法。这里我已经把方法写好了。

/**
	 *   用d树来替换s数在二叉树中的位置
	 * @param root
	 * @param s
	 * @param d
	 */
	private void transplant(Data root,Data s,Data d){
		if(root==s){
			root=d;
		}else if (s==s.getParent().getLeft()) {
			s.getParent().setLeft(d);
		}else {
			s.getParent().setRight(d);
		}
		d.setParent(s.getParent());
	}

public void delete(Data tree ,Data d){
		
		if(d.getLeft()==null){
			transplant(tree, d, d.getRight());
		}else if(d.getRight()==null){
			transplant(tree, d, d.getLeft());
		}else{
			Data cache=min(d.getRight());
			if(cache!=d.getRight()){
				transplant(tree, cache, cache.getRight());
				cache.setRight(d.getRight());
				cache.getRight().setParent(cache);
			}
			transplant(tree, d, cache);
			cache.setLeft(d.getLeft());
			cache.getLeft().setParent(cache);
		}
	}

         友情提示：转载请注明出处【作者：idlear  博客：http://blog.csdn.net/idlear】

算法起步之二叉搜索树

原文：http://www.cnblogs.com/lonelyxmas/p/3562012.html