一、前言
本文诣在帮助像博主这样没有基础的同学更好地理解二叉搜索树中前驱节点的求法，以及为什么这么求就可以，高手童鞋就忽略吧...这其中可能有我个人理解不准确的地方，还请帮忙指正。本文所总结的证明方法都是我自己归纳的所以不一定正确，给需要的同学作参考。
接下来就是正文内容了
二、前驱节点的定义
1. 定义：某个节点的前驱节点指所有值小于该节点的节点中值最大的节点
举例来说：途中的树中，9的前驱是8,8的前驱是7,7的前驱是6,2的前驱是1,1没有前驱。。。
2. 如何求某个节点的前驱呢？
- 若一个节点有左子树，那么该节点的前驱节点是其左子树中值最大的节点
- 若一个节点没有左子树，且该节点是其父节点的右边孩子，那么该节点的前驱结点即为其父节点。
- 若一个节点没有左子树，且该节点是其父节点的左边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的右边孩子（可参考例子2的前驱结点是1），那么Q就是该节点的前驱节点
3. java实现
/*
* 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
*/
public BSTNode<T> predecessor(BSTNode<T> x) {
// 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
if (x.left != null)
return maximum(x.left);
// 如果x没有左孩子。则x有以下两种可能：
// (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
// (02) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
BSTNode<T> y = x.parent;
while ((y!=null) && (x==y.left)) {//满足条件，不断往上追溯，直到找到右祖先结点
x = y;
y = y.parent;
}
return y;
}
4. 用到的结论
接下来我们就要证明以上三个结论的正确性，在证明这三个结论正确的过程中需要用到另外三个结论：
结论一：在同一棵树中，若存在关系a<b<c那么任意a和c的共同路径都是b的路径。
结论二：在同一棵树中，若a<b<c 那么任意a和c的共同祖先都是b的祖先（假设共同路径不为空，且b与任意a、c共同祖先都不相等）。
结论三：假设y是x的前驱节点，要么x是y的祖先，要么y是x的祖先
这三个结论是我针对二叉搜索树的性质总结出来的，并不标准，后面我会给出我的证明方法，现在我们还是先拿来用。
三、前驱节点求法的论证
接下来我们就要用这三个结论来证明三种情况下节点的前驱的求法了：
- 如果节点的左子树不为空那么节点一定是左子树的最大节点：
证明：证明这一点我们只需要证明在节点x存在左子树的情况下节点x的前驱一定在x的左子树中即可。
首先我们假设节点x，左子树最大节点为y，假设在树的某一处存在一个节点z，满足y<z<x（z必然不在x的左子树中）。我们只需要证明z不存在即可。
根据结论一可以知道从根节点到节点x都是x和y的共同路径，所以x也是z的路径上的祖先，同时z<x所以z位于 x的左子树中，这和y是x左子树中最大节点矛盾，故树中不存在一个值z满足y<z<x。所以如果节点的左子树不为空那么节点一定是左子树的最大节点成立。
- 若一个节点没有左子树，且该节点是其父节点的右边孩子，那么该节点的前驱结点即为其父节点：
证明：同样我们假设节点x的父节点为y，x为y的右孩子所以y<x,假设在树中存在一个值z满足，y<z<x，那么由结论结论一可知从根节点到节点y都是x和y的共同路径，那么y亦是节点z的路径上的祖先之一，且z>y，所以z位于y的右子树上此时y的右孩子是x，所以z必然位于x的左子树上，这与x没有左子树矛盾，所以不存在z使y<z<x，y即是比节点x小的最大节点。所以若一个节点没有左子树，且该节点是其父节点的右边孩子，那么该节点的前驱结点即为其父节点。
- 若一个节点没有左子树， 且该节点是其父节点的左边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的右边孩子（可参考例子2的前驱结点是1），那么Q就是该节点的前驱节点（也可能不存在）。
证明： 该结论等价于：当节点x的前驱节点存在时，x的前驱是离x最近的x的祖先中右节点为x祖先的节点。接下来我们证明x前驱存在时的情况。
由结论三可知，假设z是x的前驱，那么要么z是x的祖先，要么x是z的祖先，因为z<x且x没有左子树，所以x的子树中不存在比x小的值，可见此时z是x的祖先，且由于x大于z所以x位于z的右子树中
假设y是离x最近的x祖先中右节点为x的祖先的节点，
(1) 假设z是x的前驱，且z在y的上层，那么存在关系z<x,y<x。由于z是x的前驱故z<y<x关系不成立，所以有y<z<x成立，由结论一可知y和x的任意公共路径均是z的路径，然而z位于y的上层，所以该结论不成立。
(2) 假设z是x的前驱，且z在y的下层和x的上层之间，且由于z是x的前驱故z<y<x关系不成立，所以y<z<x，所以z位于y的右子树内，x位于y的右子树内，这与y是离x最近的右节点为x祖先的节点假设相悖，故结论不成立。
综上，x的前驱节点只能是y。
四、证明结论二：在同一棵树中，若a<b<c 那么任意a和c的共同祖先都是b的祖先（假设共同路径不为空，且b与任意a、c共同祖先不相等）。
证明：
现假设一颗存在a<b<c的树，假设a和c的祖先分别为[ac(0),ac(1),ac(2),...,ac(n),ap(n+1),ap(n+2),...],[ac(0),ac(1),ac(2),...,ac(n),cp(n+1),cp(n+2),...]
此时a和c共同祖先集合为[ac(0),ac(1),ac(2),...,ac(n)]
现在我们假设我们要将与b相等的d插入树中，那么，d必然会插到b的位置，即b与d等价。
所以我们只要证明d插入后的路径经过a、c的共同祖先即可。
- 当共同祖先数量等于1时，ac(0)为根节点，所以往ac(0)中插入d时ac(0)一定是d的祖先。
- 我共同祖先数量大于1时：
我们采用数学归纳法来证明共同祖先数量大于1时d插入一定会经过a、c的共同祖先
定义插入位置p，
(1) p = 0时，插入的节点为ac0(根节点)，插入后ac0成为d的祖先，且由于（ac1 - ac0）* （d - ac0） > 0，所以d会继续插入下个节点ac1，
(2) p > 0时，我们假设当前插入的节点位置为n-2时，ac(n-2)
成为d的祖先且d要插入下个节点为ac(n-1)，成立。我们只需要证明d插入下个节点ac(n-1)时ac(n-1)将成为d的祖先且d将继续插入ac(n)即可。
(3) 当d插入ac(n-1)时，由于(ac(n)-ac(n-1)) * (d - ac(n - 1)) > 0所以当d插入到ac(n-1)时ac(n-1)将成为d的祖先，并且d将继续插入ac(n).
由数学归纳法可知，任意a、c共同祖先都是d的祖先，即b的祖先。
综合情况1和2可知，在同一棵树中，若a<b<c 那么任意a和c的共同祖先都是b的祖先（假设共同路径不为空，且b与任意a、c共同祖先不相等）
五、证明结论一：在同一棵树中，若存在关系a<b<c那么任意a和c的共同路径都是b的路径。
证明：
- 由结论二可知当节点b等于任何a和c的公共祖先时，a和c的共同祖先也是b的共同祖先，即a和c的共同路径也是b的路径。
- 当b等于某一个是a和c的共同祖先时，可以证明，b只能是最其下层的公共祖先。
我们可以用反证法来证明：假设b可以是a、c的非最下层公共祖先，那么由于a<b<c可知a和c分别位于b的左右子树上，也就不会再有任何共同的下层（低于b）公共祖先了，所以假设不成立，因此b只可能是a和c的最下层公共祖先。当b是a、c的最下层公共祖先时任意a、c的公共路径都是b的路径显然是成立的。
综合1,2可知结论“在同一棵树中，若存在关系a<b<c那么任意a和c的共同路径都是b的路径。”成立
六、证明结论三：假设y是x的前驱节点，要么x是y的祖先，要么y是x的祖先
证明：
反证法：假设x，y均不是对方的祖先，由于x，y在同一棵树上，那么必然存在一个节点z使x和y分别位于y和x的左右子树上，这样也就存在关系y<z<x，那么y就不再是x的前驱节点，矛盾。所以当y是x的前驱节点时要么x是y的祖先要么y是x的祖先。
