控件中国网现已改版,您看到的是老版本网站的镜像,系统正在为您跳转到新网站首页,请稍候.......
中国最专业的商业控件资讯网产品咨询电话:023-67870900 023-67871946
产品咨询EMAIL:SALES@COMPONENTCN.COM

二叉查找树

作者:未知 出处:cnblogs 2012年05月11日 阅读:

接上一篇,让我们来继续讨论二叉查找树的基本操作,需要注意的一点是,上篇中的遍历操作是针对任意一棵二叉树都可以的,凡是没提及需要二叉查找树性质的地方,应该都是满足二叉树的操作。上篇主要讨论了二叉树

的遍历操作,这篇,我们来讨论二叉查找树的查找、求最大最小值以及求前驱和后继等操作。
查找
  二叉查找树的查找操作可以在O(h)时间内完成,其中h为树的高度。查找的算法很简单,根据二叉查找树的性质,我们先将要比较的元素跟根元素相比较,如果相等则返回,如果大于根结点的key,则继续在右子树中

查找,如果小于根结点的key值,则在左子树中查找。这也跟插入过程类似,童鞋们可以想象一下,我就不画图了,画图很麻烦。
  下面的代码完成了在树根为x的树中查找关键字为k的元素,如果存在的话就返回其饮用,不存在,则返回null。
  递归查找的代码为:

 /**
     * 查找以x为根结点的树中key的值为k的结点,返回找到的结点或者null
     * @author Alfred
     * @param x 根结点
     * @param k 要查找的整数
      * @return 找到的结点或者null
      */
     private TreeNode treeSearch(TreeNode x, int k){
         if(x == null || k == x.getKey()){
             return x;
         }
         if(k < x.getKey()){
             return treeSearch(x.getLeft(), k);//查左子树
         }else{
             return treeSearch(x.getRight(), k);//查右子树
         }
     }

  非递归查找的代码为:
 

 /**
      * 非递归地查找以x为根结点的树中key的值为k的结点,返回找到的结点或者null
     * @author Alfred
      * @param x 根结点
      * @param k 要查找的整数
      * @return 找到的结点或者null
      */
     private TreeNode treeSearchNonrecursive(TreeNode x, int k){
       while(x != null && k != x.getKey()){
            if(k < x.getKey()){
                 x = x.getLeft();
             }else{
                x = x.getRight();
             }
         }
         return x;
     }

最大值
  根据二叉查找树的性质,树中的最大值一定是位于整棵树的最“右”边的右孩子,因为,二叉查找树的性质中说明了,右子树中的结点都大于或者等于父结点和左子树。所以求最大值是一个很简单的操作。代码如下:

 /**
      * 找以x为根结点的二叉查找树中的最大值
      * @author Alfred
      * @param x 根结点
      * @return 最大值结点或者null
      */
     public TreeNode treeMax(TreeNode x){
         while(x.getRight() != null){
             x = x.getRight();
         }
         return x;
     }

最小值
  同理,根据二叉查找树的性质,最小值一定是位于整棵树中最“左”边的左孩子,因为,二叉查找树的性质的性质中说明了,左子树中的结点都小于或者等于父结点和右子树。所以跟求最大值对偶的代码如下:

 /**
      * 找以x为根结点的二叉查找树中的最小值
      * @author Alfred
      * @param x 根结点
      * @return 最小值结点或者null
      */
     public TreeNode treeMin(TreeNode x){
         while(x.getLeft() != null){
             x = x.getLeft();
         }
         return x;
     }

后继
  由于在之前的博客里面数结点的定义形式,在处理的时候将树中相同的结点全都合并了起来,因此,位于树中不同位置的结点的key值肯定是不同的。因此,我们将求某一个结点后继结点的操作看成是求大于该结点

key值的结点中key值最小的那个结点(有点绕。。。)。
  我们记结点x为输入结点,y为输出结点,即y结点是x结点的后继,在我们这里分两种情况进行讨论:
  1. x结点的右子树不为空。
    根据二叉查找树的性质,y肯定是位于x的右子树上,而且是x的右子树的最小值。
  2. x结点的右子树为空。
    如果存在后继y,则y是x的最低祖先结点,且y的左儿子也是x的祖先。晕了?说的简单些。如果x结点的右子树为空,则以x结点为最“右”孩子的子树t中,x结点一定是这个子树的最大值,根据二叉查找树的性质

,只有当存在某一结点y,y的左子树恰好是t的时候,y才是x的后继。现在回去读一读这段开始的话,是不是容易理解多了。
  好了,了解了基本的算法,就让我贴上代码吧~

      /**
      * 找结点x的后继结点
      * @author Alfred
     * @param x 结点
      * @return x的后继结点或者null
      */
     public TreeNode treeSuccessor(TreeNode x){
         //第一种情况
        if(x.getRight() != null){
             return treeMin(x.getRight());
         }
         //第二种情况
         TreeNode tmpNode = x.getParent();
        while(tmpNode != null && x == tmpNode.getRight()){
             x = tmpNode;
             tmpNode = tmpNode.getParent();
         }
        return tmpNode;
   }

  这个算法就是按照上面提到的两种情况来实现的,时间复杂度为O(h),h为树的高度。
前驱
  求结点的前驱的算法与后继的算法是对称的。其时间复杂度也是O(h)。在处理上也分为两种情况,我就直接上代码了,有心的童鞋们自己想一下吧~

  /**
      * 找结点x的前趋结点
    * @author Alfred
     * @param x 结点
     * @return x的前趋结点或者null
     */
     public TreeNode treePredecessor(TreeNode x){
        //第一种情况
        if(x.getLeft() != null){
             return treeMax(x.getLeft());
         }
//第二种情况
         TreeNode tmpNode = x.getParent();
        while(tmpNode != null && x == tmpNode.getLeft()){
            x = tmpNode;
             tmpNode = tmpNode.getParent();
         }
         return tmpNode;
     }
 

热推产品

  • ActiveReport... 强大的.NET报表设计、浏览、打印、转换控件,可以同时用于WindowsForms谀坔攀戀Forms平台下......
  • AnyChart AnyChart使你可以创建出绚丽的交互式的Flash和HTML5的图表和仪表控件。可以用于仪表盘的创......
首页 | 新闻中心 | 产品中心 | 技术文档 | 友情连接 | 关于磐岩 | 技术支持中心 | 联系我们 | 帮助中心 Copyright-2006 ComponentCN.com all rights reserved.重庆磐岩科技有限公司(控件中国网) 版权所有 电话:023 - 67870900 传真:023 - 67870270 产品咨询:sales@componentcn.com 渝ICP备12000264号 法律顾问:元炳律师事务所 重庆市江北区塔坪36号维丰创意绿苑A座28-5 邮编:400020
在线客服
在线客服系统
在线客服
在线客服系统