二叉树的后继节点

struct rbtree* successor(struct rbtree *node) {
    if (!node) return NULL;
    if (node->right) {
        /* 右子树的最左子树 */
        node = node->right;
        while (node->left) node = node->left;
        return node;
    } else {
        /* 向上直到当前节点是其父节点的左子树(后继为父节点)
           或者父节点为NULL(此时后继节点不存在返回NULL) */
        struct rbtree *parent = _rb_parentof(node);
        while (parent && node == parent->right) {
            node = parent;
            parent = _rb_parentof(node);
        }
        return parent;
    }
}