Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Sammm
3 / 3 / 1
Регистрация: 21.10.2012
Сообщений: 182
30.06.2013, 02:28     Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение? #1
Вот примерная рекурсивная функция, но я не знаю, как выйти из нее в нужный момент.
C++
1
2
3
4
5
6
7
8
9
10
11
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 - заданное значение

Если Вам не нравится моя идея, предложите свою.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.06.2013, 02:28     Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение?
Посмотрите здесь:

Представление выражения в двоичном дереве C++
Вывести К-тый отрицательный элемент в упорядоченном дереве поиска с просмотром TLR C++
C++ в матрице К(7,7) найти минимальный элемент и заменить его на значение среднего
Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение? C++
В массиве вещественных чисел найти элемент, превышающий его среднее арифметическое C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lowercase
 Аватар для lowercase
211 / 200 / 34
Регистрация: 09.05.2012
Сообщений: 494
30.06.2013, 02:36     Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение? #2
так ведь в двоичном дереве елементы слева всегда меньше корневого, а справа - больше. поэтому не обязательно ити в обе стороны. просто проверяйте левый узел, если он меньше заданого значения, а корень больше - вы нашли его. если корень меньше - идете вправо.
зы: на ходу придумал. так, что могу ошибатся
Sammm
3 / 3 / 1
Регистрация: 21.10.2012
Сообщений: 182
30.06.2013, 03:44  [ТС]     Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение? #3
@lowercase, Такой алгоритм не сработает.
Пусть дано такое двоичное дерево поиска. Надо найти минимальный элемент, превышающий, например, 5. Это будет 6. Как оформить этот поиск в программе?
Миниатюры
Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение?  
~SERG
3 / 3 / 1
Регистрация: 06.08.2012
Сообщений: 26
30.06.2013, 12:12     Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение? #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
3 / 3 / 1
Регистрация: 21.10.2012
Сообщений: 182
30.06.2013, 15:30  [ТС]     Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение? #5
@~SERG, Спасибо. А можно ли как-нибудь упростить алгоритм, если у каждого элемента будет указатель на родительский элемент?
Yandex
Объявления
30.06.2013, 15:30     Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение?
Ответ Создать тему
Опции темы

Текущее время: 00:05. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru