243
правки
Изменения
→Восстановление дерева по результату обхода preorderTraversal
Разберём алгоритм на примере последовательности <tex>\mathtt{8}</tex> <tex>\mathtt{2}</tex> <tex>\mathtt{1}</tex> <tex>\mathtt{4}</tex> <tex>\mathtt{3}</tex> <tex>\mathtt{5}</tex>.
Будем выделять красным цветом вершины, рассматриваемые на каждом шаге, чёрным жирным {{---}} их родителей.
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Состояние
|style="background-color:#FFF;padding:2px 10px"| ''Первая вершина всегда будет корнем, так как вывод начинался с него.''
|-
|style="background-color:#FFF;padding:2px 10px"| '''8''' <span style="color:red">'''8 2 1'''</span> 1 4 3 5|rowspan=2|style="background-color:#FFF;padding:2px 10px"| Находим убывающую подпоследовательность. Каждую вершину подвешиваем к последней из взятых ранее в качестве левого сына.|rowspan=2|style="background-color:#FFF;padding:2px 10px"| ''Каждая последующая вершина становится левым сыном предыдущей, так как выводя ключи, мы двигались по дереву поиска влево, пока есть вершины.''|style="background-color:#FFF;padding:2px 10px"| 8 '''2''' <span style="color:red">'''1'''</span> 4 3 5
|-
|style="background-color:#FFF;padding:2px 10px"| 8 2 1 <span style="color:red">'''4'''</span> 3 5
