二进制搜索树的伪代码-Java 学习之路

在二叉搜索树中，密钥x的前导是小于x的密钥y，并且对于该密钥，没有其他密钥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
}

2 回答

我以前的答案来自你的问题的简短描述 - 你正在寻找的只是树中的前身 . 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;
}

回复于 2024-05-06T17:30:27+08:00

如果没有任何左节点存在，那么就不能有任何前任节点 . 否则左子树中的max元素将是前一个

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);
}

回复于 2024-05-06T17:30:27+08:00

二进制搜索树的伪代码

2 回答

相关问题