二叉查找树5
接上一篇，继续讲二叉查找树的操作，之前的博客都讲得差不多了，本篇就讲一下删除操作，以及求最矮公共父结点（LCA：lowest common ancestor）的操作吧。
删除将一个结点从二叉查找树中删除之后，剩下的结点可能会不满足二叉查找树的性质，因此，在删除结点之后要对树进行调整，使其满足二叉查找树的性质。根据结点的孩子的数量，将删除操作分为三种情况，我们记要删除的结点为z，实际上删除的结点为y。
1. z结点没有孩子。
如下图a所示，我们要删除值为13的结点，因为结点没有孩子，所以删除之后不会影响到二叉树的整体性质，也就是说，直接将13这个结点删除即可，如图a所示，从左边的二叉树删除13这个点之后变到右边的二叉树。
2. z结点有一个孩子。
如下图b所示，要删除的值为16的结点有一个孩子，而且是右孩子，那么从图上来看，如果，我们将16去掉，然后把以20为结点的子树作为15的右子树，那么整棵树还是符合二叉查找树的性质的，因此，有一个孩子的结点的删除操作，就是要将其孩子作为其父结点的孩子即可。如图b所示。
3. z结点有两个孩子。
如下图c所示，要删除的值为5的结点，有两个孩子，删除之后肯定整棵树就不符合二叉查找树的性质了，因此要进行调整，我们发现，将5的后继，值为6的结点来放到5的位置，然后将6的孩子7作为6的父结点10的孩子，如下图c所示，我们要删除的是z结点，而我们实际要删除y结点，并替换z结点。这里需要注意的一点是，如果一个结点有右孩子，则该结点的后继，至多有一个子女，而且是右孩子。因为假如该结点的后继有左孩子和右孩子，那么其左孩子的值肯定是介于该结点和其后继之间的，那么按照二叉查找树的性质，这个左孩子就应该是该结点的后继，所以，这与原先的后继相互矛盾，因此，结论成立。
好了，分析完了删除的三种情况，我们来完成我们的程序吧。
1 /**
2 * 删除二叉查找树中的结点z
3 * @author Alfred
4 * @param z 要删除的结点
5 * @return 删除或者替换的结点
6 */
7 public TreeNode treeDelete(TreeNode z){
8 TreeNode x = null , y = null ;
9 if (z.getLeft() == null || z.getRight() == null ){
10 // 对应第1和第2种情况
11 y = z;
12 } else {
13 // 对应第3种情况
14 y = treeSuccessor(z);
15 }
16 // 将x置为y的非null子女，或者当y无子女时置为null
17 if (y.getLeft() != null ){
18 x = y.getLeft();
19 } else {
20 x = y.getRight();
21 }
22 // 通过修改x和y的父结点的引用，将y删除
23 if (x != null ){
24 x.setParent(y.getParent());
25 }
26 if (y.getParent() == null ){
27 // x成为树根
28 rootNode = x;
29 } else if (y == y.getParent().getLeft()){
30 // y是其父结点的左孩子
31 y.getParent().setLeft(x);
32 } else {
33 // y是其父结点的右孩子
34 y.getParent().setRight(x);
35 }
36 // 如果y和z不是同一个结点，说明是第3种情况
37 if (y != z){
38 // 内容替换
39 z.setKey(y.getKey());
40 z.setDataNum(y.getDataNum());
41 }
42 return y;
43 }
上面的程序完整的搞定了上面分析的三种情况。
LCALCA问题对于二叉查找树来说是非常简单的。因为二叉查找树满足其特有的性质。给定树中的两个结点x和y，求其最低公共父结点。我们把这个算法分为三种情况。对于一棵二叉查找树来说：
1. 如果x和y分别位于某结点z的左右子树上，那么结点z就是x和y的lca。
2. 如果x和y位于某结点z的左子树或者右子树上，那么x和y的lca也必然位于其所处的左子树或者右子树上。
3. 如果x或者y中，有一个结点是另外一个结点的父结点，那么lca就是它们中的父结点。即如果有一个点和某结点重合，则重合的点就是lca。
那么，我们就从根结点开始，按照从上往下的顺序查找lca吧，比较根结点与两结点的关系，然后再进行下一步的操作。代码如下：
1 /**
2 * 求两个结点的最低公共父结点
3 * @author Alfred
4 * @param x 结点
5 * @param y 结点
6 * @return 最低公共父结点
7 */
8 public TreeNode lca(TreeNode x, TreeNode y){
9 TreeNode tmpNode = rootNode;
10 // 获取两个key值
11 int xKey = x.getKey();
12 int yKey = y.getKey();
13 // 给两个元素按从小到大排下序，使得x<y
14 if (xKey > yKey){
15 int tmpKey = xKey;
16 xKey = yKey;
17 yKey = tmpKey;
18 }
19 while ( true ){
20 if (tmpNode.getKey() < xKey){
21 // 这种情况下，lca在其右子树上
22 tmpNode = tmpNode.getRight();
23 } else if (tmpNode.getKey() > yKey){
24 // 这种情况下，lca在其左子树上
25 tmpNode = tmpNode.getLeft();
26 } else {
27 return tmpNode;
28 }
29 }
30 }
代码比较简单，就是按照上面的三种情况按照从上到下的顺序来分类处理的。其他还有一些lca算法，如离线算法(Tarjan)和在线算法(RMQ)等，暂时先不讨论了，以后有时间了再补上吧。为了方便想学习的童鞋来测试，我把整个代码就贴到下面了（木有找到更好地方法来分享。。）。
TreeNode.java
BSTree.java
TestMain.java
ps：关于二叉查找树的一些操作先写到这里吧，有不对的地方，请广大博友指正啊。
pss：画图好累啊。。转载请注明。。。
标签: 算法
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息