• 算法之二叉搜索树
  • 发布于 2个月前
  • 294 热度
    0 评论
  • 林勇
  • 0 粉丝 38 篇博客
  •   

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

javabean:

  1. class Data{  
  2.     private Data parent;  
  3.     private int value;  
  4.     private Data left;  
  5.     private Data right;  
  6.     public Data getParent() {  
  7.         return parent;  
  8.     }  
  9.     public void setParent(Data parent) {  
  10.         this.parent = parent;  
  11.     }  
  12.     public int getValue() {  
  13.         return value;  
  14.     }  
  15.     public void setValue(int value) {  
  16.         this.value = value;  
  17.     }  
  18.     public Data getLeft() {  
  19.         return left;  
  20.     }  
  21.     public void setLeft(Data left) {  
  22.         this.left = left;  
  23.     }  
  24.     public Data getRight() {  
  25.         return right;  
  26.     }  
  27.     public void setRight(Data right) {  
  28.         this.right = right;  
  29.     }  
  30. }  

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

  1. public void insert(Data tree,Data v){  
  2.         if(tree==null){  
  3.             return;  
  4.         }  
  5.         Data flag=tree;  
  6.         Data present=flag;  
  7.         while(flag!=null){  
  8.             present=flag;  
  9.             if(v.getValue()>present.getValue()){  
  10.                 flag=flag.getRight();  
  11.             }else {  
  12.                 flag=flag.getLeft();  
  13.             }  
  14.         }  
  15.         v.setParent(present);  
  16.         if (v.getValue()>present.getValue()) {  
  17.             present.setRight(v);  
  18.         }else {  
  19.             present.setLeft(v);  
  20.         }  
  21.     }  

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

  1. public Data search(Data tree,int value){  
  2.      Data present=tree;  
  3.      while(present!=null&&value!=present.getValue()){  
  4.          if(value>present.getValue()){  
  5.              present=present.getRight();  
  6.          }else {  
  7.             present=present.getLeft();  
  8.         }  
  9.      }  
  10.     return present;  
  11. }  

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

  1. public Data min(Data d){  
  2.         while(d.getLeft()!=null){  
  3.             d=d.getLeft();  
  4.         }  
  5.         return d;  
  6.     }  
  7.     public Data max(Data d){  
  8.         while(d.getRight()!=null){  
  9.             d=d.getRight();  
  10.         }  
  11.         return d;  
  12.     }  

很好理解,应该不需要解释什么吧,就是一直取左或一直取右知道为null即可。
删除操作:一共有三种情况其中前两种情况非常简单。直接贴图,比较直观。

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

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

  1. /** 
  2.      *   用d树来替换s数在二叉树中的位置 
  3.      * @param root 
  4.      * @param s 
  5.      * @param d 
  6.      */  
  7.     private void transplant(Data root,Data s,Data d){  
  8.         if(root==s){  
  9.             root=d;  
  10.         }else if (s==s.getParent().getLeft()) {  
  11.             s.getParent().setLeft(d);  
  12.         }else {  
  13.             s.getParent().setRight(d);  
  14.         }  
  15.         d.setParent(s.getParent());  
  16.     }  

有了这个方法我们就容易多了。剩下的就是维护链表结构就可以了。我们还是按照上面的情况分析。前两种情况我相信大家都会了。最后一个替换找谁替换?这里我先给出答案是找z右节点开始的最小值来替换。为什么这样,首先这个点至少是没有左节点,取出后其右节点可以直接取代他的位置,如果没有右节点我们更轻松。现在它跟树就脱离,看他放在z的位置可以吗?完全可以,他是右子树的最小值,比左子树是要大,但是比右子树小于z的效果是一样的。这样去想是不是已经解决了。有人可能想左子树的最大值可以吗,也是可以的。下面是代码。大家可以看代码将细节补充起来。

  1. public void delete(Data tree ,Data d){  
  2.           
  3.         if(d.getLeft()==null){  
  4.             transplant(tree, d, d.getRight());  
  5.         }else if(d.getRight()==null){  
  6.             transplant(tree, d, d.getLeft());  
  7.         }else{  
  8.             Data cache=min(d.getRight());  
  9.             if(cache!=d.getRight()){  
  10.                 transplant(tree, cache, cache.getRight());  
  11.                 cache.setRight(d.getRight());  
  12.                 cache.getRight().setParent(cache);  
  13.             }  
  14.             transplant(tree, d, cache);  
  15.             cache.setLeft(d.getLeft());  
  16.             cache.getLeft().setParent(cache);  
  17.         }  
  18.     }  
用户评论