4. Способи зберігання дерев

Для дерев прийняте послідовне і зв'язане зберігання. Послідовне зберігання створюється на основі одного з лінійних зображень дерева – у вигляді "рядка", зокрема воно може бути рівневим або дужковим.

Рівневе задання. З кожним вузлом дерева v зв'язується номер рівня цього дерева k – ціле додатне число. Потім записуються всі його вузли із номерами рівнів відповідно до якогось порядку проходження дерева. Так, рівневим заданням дерева, зображеного на рис. 6, згідно з прямим по­рядком може бути 1,1,2,2,4,3,5,3,7,4,8,4,10,5,3,2,6,3,9,4,11,5,12,5.

Дужкове задання. Дужковим заданням (g₃) дерева В з одного вузла є запис цього вузла. Якщо В складається з кореня W_і піддерев В₁, В₂,..., В_m, тоді дужкове задання записується у вигляді W (g₃(В₁), g₃(B₂),..., g₃(B_m))

Дерево з рис. 6 у дужковому зображенні матиме вигляд:

1(2 (4, 5 (7, 8 (10))), 3 (6 (9 (11, 12)))).

Форми зв'язного зберігання базуються на використанні динамічних змінних. Вони залежать від опису відношень між предками та нащадками (батьками та синами).

Найбільш використовуваними формами зв'язного зберігання є стан­дартна, обернена і розширена стандартна. У стандартній формі фіксуються зв'язки від батька до всіх синів. Отже, якщо дерево має степінь п, тоді в кожному вузлі ми повинні мати п вказівників на синів вузла. Якщо вузол має менше п синів, тоді непотрібні вказівники зв'язку обнуляються за до­помогою вмонтованої функції nil. В оберненій формі зв'язного зберіган­ня дерев вказуються зв'язки від синів до батьків. Розширена стандартна форма об'єднує стандартну та обернену форму зв'язного зберігання дерев. Для дерева з рис. 6 зв'язне зберігання в стандартній формі подане на рис. 7.

Рис.7. Зберігання дерева у стандартній формі

В описаних формах задання дерева один вузол задання відповідає од­ному вузлу дерева, і кількість зв'язків вузла залежить від степеня дерева. Коли дерево неоднорідне і має багато вузлів, степінь яких значно менший від степеня дерева, тоді обробка незадіяних зв'язків спричиняє зайвий клопіт. Тому розглянемо задання вузла з фіксованим розміром.

Вузол матиме три поля — TAG, DATA і LINK. Коли TAG = 1, DATA містить покажчик на список, елементи якого відповідають синам відповід­ного вузла; в іншому разі DATA включає елемент-листок. Поле LINK використовується як поле зв'язку списку піддерев кожного елемента дерева Так, дерево, зображене на рис.8, відображатиметься в даному разі списковою структурою з рис. 9.

Рис. 8. Дерево

Рис.9. Спискова структура задания дерева з рис. 8 у формі вузла фіксованого розміру

Бінарне дерево називається повним, якщо для деякого цілого числа k кожний вузол глибини, меншої за k, має як лівого, так і правого сина і кож­ний вузол глибини k є листом. Повне бінарне дерево висоти k має в точності 2^k-1 вузлів.

У такому разі повне бінарне дерево з п вузлами можна зручно зада­ти послідовною нумерацією вершин, починаючи з кореня, по рівнях зліва

направо за допомогою масиву Tree (і). Тоді для будь-якого вузла з індек-сом і, 1 < і < п справджуватиметься:

1) батько вузла і, Parent(і) визначатиметься [і/2], якщо і = 1. Коли і = 1, тоді цей вузол вже є коренем і тому батька він не має;

2) лівий син вузла і, Lson (і) визначатиметься формулою Lson (і) = 2 х і, коли 2 х і < n. Коли ж 2 х і> п, тоді вузол i не має лівого сина;

3) правий син вузла і, Rson (i) визначатиметься формулою Rson(i) = = 2 х i + 1, коли 2 х і + 1 < n. Коли ж 2 х і + 1 > n, тоді вузол г не має пра­вого сина.