在二叉搜索树上找到第一个大于 X 的键

Question

The successor of an element in a BST is the element's successor in the sorted order determined by the inorder traversal. Finding the successor when each node has a pointer to its parent node is presented in CLRS's algorithm textbook (Introduction to Algorithms by MIT press).

有没有办法找到结构中没有 parent 的第一个大于 X 的值？喜欢：

typedef struct tree tree;
struct tree{
   int value;
   tree *left;
   tree *right;
};

//Function:  

tree *find_first_bigger(tree *t, int x){}

我尝试使用：

tree *find_first_bigger(tree *t, int x){
   if(t == NULL)
      return NULL;

   if((*t)->value > x)
      find_first_bigger((*t)->left, x);

   else if((*t)->value < x)
      find_first_bigger((*t)->right), x);
   else if((*t)->value == x){
      if((*t)->right != NULL) 
         return tree_first_bigger((*t)->right);
      else
         return tree;
   }
}

在这个例子中（它使用的是字母，但这不是问题），如果我尝试搜索第一个大于 N（它应该 return 我 O）但是它 return 是我 N.

Answer 1

您可以对代码进行一些更改：

您必须 return 来自递归调用的值
如果找不到值，returnNULL。这意味着 returning NULL if t->right == NULL on the last if.
往左走时，如果那里没有找到值，答案一定是节点本身。在N的情况下，就是我们左转的最后一个节点：O。如果是 P，答案就是 T 本身。

完成所有这些更改后，代码应如下所示：

tree *find_first_bigger(tree *t, int x){
   if(t == NULL)
      return NULL;

   if(t->value > x) {
      tree *answer = find_first_bigger(t->left, x);
      if (answer != NULL) 
          return answer;
      return t;
   } else if(t->value < x) {
      return find_first_bigger(t->right, x);
   } else if(t->value == x) {
      if (t->right != NULL)
          return tree_first_bigger(t->right);
      return NULL;
   }
}

你可以找到我用来测试的完整代码in this gist。

Answer 2

在您的问题中，您似乎表示要找出给定值 'x' 的 InOrderSuccessor()。

如果树中不一定存在'x'，我们需要改变算法。根据您提供的示例和问题陈述，这里是查找 BST 中下一个元素的代码。

关键案例是：

不存在更大的元素，因为'x'是最大的。
'x' 有权利 child ?
是：获得 x 右边的 left-most child sub-tree。
否：return parent.

主要观察是，无论何时我们直接进入树，我们都不会更新 parent 指针。

  tree *ptr = root;
  tree *prnt = NULL;
  while (ptr != NULL) {
      if (x == ptr->key) {
          if (ptr->right != NULL) {
              return GetLeftMostChild(ptr->right);
          } else {
              return prnt;
          }
      } else if (x > ptr->key) {
          ptr = ptr->right;
      } else {
          prnt = ptr;
          ptr = ptr->left;
      }
  }

这是 leftMostChild() 的定义

tree *GetLeftMostChild(tree *n) {
    tree *ptr = n;
    while (ptr->left != NULL) {
        ptr = ptr->left;
    }
    return ptr;
}

Answer 3

你已经完成了 90% job.Allow 我来完成剩下的 10%。

因为 t 是指向结构的指针，你应该使用 t->left 而不是 (*t)->left 并且相同在访问结构的 right 和 value 字段时适用。

现在，只需将您的函数修改为：

将此添加为函数的第一行

static tree* PTR=NULL;

修改第二个if条件为:

if(t->value > x)
 {
     PTR=t;
     find_first_bigger(t->left, x);
 }

修改第二个else if条件为：

else if(t->value == x)
{
  if(t->right != NULL)
     {
         t=t->right;
         while(t->left!=NULL)
            t=t->left;
         return t;
     }
  else return PTR;
}

因此正确的函数是

tree *find_first_bigger(tree *t, int x)
{
   static tree* PTR=NULL;
   if(t == NULL)
      return NULL;
   if(t->value > x)
     {
         PTR=t;
         find_first_bigger(t->left, x);
     }
   else if(t->value < x)
       find_first_bigger(t->right, x);
   else if(t->value == x)
    {
      if(t->right != NULL)
         {
             t=t->right;
             while(t->left!=NULL)
                t=t->left;
             return t;
         }
      else return PTR;
   }
}

在主函数中，如果返回的指针为NULL，这意味着：该键本身是最大的键。有任何疑问。

Answer 4

我还没有对此进行测试，但我认为它应该可以工作。让我知道是否有误。 //C++ 11

 #include<iostream>
 using namespace std;
 struct BSTNode{
     int val;
     BSTNode* left;
     BSTNode* right;
 };


 int FindJustLarger(BSTNode*& node, int token, int sofarlarge){
    // for invalid inputs it will return intial value of sofarlarge
    // By invalid input I mean token > largest value in BST
    if(node == nullptr)
        return sofarlarge;

    else if(node->val > token){
        sofarlarge = node->val;
        return FindJustLarger(node->left, token, sofarlarge);}

    else
        return FindJustLarger(node->right, token, sofarlarge);}

int main(){
    BSTNode* head = new BSTNode{5, nullptr, nullptr};
    FindJustLarger(head, 5, NULL);
    delete head;
    return 0;}

在二叉搜索树上找到第一个大于 X 的键

Find the first key bigger than X on Binary Search Tree

c

algorithm

binary-search-tree