在二进制搜索树中InOrder后继

Question

这是我必须解决的问题：

给出了二进制搜索树中的节点，找到节点 具有比给定的最小键 节点..

经常给出的算法是这个：

bst_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x = y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

.

（你可以找到问题的进一步解释 。）

现在，我想知道这是否可以是另一个解决方案：

bst_successor(x)
    {
            if(x == NULL)
                    return NULL;
            if(x.right != NULL)
                    return abr_min(x.right)
            y = x.p;
            while(y != NULL && y.key < x.key)
            {
                    y = y.p;
            }
            return y;
    }

.

Answer 1

如果一个节点的键永远不等于不同节点的密钥，则代码是正确的。

否则，您的代码无法返回以下图表底部的节点的正确INORDER-CAPERAL。