Алгоритм возврата длины кратчайшей ветви в двоичном дереве

Question

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

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

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

Пожалуйста, укажите псевдокод для этого алгоритма.

Answer 1

Я вижу, что вы получили ответы о том, как получить длину самой короткой ветви, но ваше домашнее задание фактически состоит в том, чтобы вернуть саму ветку , предположительно в виде списка узлы. Итак, вот исполняемый псевдокод (т. Е. Python), чтобы фактически вернуть ветвь, используя None для обозначения нуля:

def MinBranch(l, r, x):
  if x is None: return []
  left_one = MinBranch(l, r, l(x))
  right_one = MinBranch(l, r, r(x))
  if len(left_one) < len(right_one):
    tail = left_one
  else:
    tail = right_one
  return [x] + tail

Answer 2

Посмотрите на обе ветви. Найти длину кратчайшего пути в каждом. Добавьте один к меньшему и считайте его самой короткой ветвью.

Answer 3

Вы также можете найти его в O (2 ^R ), где R - результат. Полезно, если дерево очень несбалансированное или бесконечное. Это <= O (N). </p>

Вы можете сделать это с помощью итеративно-углубленного DFS.

Answer 4

function recurseMin(n)
{
if r(n) is null and l(n) is null, return 1
if r(n) is not null, rightSum = recurseMin( r(n-1) )
if l(n) is not null, leftSum = recurseMin ( l(n-1) )
return 1 + min( leftSum, rightSum )
}