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

Question

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

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

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

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

ОК, так что в основном это то, что я придумал до сих пор:

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....

Steping через алгоритм с некоторыми образцами деревьев поможет раскрыть вне череде ошибок, как этот ...

Answer 3

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

Подсказка: рассмотрите подход поиска по ширине.

Answer 4

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

Answer 5

Похоже, у вас почти есть, но рассмотрят следующий пример:

 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) не является листовым узлом. Ваш код забыл подсчитать текущий узел (oops!). Я уверен, что вы можете управлять , чтобы исправить это.

---

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

  4 
     3 5 
    2 
    1 

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

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