二叉查找树（四）

时间：2021-01-30 20:20:16

　　接上一篇，让我们来继续讨论二叉查找树的基本操作，需要注意的一点是，上篇中的遍历操作是针对任意一棵二叉树都可以的，凡是没提及需要二叉查找树性质的地方，应该都是满足二叉树的操作。上篇主要讨论了二叉树的遍历操作，这篇，我们来讨论二叉查找树的查找、求最大最小值以及求前驱和后继等操作。

  • 查找

　　二叉查找树的查找操作可以在O(h)时间内完成，其中h为树的高度。查找的算法很简单，根据二叉查找树的性质，我们先将要比较的元素跟根元素相比较，如果相等则返回，如果大于根结点的key，则继续在右子树中查找，如果小于根结点的key值，则在左子树中查找。这也跟插入过程类似，童鞋们可以想象一下，我就不画图了，画图很麻烦。

　　下面的代码完成了在树根为x的树中查找关键字为k的元素，如果存在的话就返回其饮用，不存在，则返回null。

　　递归查找的代码为：

 1 /**
 2      * 查找以x为根结点的树中key的值为k的结点，返回找到的结点或者null
 3      * @author Alfred
 4      * @param x 根结点
 5      * @param k 要查找的整数
 6      * @return 找到的结点或者null
 7      */
 8     private TreeNode treeSearch(TreeNode x, int k){
 9         if(x == null || k == x.getKey()){
10             return x;
11         }
12         if(k < x.getKey()){
13             return treeSearch(x.getLeft(), k);//查左子树
14         }else{
15             return treeSearch(x.getRight(), k);//查右子树
16         }
17     }

　　非递归查找的代码为：

　

 1 /**
 2      * 非递归地查找以x为根结点的树中key的值为k的结点，返回找到的结点或者null
 3      * @author Alfred
 4      * @param x 根结点
 5      * @param k 要查找的整数
 6      * @return 找到的结点或者null
 7      */
 8     private TreeNode treeSearchNonrecursive(TreeNode x, int k){
 9         while(x != null && k != x.getKey()){
10             if(k < x.getKey()){
11                 x = x.getLeft();
12             }else{
13                 x = x.getRight();
14             }
15         }
16         return x;
17     }
  • 最大值

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

 1 /**
 2      * 找以x为根结点的二叉查找树中的最大值
 3      * @author Alfred
 4      * @param x 根结点
 5      * @return 最大值结点或者null
 6      */
 7     public TreeNode treeMax(TreeNode x){
 8         while(x.getRight() != null){
 9             x = x.getRight();
10         }
11         return x;
12     }
  • 最小值

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

 1 /**
 2      * 找以x为根结点的二叉查找树中的最小值
 3      * @author Alfred
 4      * @param x 根结点
 5      * @return 最小值结点或者null
 6      */
 7     public TreeNode treeMin(TreeNode x){
 8         while(x.getLeft() != null){
 9             x = x.getLeft();
10         }
11         return x;
12     }
  • 后继

　　由于在之前的博客里面数结点的定义形式，在处理的时候将树中相同的结点全都合并了起来，因此，位于树中不同位置的结点的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的后继。现在回去读一读这段开始的话，是不是容易理解多了。

　　好了，了解了基本的算法，就让我贴上代码吧~

 1     /**
 2      * 找结点x的后继结点
 3      * @author Alfred
 4      * @param x 结点
 5      * @return x的后继结点或者null
 6      */
 7     public TreeNode treeSuccessor(TreeNode x){
 8         //第一种情况
 9         if(x.getRight() != null){
10             return treeMin(x.getRight());
11         }
12         //第二种情况
13         TreeNode tmpNode = x.getParent();
14         while(tmpNode != null && x == tmpNode.getRight()){
15             x = tmpNode;
16             tmpNode = tmpNode.getParent();
17         }
18         return tmpNode;
19     }

　　这个算法就是按照上面提到的两种情况来实现的，时间复杂度为O(h)，h为树的高度。

  • 前驱

　　求结点的前驱的算法与后继的算法是对称的。其时间复杂度也是O(h)。在处理上也分为两种情况，我就直接上代码了，有心的童鞋们自己想一下吧~

 1 /**
 2      * 找结点x的前趋结点
 3      * @author Alfred
 4      * @param x 结点
 5      * @return x的前趋结点或者null
 6      */
 7     public TreeNode treePredecessor(TreeNode x){
 8         //第一种情况
 9         if(x.getLeft() != null){
10             return treeMax(x.getLeft());
11         }
12         //第二种情况
13         TreeNode tmpNode = x.getParent();
14         while(tmpNode != null && x == tmpNode.getLeft()){
15             x = tmpNode;
16             tmpNode = tmpNode.getParent();
17         }
18         return tmpNode;
19     }

　　嗯。。。本话完，其他操作下回分解。

 

标签：

相关文章