Теоретичні відомості

Лабораторна робота № 1

Тема:Способи обходу дерева.

Мета:Скласти програму обходу дерева із використанням спеціалізованих структур даних.

Теоретичні відомості

Дерево — це сукупність елементів, які називаються вузлами (один з них визначений як корінь), та відношень (“батьківських”), що утворюють ієрархічну структуру вузлів.

Отже, кожен елемент дерева називається вершиною або вузлом. Найвища точка буде кореневою вершиною. Вершини на протилежній стороні дерева називаються кінцевими (або листками). Вибравши деяку вершину дерева, можна зауважити, що ця вершина разом із розташованими внизу вершинами, також утворює деяку деревовидну структуру. Цю меншу структуру прийнято називати піддеревом. При обговоренні деревовидної структури кажуть, що кожна вершина породжує ті вершини, які знаходяться безпосередньо нижче від неї. В цьому сенсі можуть вживатися посилання на предків (попередників) та потомків (наступників) даної вершини. Безпосередніх наступників деякої вершини називають її дочірніми вершинами, а її безпосереднього попередника — батьківською вершиною. Крім того, вершини, що, мають спільну батьківську вершину, називають близнятами.

Вузли так само, як і елементи списків, можуть бути елементами будь-якого типу. Ми часто зображуватимемо вузли буквами, рядками або числами.

Формально дерево можна рекурентно визначити таким чином:

1. Один вузол є деревом. Він також є коренем цього дерева.

2. Нехай n ― це вузол, а Т_1,Т_2,..., Т_k ― дерева з коренями n₁, n₂, … , n_kвідповідно. Можна побудувати нове дерево, зробивши n батьком вузлів n₁, n₂, … , n_k.В цьому дереві n буде коренем, а Т_1,Т_2,..., Т_k ― піддеревами цього кореня. Вузли n₁, n₂, … , n_k називаються синами вузла n.

Часто у визначення включають поняття нульового дерева, тобто “дерева” без вузлів. Таке дерево ми будемо позначати символом Л.

Шляхом з вузла n₁ у вузол n_k називається послідовність вузлів n₁, n₂, … , n_k, де для всіх і, 1<= i <= k, вузол n_i є батьком вузла n_i+1.

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

Якщо існує шлях з вузла а в b, то в цьому випадку вузол b — наступник вузла а. Зауважимо, що будь-який вузол одночасно є і попередником, і наступником самого себе. Попередник або наступник вузла, що не є таким для самого себе, називається істиним попередником або істинним наступником відповідно; в дереві тільки корінь не має істинного попередника. Вузол, що не має істинних наступників, називається листком.

Неперервний список є типовим для системи зберігання, коли список зберігається у вигляді масиву. Наприклад, якщо припустити, що кожне ім’я складається не більш, ніж з восьми символів, то в даному випадку програміст зможе організувати список з 10 імен у вигляді масиву символів із 10 рядків і 8 стовпчиків. В результаті утворюється структура (див. мал.1) (припускається, що масив записується в пам’яті з розгорткою по рядкам).

Неперервний блок комірок пам’яті

Мал.1. Список імен, що зберігається у вигляді неперервного списку.

Неперервний список дуже зручний у використанні, але має деякі суттєві недоліки. Припустимо, що необхідно знищити одне з імен в списку. Якщо це ім’я на даний час розташоване ближче до початку списку і потрібно зберегти в списку той самий (припустимо, алфавітний) порядок, то потрібно буде перемістити всі імена, що йдуть далі по списку, вперед, щоб заповнити порожнє місце в пам’яті, яке утвориться після знищення. Серйозніша проблема виникне, коли потрібно буде добавити імена, оскільки для цього треба перемістити весь список в інше місце, щоб отримати новий блок неперервної пам’яті, необхідний для розміщення розширеного списку. Для уникнення вказаних вище проблем дозволяють зберігати окремі імена з одного списку в місцях пам’яті. Для цього потрібно зберігати кожне ім’я в блоці з дев’яти неперервних комірок пам’яті. Перші вісім призначені для зберігання самого імені, а дев’ята використовується як покажчик на наступний елемент списку. При такому способі зберігання елементи списку можуть бути розкидані як множини маленьких блоків пам’яті з дев’яти комірок, що об’єднуються в єдиний список покажчиками. У відповідності з даним методом об’єднання така структура називається зв'язаним списком.

Обхід дерева рекурсивно можна визначити наступним чином:

Якщо дерево Т ― нульове дерево, то в список обходу заноситься порожній запис.
Якщо дерево Т складається з одного вузла , то в список обходу записується цей вузол.
Нехай Т ― це дерево з коренем n і піддеревами Т_1,Т_2,..., Т_k, як показано на мал.2.

Тоді при проходженні в прямому порядку (тобто при прямому упорядкуванні) вузлів дерева Т спочатку відвідують корінь n, потім вузли піддерева Т₁, потім вузли піддерева Т₂ і т.д. Останніми відвідуються вузли піддерева Т_k.

При проходженні дерева в оберненому порядку спочатку відвідують в оберненому порядку всі вузли піддерева Т₁, потім послідовно відвідуються всі вузли піддерев Т₂, ..., Т_к також в оберненому порядку, останнім відвідується корінь n.

При симетричному обході спочатку відвідують в симетричному порядку всі вузли піддерева Т₁, потім корінь n, потім послідовно в симетричному порядку відвідують всі вузли піддерев Т₂, ...,Т_k .

Мал. 2.

⇐ Предыдущая 123 4 5 6 7 8 9 10 Следующая ⇒