Найти первый ключ больше, чем X в двоичном дереве поиска

Question

Преемник элемента в BST является преемником элемента в отсортированном порядке , определяемом обходным порядком. Поиск преемника , когда каждый узел имеет указатель на его родительский узел, представлен в учебнике алгоритмов CLRS (Введение в алгоритмы с помощью MIT ).

Есть ли способ найти первое значение, которое больше X без parent в структуре? Как:

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 (он должен вернуться me O) но он возвращает меня N.

Answer 1

Вы сделали 90% от job.Allow мне сделать оставшиеся 10%.

Поскольку т является указателем на структуру, которую вы должны использовать t-> левый вместо (* т) -> левый и то же самое относится и при доступе к правой и значение, полей структуры.

Теперь Просто измените функцию:

Добавить это как первой строке функции

static tree* PTR=NULL; 

Измените второе, если условие в:

Измените второе, если условие равно:

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 2

Некоторые изменения, которые вы можете сделать в вашем коде:

• Вы должны возвращать значения из рекурсивных вызовов

• Если значение не найдено, вернуть NULL. Это означает возвращение NULL, если t->right == NULL на последних 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 3

В вашем вопросе вам показалось, что вы хотите узнать InOrderSuccessor() данного значения 'x'.

Если «x» не обязательно существует в дереве, нам нужно изменить алгоритм. Учитывая приведенный вами пример и инструкцию о проблеме, вот код для поиска следующего элемента в BST.

Основные случаи:

• Нет больше элемент существует, потому что «х» является самым большим.
• «x» имеет ребенка в правильном направлении?
• ДА: получите самый левый дочерний элемент справа от дерева.
• НЕТ: возвращение родителя.

Главное замечание состоит в том, что мы не обновляем указатель родителя, всякий раз, когда мы идем прямо в дерево.

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