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

Найти длину (количество узлов) на пути от корня дерева до ближайшего узла

04.12.2020, 02:32. Показов 6139. Ответов 4

Студворк — интернет-сервис помощи студентам
Добрый вечер, нуждаюсь в помощи с этим заданием... Было бы очень неплохо помочь, нашел похожий вопрос 2016 года, но тот код не работает...
Найти длину (количество узлов) на пути от корня дерева до ближайшего узла, содержащего данный элемент (если такого узла в дереве нет, то считать результат равным -1)
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
04.12.2020, 02:32
Ответы с готовыми решениями:

Длина пути от корня дерева до вершины (узла) с ключом n
Составить программу, которая определяет длину пути от корня дерева до вершины (узла) с ключом n (если n не входит в дерево, то длину пути...

Вычислить длину пути бинарного дерева от корня до ближайшей вершины
Напишите программу, которая формирует бинарное дерево поиска, выводит построенное дерево на экран и вычисляет длину пути (число ветвей) от...

Сетевые алгоритмы. Найти кратчайшие пути от узла 1 до всех остальных узлов
Найти кратчайшие пути от узла 1 до всех остальных узлов . Описать алгоритм .

4
0 / 0 / 0
Регистрация: 04.12.2020
Сообщений: 6
04.12.2020, 23:56  [ТС]
Если еще кого-то интересует этот вопрос, то вот, я сделал, может быть не очень эффективно, зато работает.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int pLength(Tree* root, int x, int& lvl) {
    if (root != NULL) { //пока дерево не пустое
        lvl++; //повысить уровень дерева
        if (root->data == x) //корень равен этому элементу?
            return lvl; //вернуть уровень
        int savedLevel = lvl; //сохранить уровень
        int pl = pLength(root->left, x, lvl); // присвоить pl значение рекурсии
        if (pl == lvl) //если они равны
            return lvl; //вернуть уровень
        lvl = savedLevel; //загрузить уровень
        int pr = pLength(root->right, x, lvl); // присвоить pr значение рекурсии
        if (pr == lvl) //если они равны
            return lvl; //вернуть
    }
    return 0; //если нет, вернуть 0
}
и где-то в main
C++
1
2
3
4
5
int lvl = 0, l;
cout >> "Введите искомое число: ";
cin << l;
...
len = pLength(root, l, lvl) - 1; //путь от корня до определенного элемента
0
41 / 26 / 17
Регистрация: 11.11.2019
Сообщений: 92
05.12.2020, 00:25
Если Вам интересно, могу на несколько моментов в коде указать, чтобы повысить и читаемость кода, и оптимизировать его хотя бы по памяти, поскольку вы слишком много переменных вводите на момент рекурсий.
0
0 / 0 / 0
Регистрация: 04.12.2020
Сообщений: 6
08.12.2020, 17:51  [ТС]
Было бы неплохо, если не сложно)
0
41 / 26 / 17
Регистрация: 11.11.2019
Сообщений: 92
08.12.2020, 18:33
Лучший ответ Сообщение было отмечено Matrixon как решение

Решение

Matrixon, Смотрите. У вас идёт возвращение функции. В случае с рекурсиями, что находят какую-либо степень или факториал - тема хорошая, в случае с бинарными деревьями лучше использовать смену значения в адресе(могу ошибаться в правильности формулировки) самой переменной, поскольку передавать значения так, как сделали Вы - дело немного гиблое. Легче всё сделать через void.

Я у себя немного позаимствовал функцию:

C++
1
2
3
4
5
6
7
8
9
10
11
void findAmountOfParents(bin_tree* tree, int num, int amount, int& len)
{
    if (tree == nullptr) { return; } // Для указателей лучше использовать nullptr
    if (num == tree->numOfTop)
    {
        len = amount;
                return; // поскольку дальше нет смысла искать
    }
    findAmountOfParents(tree->left, num, amount + 1, len); // Вы пройдёте по всем вершинам, но изменения в len запишутся либо 1 раз, либо len так и останется = -1
    findAmountOfParents(tree->right, num, amount + 1, len);
}
По итогу мы проходим по всем вершинам, кроме тех, что идут после num, берём нам нужную, меняем или не меняем значение в адресе len, и получаем наш итоговый ответ без лишнего выделения памяти.

И сам вызов в main можно немного подредактировать:
C++
1
2
3
4
5
6
int len = -1, x = 0; // для безопасности лучше все переменные инициализировать, даже нулём.
cout >> "Введите искомое число: ";
cin << x;
...
findAmountOfParents(root, x, -1, len); //Можно не объявлять лишние переменные, чтобы задать константные значения
cout << len;
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
08.12.2020, 18:33
Помогаю со студенческими работами здесь

Алгоритм Дейкстры на куче. Найти кратчайшие пути до всех узлов от заданного узла
Уже больше суток бьюсь над формулированием запроса в гугл, чтобы он мне выдал какой-нибудь мануал по реализации алгоритма Дейкстры на...

Запросы к иерархическим данным (Найти путь от корня дерева до узла)
Доброго времени суток! В таблице хранятся иерархические данные (используется hierarchyid). CREATE TABLE . ( BIGINT, ...

Деревья. Найти длину пути из узла a в узел b
дано бинарное дерево. найти длину пути из узла a в узел b.(если такой узел не существует то вывести сообщение об этом) как можно...

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

Найти глубину дерева, представляемую как наибольшая длина пути от корня к листьям.
В общем дано двоичное дерево надо была найти глубину дерева, представляемую как наибольшая длина пути от корня к листьям. Правильно ли...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
Вывод данных через динамический список в справочнике
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа
Maks 01.04.2026
Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .
К слову об оптимизации
kumehtar 01.04.2026
Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр).
Hrethgir 31.03.2026
Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда
anaschu 31.03.2026
В прикрепленном документе раздумья о том, как можно поменять модель в будущем
10 пpимет, которые всегда сбываются
Maks 31.03.2026
1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .
Перемещение выделенных строк ТЧ из одного документа в другой
Maks 31.03.2026
Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave
DevAlt 30.03.2026
Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru