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

Question

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

Если нет ответа, то как обход в порядке, так и в предварительном порядке совпадают?

Answer 1

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

b 
/\ 
a d 
/\ 
    c e 

и

d 
/\ 
    b e 
/\ 
a c 

оба имеют заказовМои обход a b c d e. Это, фактически, вращения, операция which preserves inorder traversal.

Answer 2

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

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

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 обычно генерируются во время компиляции, поскольку построение одного для очень сложной геометрии может занять часы, чтобы найти оптимальное решение.

Answer 3

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

3   2   
    2   1 3 
1   0 
0 

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

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