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

Как в АВЛ-дереве найти самую короткую ветвь и удалить ее? - C++

Восстановить пароль Регистрация
 
КЗОИ
Сообщений: n/a
24.09.2011, 22:51     Как в АВЛ-дереве найти самую короткую ветвь и удалить ее? #1
Доброго времени суток.
Нужна помощь. В АВЛ-дереве надо найти самую короткую ветвь и удалить ее.
Я могу удалить только узел по ключу (ну и конечно опять сбалансировать).
Никак не пойму, как это проделать с веткой и как ее вообще найти. ((
Если кто знает, намекните, пожалуйста.
Спасибо за любую информацию.

Добавлено через 13 часов 27 минут
Н-да..
Кажись с форумом промашка вышла..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2011, 22:51     Как в АВЛ-дереве найти самую короткую ветвь и удалить ее?
Посмотрите здесь:

C++ Определить самую длинную и самую короткую из введенных строк
C++ Строки. Вывести на экран самую короткую группу из 0 и 1.
Строки. Вывести на экран самую короткую группу из 0 и 1 C++
C++ Сформировать массив строк. Удалить из него самую короткую строку
В бинарном дереве определить число узлов у которых есть указатель только на одну ветвь. C++
Определить число узлов в дереве, в которых есть указатель только на одну ветвь C++
C++ Открыть заданный текстовый файл, найти в нем и вывести на экран самую короткую строку
C++ Удалить из массива строк самую короткую строку

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Merovingian
54 / 54 / 5
Регистрация: 24.09.2011
Сообщений: 149
25.09.2011, 01:28     Как в АВЛ-дереве найти самую короткую ветвь и удалить ее? #2
обычным DFS это можно сделать, записывая указатели на вершин в стек, я бы еще завел глобальный счетчик длины и рабочий счетчик.

Можно сделать с помощью алгоритма флойда, он для графа, но дерево - это частный случай графа, а именно ациклический орграф. Нужно будет реализовать алгоритм так, чтобы он искал все пути только от корня! Длина пути будет найдена и останется еще раз пробежаться по дереву и удалить ветку длина которой равна той длине, которая найдена с помощью алгоритма флойда, опять же понадобиться стек))
Yandex
Объявления
25.09.2011, 01:28     Как в АВЛ-дереве найти самую короткую ветвь и удалить ее?
Ответ Создать тему
Опции темы

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