На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Поиск пути в бинарном дереве
Всем хай! Сходу к делу!

Есть такая структура, описывающая узел ДДП:
ExpandedWrap disabled
    структура "Узел дерева"
      ключ (целое)
      ссылка на левое
      ссылка на правое


И надо найти максимальный путь между его 2мя вершинами (любыми), причем эти вершины должны иметь различное число потомков. В бинарном дереве не меньше 2ух узлов.
----------------------------------------
В вики ЭКСПЕРТЫ(!) пишут, что потомки - все узлы, располагающиеся ниже узла, т е прямые дети НЕ РАВНО потомкам, т к прямых детей узла может быть {0; 1; 2}. Но мне кажется, что в анализе достаточно будет смотреть только на прямых детей.

Вроде гарантировано, что макс. путь проходит ЧЕРЕЗ корень дерева, даже, если отсутствует какая-либо ветвь у корня, поправьте, если не так это.
Находим высоту левого поддерева (от корня). Если левой ветви нет, то высота = 0, ничего страшного, это не мешает алгоритму. Если левая ветвь есть, то гарантировано первый узел, от которого строится искомый путь, является ЛИСТОМ, иначе от корня строится путь и он имеет одного прямого ребенка.

Находим высоту правого поддерева (от корня). второй узел, до которого строится путь является листом.
Если слева был лист и справа был лист, то макс. путь = высота (слева) + высота(справа) - 1 ??
Если слева нет поддерева от корня, то макс. путь = высота (справа)??

Т е для решения надо применить ТОЛЬКО вспомогательную функцию получения высота заданного дерева, да?? Или здесь все гораздо тоньше? Были мысли делать БФС еще...не знаю...

подскажите, как быть-то, буду признателен

p.s. не исключаю, что все, что выше написал по своему алгоритму является чушью и алгоритм здесь абсолютно другой нужен)

