Я пытаюсь понять, что делает алгоритм

-2

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

c <- 0 
    while p ≠ q 
     if right[p] ≠ NULL 
     p <- right[p] 
     while left[p] ≠ NULL 
      p <- left[p] 
     else 
     if left[p] = NULL 
      c <- c + 1 
     while p = right[parent[p]] 
      p <- parent[p] 
     p <- parent[p] 
    return c

источник

2014-01-26 user2976686

Он подсчитывает количество листьев между узлами p и q, если вы перемещаете узлы по порядку по их значениям.

источник

2014-01-26 13:18:41

, алгоритм работает только в том случае, если дерево является деревом двоичного поиска или его не является matther? – user2976686

«в порядке их значений», очевидно, не будет работать, если это не дерево поиска *, а код предполагает, что это * двоичный *. так в чем вопрос? –

Он был помечен как BST. –

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

источник

2014-01-26 13:16:41 racraman

Что делать, если p = q изначально? –

Я пытаюсь понять, что делает алгоритм

ответ

Смежные вопросы