algorithm - 二叉搜索树的伪代码

Question

在二叉搜索树中，键 x 的前导是键 y 小于x，并且没有其他键 z 使得 z 小于 x 且大于比y。

给出一个算法的伪代码，该算法接受一个 key x 并返回前导 y 或 nil 如果 x 是树中的最小键。假设二进制搜索树使用数组 left、right 和 parent 表示。给出伪代码对于使用的任何辅助功能。

我不太确定如何处理这个问题。但这是我的尝试:

伪代码:

//Takes in key x

BST(x)
{

if ( x < parent[x] )

    return nil

if( parent[x] < x )

   return parent[x] // parent[x] = y
}

Answer 1

我之前的回答是对你的问题的粗略阅读 - 你正在寻找的只是树中的前身。 http://www.quora.com/How-can-you-find-successors-and-predecessors-in-a-binary-search-tree-in-order

这是他们在那篇文章中使用的代码:

public static TreeNode findPredecessor(TreeNode node)
{
    if (node == null)
        return null;

    if (node.getLeft() != null)
        return findMaximum(node.getLeft());

    TreeNode parent = node.getParent();

    TreeNode y = parent;
    TreeNode x = node;
    while (y != null && x == y.getLeft())
    {
        x = y;
        y = y.getParent();
    }

    return y;
}