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