Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
4 / 4 / 1
Регистрация: 25.03.2015
Сообщений: 63

Поиск наибольшего элемента в заданной высоте дерева

17.10.2016, 01:57. Показов 842. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Среди вершин, отдалённых от корня на расстояние A, надо найти наибольший элемент. Вот фрагмент кода, тут 3 метода, последний из них должен рекурсивно обойти дерево от корня на расстояние A и вернуть наибольшее значение. Второй метод находит высоту дерева, а первый использует это значение и запрашивает пользователя ввести нужную высоту дерева, чтобы найти наибольшее значение в этой высоте. Не получается с последним методом, не знаю как правильно написать рекурсию обхода всех поддеревьев на уровне A(корень - уровень 1) чтобы оно вернуло наибольший элемент, постоянно дохожу до ошибки что указатель указывает на nullptr.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
void RBtree::high()
{
    int h = height(root);
    int elem = 0;
    if (h)
    {
        int a, i = 1;
        cout << "Enter height: ";
        cin >> a;
        node *p = root;
        if (a <= h && a > 0)
        {
            elem = bypass(root, a);
            cout << "Biggest: " << elem << endl;
        }
        else
            cout << "Incorrect height for search. ";
    }
    else
        cout << "Tree is empty";
}
 
int RBtree::height(node *root)
{
    int h = 0;
    if (root != NULL)
    {
        int l_height = height(root->left);
        int r_height = height(root->right);
        int max_height = max(l_height, r_height);
        h = max_height + 1;
    }
 
    return h;
}
 
int RBtree::bypass(node *root, int a)
{
    int i = 1;
    int elem = 0;
    if (a != 1)
    {
        while (i != a)
        {
            if (root != NULL)
            {
                bypass(root->left, a);
                bypass(root->right, a);
                elem = root->key;
                if (elem < root->key)
                    elem = root->key;
            }
        }
    }
    else
        return p->key;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
17.10.2016, 01:57
Ответы с готовыми решениями:

Поиск наибольшего элемента дерева
Помогите, написать функцию, которая находит наибольший элемент дерева. Разработаны универсальные классы, но задача не получается. using...

Нахождение наибольшего элемента дерева
Написать функцию, которая находит наибольший элемент дерева. Добавлено через 3 часа 56 минут помогитее((

Найти величину наибольшего элемента на n-м уровне дерева
Найти величину наибольшего элемента на n-м уровне дерева (корень считать вершиной 0-го уровня).

2
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
17.10.2016, 02:29
L1oN, идея примерно такая же, как и в твоей функции height.
В height ты обходишь сначало левое поддерево, затем правое и находишь максимум из их высот, а останавливаешься тогда, когда доходишь до листа дерева.
В твоем случае теперь вместо остановки на листьях дерева, нужно останавливаться на конкретном уровне дерева.

Может с кодом станет чуть понятнее:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
node * RBtree::bypass(node *root, int cur_h, int max_h) {
    if (cur_h == max_h) // Останавливаем рекурсию на уровне max_h
        return root; // Текущий элемент максимальный
    if (root != NULL && cur_h < max_h)
    {
        // Смотрим максимальный элемент на уровне max_h в левом и правом поддеревьях
        node *l_max = bypass(root->left, cur_h + 1, max_h);
        node *r_max = bypass(root->right, cur_h + 1, max_h);
        
        // Выбираем максимальный их них
        node *max = l_max;
        if (!max)
            max = r_max;
        else if (r_max && r_max->key > max->key)
            max = r_max;
        return max;
    }
 
    return nullptr;
}
1
4 / 4 / 1
Регистрация: 25.03.2015
Сообщений: 63
17.10.2016, 12:40  [ТС]
Да, спасибо, теперь понятно, я не написал условие для выхода с рекурсии при a == h, и так же бы не догадался плюсовать проверяемую высоту каждый раз, вызывая рекурсию. Ваш метод работает правильно, только надо вводить противоположную высоту, то есть, если дерево имеет высоту 4, то чтобы узнать наибольший элемент 1 уровня(корень), мне надо ввести высоту 4, и наоборот, если хочу узнать наибольший элемент 4 высоты, то надо ввести высоту 1, но это пустяк, спасибо большое за объяснение
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
17.10.2016, 12:40
Помогаю со студенческими работами здесь

Вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск заданного элемента
Добавить в класс &quot;Односвязный список&quot; следующие функции: вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск...

[nand2tetris ] Поиск наибольшего элемента
Здравствуйте! Нужно найти поиск троих элементов (наибольший элемент) Есть етот для двоих, но как переобразовать для троих? Никак не могу...

Поиск наибольшего элемента в массиве
ДОброго времени суток. вопрос такой,допустим у меня есть массив, и его размер, как мне найти в нем масое больщое число? заранее...

Составить программу нахождения наибольшего элемента и суммы заданной числовой последовательности
Составить программу нахождения наибольшего элементов и суммы заданной числовой последовательности 23,6,12,89,22,34,56

Поиск наибольшего элемента в бинарном дереве
Доброго времени суток. Есть бинарное дерево, надо найти максимальный элемент и его индекс. Видел код поиска максимального элемента на С++,...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru