Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение?

@Sammm · Регистрация: 21.10.2012

Author24 — интернет-сервис помощи студентам

Вот примерная рекурсивная функция, но я не знаю, как выйти из нее в нужный момент.

C++

void range(Node *root, int r)
{
    if (root==NULL) return;
    range(root->left, r);
    if(root->key > r) 
       {
          printf("%d\n", root->key); 
          return; //значение найдено, надо здесь выйти из функции, но она рекурсивная, полностью выйти не получается
       }
    range(root->right, r);
}

root - корень дерева
r - заданное значение

Если Вам не нравится моя идея, предложите свою.

@lowercase · 30.06.2013, 02:36

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

@Sammm · 30.06.2013, 03:44 **[ТС]**

@lowercase, Такой алгоритм не сработает.
Пусть дано такое двоичное дерево поиска. Надо найти минимальный элемент, превышающий, например, 5. Это будет 6. Как оформить этот поиск в программе?

@~SERG · 30.06.2013, 12:12

C++

void range(Node  *root,  int rr)
{
    int value = 2E9;
 
    find(root, rr, &value);
    printf(" %d\n\n", value);
}
    
 
 
void find(Node  *root, int rr, int *v)
{
 
    if(root == 0)
        return;
 
    find(root->left, rr, v);
 
    if(root->data > rr  &&  root->data  <  *v)
        *v = root->data;
 
    find(root->right, rr, v);
}

data - информационное поле в дереве

@Sammm · 30.06.2013, 15:30 **[ТС]**

@~SERG, Спасибо. А можно ли как-нибудь упростить алгоритм, если у каждого элемента будет указатель на родительский элемент?

@lowercase 213 / 202 / 85 Регистрация: 09.05.2012 Сообщений: 494
	30.06.2013, 02:36	2
	так ведь в двоичном дереве елементы слева всегда меньше корневого, а справа - больше. поэтому не обязательно ити в обе стороны. просто проверяйте левый узел, если он меньше заданого значения, а корень больше - вы нашли его. если корень меньше - идете вправо. зы: на ходу придумал. так, что могу ошибатся 1

@Sammm 3 / 3 / 5 Регистрация: 21.10.2012 Сообщений: 182
	30.06.2013, 03:44 [ТС]	3
	@lowercase, Такой алгоритм не сработает. Пусть дано такое двоичное дерево поиска. Надо найти минимальный элемент, превышающий, например, 5. Это будет 6. Как оформить этот поиск в программе? Миниатюры 0

@Sammm 3 / 3 / 5 Регистрация: 21.10.2012 Сообщений: 182
	30.06.2013, 15:30 [ТС]	5
	@~SERG, Спасибо. А можно ли как-нибудь упростить алгоритм, если у каждого элемента будет указатель на родительский элемент? 0