Как отличить два BST

Question

Вот комбинации разных BST с одним и тем же элементом, расположение выглядит по-разному в зависимости от последовательности добавления узлов в древовидную структуру:

  1             1           1                    1         1
   \             \           \                    \         \
    2             2           3                    4         4 
     \             \         / \                  /         /
      3             4       2   4                3         2
       \           /                            /           \
        4         3                            2             3




  2           2          3        3             4         4         4      
 / \         / \        / \      / \           /         /         /      
1   3       1   4      2   4    1   4         3         2         3      
     \         /      /          \           /         / \       /         
      4       3      1            2         2         1   3     1          
                                           /                     \          
                                          1                       2        



  4         4
 /         /
1         1 
 \         \
  2         3 
   \        /
    3      2

Их порядок следования будет таким же, так как мы можем их различать? Особенно, когда существует более одной последовательности добавления узлов, и все они генерируют одну и ту же структуру, например 2,1,4,5, 2,4,1,3, 2,4,3,1.

Answer 1

Вы упомянули, что все ваши примеры имеют одинаковый обход по порядку (1234), что означает, что inorder недостаточно для получения древовидной структуры.Однако для выведения древовидной структуры двоичного дерева поиска достаточно последовательностей пост-заказа и предварительного заказа . Например, с учетом предварительного заказа 2-1-3-4, единственным двоичным деревом поиска, которое удовлетворяет этому предварительному порядку, является ваш пример строки 2 столбца 1Сравните это с предварительным заказом 2-1-4-3, который будет вашим примером со строкой 2 col 2.

Для всех ваших примеров, вот их записи предварительного заказа

[1234] [1243] [1324] [1432] [1423]

[2134] [2143] [3214] [3124] [4321] [4213] [4312]

[4123] [4132]

Как видите, все они различны.Вы можете повторить тот же процесс для их обхода после заказа, и вы должны получить все отличные результаты.