Добавлено
кстати, я понял, что макс.путь необязательно должен проходить через корень исходного ДДП...мда..сложнее тут все (как обычно!).
значит, надо сначала найти "корень", так сказать точку перегиба макс. пути...
    Навскидку рисуется такое.

    Строим пути от корня ко всем листьям. Дополняем каждый узел его уровнем и, возможно, полным путём. Если что лишнее - потом при оптимизации удалится. Идём обратно. Для каждого не-листа имеем 1 или 2 потомка. У каждого потомка имеется свой текущий максимальный путь. Соответственно получаем два значения - максимальный путь от текущего узла до дальнего листа (тот самый текущий максимальный путь) и длину пути через текущий узел до дальних листьев. Забираемся так по дереву до корня. В результате получаем массив максимальных путей, откуда берём самый-самый максимум. Всё.
    Цитата Akina @
    Всё

    )

    а неужели нельзя обойтись высотами левого и правого поддерева для текущего узла...
    если получить ДЛЯ каждого узла исходного ДДП высоту левого и правого поддерева. Разве MAX(left(h) + right(h)) не будут показывать узел, который является точкой перелома макс.пути? Ведь если знать корень поддерева, через который проходит макс.путь, то дальше вроде уже легко становится (вроде!)
    Цитата FasterHarder @
    а неужели нельзя обойтись высотами левого и правого поддерева для текущего узла...
    если получить ДЛЯ каждого узла исходного ДДП высоту левого и правого поддерева.

    Так я именно это и описываю. Просто я изначально предполагаю, что ничего этого - ни максимальной для узла глубины ветви его потомков (по отдельности), ни путей, ни чего-то ещё,- не имеется.

    То, что ты говоришь - это в моём описании обратный ход.
    Сообщение отредактировано: Akina -
    Akina, у меня есть уже готовая (и работающая) функция нахождение высоты дерева.
    В итоге резюмирую алгоритм.
    Надо найти среди всех узлов исходного ДДП вершину, у которой left(h) + right(h) --> max. Как это сделать? Обходом (любым), как я понимаю рекурсивным. Думаю, что справлюсь, на крайняк заведу глобальную переменную max_height.

    После этого 3 случая имеем:
    1. если левое поддерево пустое, то ответ right(h).
    2. если правое поддерево пустое, то ответ left(h).
    3. если есть оба сына, то ответ: right(h) + left(h) - 1.

    Один из концов макс. пути - ЛИСТ(!), другой с 1 или 2 детьми. Поэтому в формуле п3 (-1), чтобы подняться на уровень выше от листа.
    Еще такой момент: мне ведь по задаче надо найти лишь ДЛИНУ макс.пути, при этом не нужно находить между какими узлами он строится. Хотя добавить эти узлы вроде несложно...

    Если все-таки я где-то прогнал здесь, то просьба поправить)
    Цитата FasterHarder @
    В вики ЭКСПЕРТЫ(!) пишут, что потомки - все узлы, располагающиеся ниже узла, т е прямые дети НЕ РАВНО потомкам, т к прямых детей узла может быть {0; 1; 2}. Но мне кажется, что в анализе достаточно будет смотреть только на прямых детей.

    Вместо диванных ЭКСПЕРТОВ(!) читайте Кнута.
    FasterHarder
    Ну всё так.
    Как я понимаю, у тебя вся проблема - это как именно сделать алгоритмически, верно? Я бы делал так.

    Добавляем каждому узлу свойство "уровень". У корня - 1, у его дочек - 2, и так далее. Заполняем поиском в ширину или в глубину - как захочешь. Добавляем каждому узлу свойство "длина". Обрабатываем полученный список поиском "из глубины к поверхности" (т.е. начинаем с макс. глубины, и в порядке уменьшения послойно). Для узла "длина" = 1 + макс("длина правого", "длина левого"), при отсутствии потомка справа и/или слева считаем его длину за ноль. Также считаем "текущий максимум" = 1 + "длина левого" + "длина правого" и сравниваем его с текущим глобальным (который изначально нулевой), если больше - запоминаем новое значение. Когда дойдём до корня и обработаем его - выводим полученный глобальный "текущий максимум".
    В общем у меня вроде(!) все получилось, правда такое чувство, что все это дело можно кодировать гораздо точнее и оптимальнее.
    Вот главная функция, которая находит узел, через которую пройдет макс.путь удовлетворяющий условиям:

    ExpandedWrap disabled
      void Find_root_max_path(BST *proot, BST **pnode_path, int pmax_height)
      {
          if(proot != NULL)
          {
              int current_height = Height(proot->left) + Height(proot->right);
              if(current_height > pmax_height)
              {
                  pmax_height = current_height;
                  *pnode_path = proot;
              }
              Find_root_max_path(proot->left, pnode_path, pmax_height);
              Find_root_max_path(proot->right, pnode_path, pmax_height);
          }
      }


    а ведь наверняка это можно реализовать ЧЕРЕЗ функцию, которая в качестве ответа вернет указатель на узел, являющийся "точкой перелома" макс.пути - вообще без понятия, как это реализуют на рекурсии... и так сойдет (с) )

    Добавлено
    Akina, спс за помощь

    scrambrella, Кнута я бы читал с большим удовольствием, если бы не одно НО...
    Цитата FasterHarder @
    scrambrella, Кнута я бы читал с большим удовольствием, если бы не одно НО...

    Лень матушка - единственное но, по которому никто не читает Кнута. Чтение Кнута требует ЗНАЧИТЕЛЬНЫХ умственных усилий, а люди стремятся экономить мышление.
    Скрытый текст
    scrambrellaда, все верно...я его НЕ понимаю, тем более он вводит какой-то собственный язык для всех примеров (насколько я помню) + вроде у него оооооочень много всесторонней математики в объяснениях (всякие алгоритмические доказательства - полная жесть и на мое ИМХО это чуть ли не самое сложное - уметь доказывать тот или иной алгоритм
    Мой автор Г.Шилдт) доступно, авторитетно объясняет...
    Цитата FasterHarder @
    Скрытый текст
    scrambrellaда, все верно...я его НЕ понимаю, тем более он вводит какой-то собственный язык для всех примеров (насколько я помню) + вроде у него оооооочень много всесторонней математики в объяснениях (всякие алгоритмические доказательства - полная жесть и на мое ИМХО это чуть ли не самое сложное - уметь доказывать тот или иной алгоритм
    Мой автор Г.Шилдт) доступно, авторитетно объясняет...

    Даже пропуская тексты программ можно кое-что понять. Математика в Кнуте относительно понятная, часть алгоритмов с поясняющими картинками. Собственный ЯП Кнута раздражает. Сам его пока не освоил. Как он сам пишет - это что-то близкое к ассемблеру.
    1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
    0 пользователей:


    Рейтинг@Mail.ru
    [ Script execution time: 0,0442 ]   [ 19 queries used ]   [ Generated: 4.12.21, 05:23 GMT ]