Mavzu: 14 “Dag‘al kuch” usuli bilan tartiblashtirish

Замена извлекаемого элемента на специальный символ
В результате построения такого дерева наименьший элемент попадает сразу в корень. Далее начинается извлечение элементов из дерева. Извлекается значение из корня. Данное значение является первым элементом в результирующем массиве. Извлеченное значение помещается в отсортированный массив и заменяется в дереве на специальный символ.
После этого происходит повторное занесение значений в родительские элементы от листьев к корню. При сравнениях специальный символ считается большим по отношению к любому другому значению.
После повторного заполнения из корня извлекается очередной элемент и итерация повторяется. Извлечения элементов продолжаются до тех пор, пока в дереве не останутся одни специальные символы.
Повторное заполнение дерева сортировки
Извлечения элементов из дерева сортировки
В результате получим отсортированный массив
0, 1, 3, 4, 5, 8, 10, 20
Представление симметрично прошитого бинарного дерева в виде массивов
Такие структуры данных получили название прошитых бинарных деревьев. Указатели или адреса, определяющие порядок обхода, называют нитями. При этом в соответствии с порядком прохождения вершин различают право прошитые, лево прошитые и симметрично прошитые бинарные деревья.
Прошитое дерево со специальными прошивающими ссылками, показанными пунктирными стрелками
Прошитое двоичное дерево — это вариант двоичного дерева, который позволяет производить быстрый обход — если дан указатель на узел в прошитом дереве, можно легко найти следующий по порядку узел (и/или предыдущий).

Прошитые деревья

Прошитые деревья

Определение

Прошитое дерево определяется следующим образом:

«Двоичное дерево прошивается путём присвоения всем указателям правого потомка, которые обычно были бы нулевыми указателями, указателей на следующий по порядку узел данного узла (если такой существует), а всем указателям левого потомка, которые обычно были бы нулевыми указателями, указателей на предыдущие узлы в упорядочении»