прошивка дерев

Цей тип покажчиків слід відрізняти від покажчиків, використовуваних в структурі дерева. Для лівого і правого піддерева операція замінює порожні покажчики на нитки - прошивка.

Прошивка може виконуватися по-різному

Симетрично прошита дерево - дерево прошита зліва і справа.

В прямо прошитих зліва і справа порожні покажчики.

Переваги прошитого дерева:

--можливість визначення попередника і приймача вершини.

--включення нової вершини складніше, т.к необхідно підтримувати і структуру зв'язку та зв'язку з нитки.

Для БД з симетричною прошивкою вставка нової вершини зліва від заданої р- ліве піддерево заданої вершини х якщо х має своїх нащадків, тобто нова вершина вставляється між х і лівим сином х.

Для зручності створення і обходу БД використовується додатковий головний вершина head, яка служить при змішаному обході попередників його 1-ої вершини і приймачів всіх його кінцевих вершин. Такого роду елементи є реальною необхідністю.

Схожі статті