Самая короткая ветвь в бинарном дереве?

Question

Двоичное дерево может быть закодировано с использованием двух функций l и r такой, что для node n, l(n) дают левому потомку n, r(n) дать право ребенку n.

Ветвь дерева - это путь от корня к листу, Длина ветви до определенного листа - это число дуги на пути от корня к этому листу.

Пусть MinBranch(l,r,x) будет простым рекурсивным алгоритмом для взять двоичное дерево, закодированное функциями l и r вместе с корневым узлом х для двоичного дерева и возвращает длину самой короткой ветви двоичного файла дерево.

Дайте псевдокод для этого алгоритма.

Хорошо, так что в основном это то, что я придумал:

MinBranch(l, r, x)
{
    if x is None return 0

    left_one = MinBranch(l, r, l(x))

    right_one = MinBranch(l, r, r(x))

    return {min (left_one),(right_one)}
}

Очевидно, что это не прекрасно и не идеально. Я был бы признателен, если бы люди могут помочь мне сделать это идеально и работать - любая помощь будет оценено.

Answer 1

Я сомневаюсь, что кто-нибудь решит домашнюю работу за вас. Подсказка: возвращаемое значение должно обязательно расти с ростом дерева, верно? Однако я не вижу никаких числовых литералов в вашей функции, кроме 0 и операторов сложения. Как вы будете возвращать большие числа?

Еще одна точка зрения на ту же проблему: в любое время вы пишете рекурсивную функцию, она помогает перечислить «при каких условиях я должен перестать называть себя? Что я возвращаю в каждом случае?»

Answer 2

Вы на правильном подходе, но вы не совсем там; ваш рекурсивный алгоритм всегда будет возвращать 0. (хотя логика почти верна ...)

обратите внимание, что длина ответвлений на единицу меньше длины ответвления; поэтому left_one и right_one должны быть 1 + MinBranch....

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

Answer 3

Похоже, у вас это почти получилось, но рассмотрим пример:

      4

   3     5

Когда вы проследите через MinBranch, вы увидите это в своем MinBranch(l,r,4) Звоните:

left_one = MinBranch(l, r, l(x))
         = MinBranch(l, r, l(4))
         = MinBranch(l, r, 3)
         = 0

Это имеет смысл, в конце концов, 3 - это листовой узел, поэтому, конечно, расстояние до ближайшего конечного узла равно 0. То же самое происходит для right_one.

Но тогда вы окажетесь здесь:

return {min (left_one),(right_one)}
     = {min (0), (0) }
     = 0

но это явно не так, потому что этот узел (4) не является листовым узлом. Ваш Код забыл сосчитать текущий узел (упс!). Я уверен, что вы можете управлять чтобы исправить это.

---

Теперь, на самом деле, то, как ты это делаешь, не самое быстрое, но я не уверен, что это актуально для этого упражнения. Посмотрите на это дерево:

         4
       3   5
     2
   1

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

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

Answer 4

То, что у вас там, похоже на алгоритм поиска в глубину, который должен будет искать по всему дереву, прежде чем вы найдете решение. Вам нужен алгоритм поиска в ширину , который может вернуться, как только найдет решение, не выполнив полный поиск

Answer 5

То, что вы создали, можно рассматривать как поиск в глубину. Однако, учитывая, что вы ищете (самая короткая ветвь), это может быть не самый эффективный подход. Подумайте, как ваш алгоритм будет работать на дереве, которое было очень тяжелым с левой стороны (корневого узла), но имело только один узел с правой стороны.

Подсказка: рассмотрите возможность поиска в ширину.