Сколько последовательностей BST с порядком уровней возможно при заданной последовательности preOrder и inOrder?

Когда я пытаюсь распечатать уровень Order of BST, у меня возникает этот вопрос.

Вот

Pre-Order Sequence: 4, 1, 2, 3, 5, 6, 7, 8
In_order Sequence : 1, 2, 3, 4, 5, 6, 7, 8

Последовательность порядка уровней для BST с указанными выше pre_order и In_order равна [4, 2, 6, 1, 3, 5, 7, 8].

Тем не менее, для той же последовательности «Предварительный заказ» и «По порядку» такая последовательность уровней порядка кажется возможной. [4, 1, 5, 2, 6, 3, 7, 8]. Я не знаю как. Я пытаюсь понять это.

Я не могу построить BST на бумаге (чертеже), которая удовлетворяет всем последовательностям pre_order, In-order и level order.


algorithm binary-tree binary-search-tree inorder preorder
person brain storm    schedule 24.06.2015    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Если у вас есть обход по порядку вместе с обходом до/по порядку, этого достаточно для восстановления бинарного дерева. Более того, в случае BST (бинарного дерева поиска) достаточно только пост- или предварительного заказа.

В вашем случае восстановление BST из предварительного заказа 4, 1, 2, 3, 5, 6, 7, 8 дает следующее BST:

     4
   /   \
  1     5
   \     \
    2     6
     \     \
      3     7
             \
              8

что дает, опять же, уникальный обход по уровням [4,1,5,2,6,3,7,8].

Смотрите также:

person Miljen Mikic    schedule 24.06.2015
comment
я сомневаюсь, что для приведенных выше preOrder и Inorder возможны последовательности двухуровневого порядка? - person brain storm; 24.06.2015
comment
ваш порядок первого уровня неверен. Значит, если вы построите дерево из заданного предварительного порядка, и для того, чтобы вы получили уникальное дерево и порядок уровней для этого дерева, будет [4, 1, 5, 2, 6, 3, 7, 8], а не [ 4, 2, 6, 1, 3, 5, 7, 8] - person nikhil jain; 24.06.2015

arrow_upward
1
arrow_downward

Следующая комбинация создаст уникальное двоичное дерево (которое может быть BST).

Inorder and Preorder.
Inorder and Postorder.
Inorder and Level-order.

Таким образом, в вашем случае задан порядок и предварительный порядок, который будет генерировать уникальное двоичное дерево, которое в вашем случае является BST, поэтому порядок уровней будет уникальным для этого дерева.

Pre-Order Sequence: 4, 1, 2, 3, 5, 6, 7, 8
In_order Sequence : 1, 2, 3, 4, 5, 6, 7, 8

Дерево SO будет

level 0- 4
level 1- 1,5
level 2- 2,6
level 3- 3,7
level 4- 8

Порядок уровней

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

в сортировке всегда будет уникальный обход порядка уровней

person nikhil jain    schedule 24.06.2015
comment
посмотри на это. У меня есть связанный с этим вопрос. stackoverflow.com/questions/31020267/ - person brain storm; 24.06.2015