Почему изменение обхода с «На заказ» на «Предварительный / Постзаказ» делает неправильный ответ в «Упражнении: эквивалентные двоичные деревья»?

Question

В разделе параллелизма Тур по Голангу есть следующее упражнение. оператор проблемы хочет убедиться, что два входных дерева одинаковы или нет.

Проблема здесь в том, что когда мы меняем порядок обхода с того, чтобы сделать предварительный / последующий заказ, он терпит неудачу. то есть приведенный ниже код работает правильно

if t != nil {
    traverse(t.Left, ch)
    ch <- t.Value
    traverse(t.Right, ch)
}

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

Поскольку мы использовали тот же код для обхода ожидаемого значения, порядок не должен иметь значения (т. Е. Значения передаются на канал в том же порядке ...).

PS: Вы можете найти больше ответов на это упражнение здесь .

Answer 1

Ответ на этот вопрос скорее связан со структурами данных, а не с синтаксисом Голанга, и связан со свойствами дерева двоичного поиска.

Как указано в документации, tree.New func возвращает случайный сконструированный ключ:

New возвращает новое случайное двоичное дерево, содержащее значения k, 2k, ..., 10k.

Обход по порядку обещает отсортировать выходные данные, но это не относится к обходу по предварительному и последующему порядку, и поэтому выходные данные не будут равны для этих обходов.

Рассмотрим следующее дерево:

       4
      / \
     2   5
    / \
   1   3

InOrder traverse: 1, 2, 3, 4, 5

PostOrder traverse: 1 3 2 5 4

Для получения дополнительной информации: Двоичные деревья