Когда два дерева равны?

Question

Если обход по порядку двух двоичных деревьев (не двоичных деревьев поиска) одинаков, гарантирует ли это, что два дерева одинаковы?порядок и обратный порядок одинаковы?

Answer 1

Определенно нет. Два дерева

  b
 / \
a   d
   / \
  c   e

и

    d
   / \
  b   e
 / \
a   c

оба имеют обход по порядку a b c d e. На самом деле это вращения, операция , которая сохраняет прохождение порядка .

Answer 2

NO , и это видно на этом простом примере

   3            2          
  2           1   3
 1           0
0  

Оба имеют одинаковый порядок обходы [0,1,2,3]

Но если inorder и preorder обходы одинаковы, то деревья равны.

Answer 3

Я думаю «нет».

Возможно, что два дерева могут быть сбалансированы по-разному, но имеют одинаковый «порядок» значений узлов.Например, если из набора

1,2,3,4,5,6,7

Вы построите дерево:

         4
      2    6
   1   3  5   7

обход в порядке приведет к 1,2,3,4,5,6,7.

однако, если вы выберете другой корневой узел (если список предварительно не отсортирован правильно)

           5
         4   6
       2       7   
     1   3

Эти два дерева дадут одинаковый результат обхода по порядку, но(явно) не идентичны.

или даже

      7
     6
    5
   4
  3
 2
1

и так далее.

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

BSP хранит треугольники в дереве.Каждый узел содержит треугольник или фасет.Левый узел содержит все дочерние элементы, которые находятся «позади» фасета, в то время как правый дочерний элемент содержит все, что находится «впереди».Выполните повторение, как и ожидалось.

Если вы выберете самый левый аспект сцены в качестве корня, то правый ребенок будет владеть каждым другим аспектом.Если вы примете плохое решение для правильного ребенка, произойдет то же самое.Для каждого вполне возможно создать BSP-компилятор, который с помощью идиотского анализа создает «дерево», которое на самом деле представляет собой список (как в моем последнем примере выше).Проблема состоит в том, чтобы разделить набор данных так, чтобы каждый узел делил оставшийся список как можно более равномерно.Это одна из причин того, что BSP обычно генерируются во время компиляции, поскольку создание одного для очень сложной геометрии может занять часы, чтобы найти оптимальное решение.