Изменения

Перейти к: навигация, поиск

Дерево поиска, наивная реализация

95 байт добавлено, 17:41, 15 января 2017
Восстановление дерева по результату обхода preorderTraversal
Как мы помним, процедура <tex>\mathrm{preorderTraversal}</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына.
Разберём алгоритм на примере последовательности <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"
243
правки

Навигация