c - 在二叉搜索树上找到第一个大于 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 的字母(它应该返回 O)但是它返回给我 N。

Answer 1

你已经完成了 90% 的工作。请允许我完成剩下的 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;
   }
}

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