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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Sammm
3 / 3 / 1
Регистрация: 21.10.2012
Сообщений: 182
#1

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

30.06.2013, 02:28. Просмотров 736. Ответов 4
Метки нет (Все метки)

Вот примерная рекурсивная функция, но я не знаю, как выйти из нее в нужный момент.
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++
Посредством двоичного поиска найти такой минимальный элемент, чтобы выполнялось заданное условие C++
Реализация словаря в двоичном дереве поиска C++
C++ Реализация словаря в двоичном дереве поиска
C++ Подсчет уровней в двоичном дереве поиска
Найти первый элемент заданного массива, превышающий значение, введённое с клавиатуры C++
В массиве вещественных чисел найти элемент, превышающий его среднее арифметическое C++
Вывести К-тый отрицательный элемент в упорядоченном дереве поиска с просмотром TLR C++
C++ в матрице К(7,7) найти минимальный элемент и заменить его на значение среднего
C++ Поиск в двоичном дереве
C++ Найти сумму листьев в бинарном дереве поиска
Представление выражения в двоичном дереве C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lowercase
212 / 201 / 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     Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение?
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru