二叉搜索树的前驱和后继节点

前驱节点val值小于该节点val值并且值最大的节点
后继节点val值大于该节点val值并且值最小的节点

BST.png

前驱节点
1 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"
(例如:节点10,前驱就是8);
2 如果x没有左孩子。则x有以下两种可能;
2.1 x是"一个右孩子"，则"x的前驱结点"为 "它的父结点";

前驱节点.png
图片有个错误,节点8的前驱是节点7

---

2.2 x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点";

前驱节点.png

问题:什么是最低的父节点?
答:我的理解是,要找前驱元素,肯定是找一个有右孩子的父亲节点,并且这个父亲节点的右孩子中一定能找到当前节点.
上图中,节点6没有左孩子,并且是个左孩子.有右孩子的父亲节点有5和10,但是只有在5的右孩子中能找到节点6.

---

后继节点
1 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"
(例如:节点5,后继就是6);
2 如果x没有右孩子。则x有以下两种可能;
2.1 x是"一个左孩子"，则"x的后继结点"为 "它的父结点";
2.2 x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的前驱结点";

BST.png

问题:什么是最低的父节点?
答:我的理解是,要找后继元素,肯定是找一个有左孩子的父亲节点,并且这个父亲节点的左孩子中一定能找到当前节点.
上图中,节点7没有右孩子,并且是右左孩子.有左孩子的父亲节点有5和10,但是只有在10的左孩子中能找到节点7.所以说节点7的后继是节点10

//前驱元素
//节点val值小于该节点val值并且值最大的节点
Node *predecessor(Node *node) {
    Node *ret = NULL;
    // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
    if(node->left != NULL) {
        Node *r = node->left;
        while(r->right) {
            r = r->right;
        }
        ret = r;
    } else {
        // 如果x没有左孩子。则x有以下两种可能：
        // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
        // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
        ret = node->parent;
        while ((ret != NULL) && (node == ret->left)) {
            node = ret;
            ret = ret->parent;
        }
    }
    return ret;
}

//后继元素
//节点val值大于该节点val值并且值最小的节点
Node *successor(Node *node) {
    Node *ret = NULL;
    if(node->right != NULL) {
        Node *l = node->right;
        while(l->left) {
            l = l->left;
        }
        ret = l;
    } else {
        // 如果x没有右孩子。则x有以下两种可能：
        // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
        // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
        ret = node->parent;
        while ((ret != NULL) && (node == ret->right)) {
            node = ret;
            ret = ret->parent;
        }
    }
    return ret;
}