Понимание псевдокода для построения дерева из обхода предзаказа - PullRequest
Новая
       17

Понимание псевдокода для построения дерева из обхода предзаказа

1 голос
/ 05 мая 2011

Мне нужно сделать что-то похожее на задачу, описанную в этом вопросе:
Построить дерево с заданным обходом предварительного заказа

Здесь есть действительно полезный ответ, но я не совсем понимаю псевдокод, поэтому мне было интересно, может ли кто-нибудь помочь мне описать, что происходит. 

k = 0 // Initialize
input = ... get preorder traversal vector from user ... // Get input
Reconstruct(T) // Reconstruct method with tree input
  if input[k] == N // If element of input is N
    T = new node with label N // Make a new node with label N in tree T
    k = k + 1  // Increment k for next loop (Is this whole thing a loop? or a method call?)
    Reconstruct(T.left) // ?????
    Reconstruct(T.right) // ?????
 else // If element of input is L
    T = new node with label L // Make a new node with label L in tree T
    T.left = T.right = null // ?????
    k = k + 1 // Increment k for next loop

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

1 Ответ

2 голосов
/ 05 мая 2011

Там нет петли. k - это глобальная переменная, к которой можно получить доступ в Reconstruct(T). Это просто текущий индекс массива символов (входная строка).

Как объяснено в вопросе, на который вы ссылались ( Contsruct Tree с предварительным обходом ), правильный алгоритм - сделать левого потомка узла, а затем правого потомка. Что вы видите в true разделе if. Если текущий узел оказался листом L, то не давайте ему потомков и возвращайтесь к вызывающей функции.

То, что делает эта функция, следует за левым краем дерева, добавляя дочерние элементы ко всем узлам N и не добавляя дочерние элементы ко всем узлам L (иначе листья), пока строка не завершится.

Редактировать: когда автор псевдокода говорит T.left = T.right = null, это означает, что в данный момент текущий узел не имеет левого или правого дочернего элемента (потому что это лист). Это всего лишь утверждение, и оно не обязательно должно быть в коде.

...