在二叉搜索树中,键 x 的前驱是小于的键 y x,并且没有其他键 z 使得 z 小于 x 且大于 比 y。
给出一个算法的伪代码,该算法采用密钥 x 并返回 如果 x 是树中最小的键,则前驱 y 或 nil。假设二进制 搜索树使用数组 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
}
我之前的答案是对你的问题进行了糟糕的阅读 - 你正在寻找的只是树中的前身。 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;
}
如果不存在任何左节点,则不能有任何前驱节点。否则左子树中的最大元素将是前驱
public int findmax(Node root) {
if (root == NULL)
return INT_MIN;
int res = root->data;
int lres = findMax(root->left);
int rres = findMax(root->right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}
public int findPredecessor(Node node) {
if(node == null) return null;
if(node->left == null) return null;
return findMax(node->left);
}