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

Question

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

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

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

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

Answer 1

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

Answer 2

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) 
} 

Answer 3

Я вижу, что вы получили ответы о том, как получить длиной кратчайшей ветви, но ваше домашнее задание на самом деле вернуть филиал самих, по-видимому, как список узлов. Итак, вот исполняемый псевдокод (то есть, 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 4

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

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