Реферати українською » Математика » Подання бінарного дерева у вигляді масиву


Реферат Подання бінарного дерева у вигляді масиву

>ФЕДЕРАЛЬНОЕ АГЕНТСТВОМОРСКОГО ІРЕЧНОГО ТРАНСПОРТУ

Федеральне державне освітнє установа вищого професійної освіти

«Санкт-Петербурзький державний університет водних комунікацій»

>КУРСОВАЯ РОБОТА ПОДИСЦИПЛИНЕ

>ДИСКРЕТНАЯМАТЕМАТИКА

 

ТЕМА:

«ВИСТАВУДЕРЕВЬЕВ УВИДЕМАССИВА»

>Виполнил студент 2 курсу

групиИП-21:

Мальцев Валерій

Перевірив:

>Нирков Анатолію Павловичу

Санкт-Петербург

2009 р.

Зміст

Дерева. 3

Термінологія дерев. 4

>Бинарние дерева. 5

Уявлення бінарних дерев. 9

Додаток. 12

Текст програми.. 13

Список літератури.. 15


Дерева

Масиви й пов'язані списки визначають колекції об'єктів, доступом до яких здійснюються послідовно. Такі структури даних називають лінійними (>linear) списками, оскільки вони теж мають унікальні першій і останній елементи і в кожного внутрішнього елемента є лише одне спадкоємець. Лінійний список є абстракцією, що дозволяє маніпулювати даними, уявними по-різному — масивами,стеками, чергами і пов'язаними списками.

Багато додатках можна знайти нелінійний порядок об'єктів, де елементи може мати кількох спадкоємців. Наприклад, в фамільному дереві батько може мати кількох нащадків (дітей). НаРис. 1 показані три покоління сім'ї. Таке впорядкування називають ієрархічним.

Мал.1.

У статті ми розглянемо нелінійну структуру, звану деревом (>tree), що складається з вузлів та виконавчої гілок і має напрям від кореня до зовнішніх вузлам, званим листям. Ці структури подібні комунікаційної мережі, показаної наРис. 2, потребує особливих алгоритмів і застосовують у спеціальних додатках.


>Рис. 2

 

Термінологія дерев

>Древовидная структура характеризується безліччю вузлів (>nodes), що відбуваються єдиного початкового вузла, званого коренем (>root). НаРис. 3 коренем є вузол А. У термінах генеалогічного дерева вузол вважатимуться батьком (>parent), що вказував на 0, 1 чи більше вузлів, званих синами (>children). Наприклад, вузол У є батьком синів E і F. Батько вузла H - вузол D. Дерево може становити кілька поколінь сім'ї. Сини вузла і його сини їх синів називаються нащадками (>descendants), як батьки і прабатьки – предками (>ancestors) цього вузла. Наприклад, вузли E, F, I,J – нащадки вузла B. Коженнекорневой вузол має сенс тільки одного батька, й у батько має 0 чи більше синів. Вузол, яка має дітей (E, G, H, I,J), називається листом (>leaf).

Кожен вузол дерева є коренемподдерева (>subtree), що визначається даним вузлом та всіма нащадками цього вузла. Вузол F є коріньподдерева, що містить вузли F, I іJ. Вузол G є коренемподдерева без нащадків. Цю ухвалу дозволяє говорити, що вузол A є коріньподдерева, що саме виявляється деревом.


>Рис.3.

Перехід від батьківського вузла до дочірньому і решти нащадкам здійснюється вздовж шляху (>path). Наприклад, наРис. 4 шлях від кореня A до вузлу F проходить від A до B і південь від B до F. Факт, коженнекорневой вузол має єдиного з батьків, гарантує, що є єдиний шлях із будь-якої вузла для її нащадкам. Довжина шляху від кореня до цього вузлу є рівень вузла. Рівень кореня дорівнює 0. Кожен син кореня є вузлом 1-го рівня, наступне покоління – вузлами 2-го рівня життя та т.д. Наприклад, наРис. 4 вузол F є вузлом 2-го рівня із довжиною шляху 2.

Глибина (>depth) дерева є її максимальний рівень. Поняття глибини також може бути описано в термінах шляху. Глибина дерева є довжина найдовшого шляху від кореня до вузла.

НаРис.4 глибина дерева дорівнює 3.

>Рис.4. Рівень вузла й довжину шляху

>Бинарние дерева

Хоча дерева загального виду досить важливі, ми зосередимося обмеженій класі дерев, де кожен батько має більше двох синів (>Рис. 5). Такі бінарні дерева (>binarytrees) мають уніфіковану структуру, допускає різноманітні алгоритми перебігу й ефективний доступом до елементам. Вивчення бінарних дерев дає можливість вирішувати найбільш спільні завдання, пов'язані з деревами, оскільки будь-яке дерево загального виду можна еквівалентним йому бінарним деревом.

Кожен вузла бінарного дерева то, можливо 0, 1 чи 2 сина. Стосовно вузлу зліва будемо вживати термін лівий син (>leftchild), а, по відношення до вузлу справа – правий син (>rightchild). Найменування "лівий" і "правий" ставляться до графічної уявленню дерева.Бинарное дерево є рекурсивної структурою. Кожен вузол – це корінь свою власнуподдерева. Він має сини, які самі є корінням дерев, званих лівим і правихподдеревьями відповідно. Отже, процедури обробки дереврекурсивни. Ось рекурсивне визначення бінарного дерева:

>Бинарное дерево - це б таку силу-силенну вузлів B, що

а) B є деревом, якщо безліч вузлів порожньо (порожній дерево – теж дерево);

б) B розбивається втричі непересічних підмножини:

· {R} кореневої вузол

· {>L1,L2, ...,Lm} лівеподдерево R

· {>R1,R2, ...,Rm} правеподдерево R

На рівні n бінарну дерево може містити від 1 до 2N вузлів. Кількість вузлів,приходящееся до рівня, є показник щільності дерева. Інтуїтивно щільність є міра величини дерева (число вузлів) стосовно глибині дерева. НаРис. 5 дерево А містить 8 вузлів при глибині 3, тоді як дерево B містить 5 вузлів при глибині 4. Останній випадок є особливої формою, званоївирожденним (>degenerate) деревом, що має єдиний лист (E) й унелистовой вузол має сенс тільки одного сина.Вирожденное дерево еквівалентно пов'язаного списку.


>Рис.5.Бинарние дерева

Дерева з великою щільністю дуже важливі як структур даних, оскільки вони містять пропорційно більше елементів поблизу кореня, тобто. з коротшими шляхами від кореня.Плотное дерево дозволяє зберігати великі колекції даних, і здійснювати ефективний доступом до елементам. Швидкий пошук – головне, що зумовлює використання дерев для зберігання даних.

>Вирожденние дерева є крайньої мірою щільності. Інша крайність – закінчені бінарні дерева (>completebinarytree) глибини N, де кожен рівень0...N - 1 має повний набір вузлів, і всі листя рівня N розташовані зліва. Закінчене бінарну дерево, що містить2N вузлів лише на рівні N, є повним. НаРис. 6 показані яке закінчила і повний бінарні дерева.

>Рис.6. Класифікація бінарних дерев

>Бинарние дерева класифікуються з кількох ознаками.Введем поняття ступеня вузла і рівня дерева. Ступенем вузла в дереві називається кількість дуг, яка з нього виходить. Ступінь дерева дорівнює у максимальному ступені вузла, входить у дерево. З визначення рівня зрозуміло, що ступінь вузла бінарного дерева вбирається у числа два. У цьому листками на дереві є вершини, мають ступінь нуль.

>Рис.7.Бинарное дерево

Іншою важливою ознакою структурної класифікації бінарних дерев є строгість бінарного дерева. Суворо бінарну дерево полягає з вузлів, мають ступінь чи ступінь нуль.Нестрого бінарну дерево містить вузли зі ступенем рівної одному.

>Рис.8. Повне і неповне бінарні дерева


>Рис.9. Суворо і суворо бінарні дерева

Уявлення бінарних дерев

>Бинарние дерева не так важко можуть бути як списків чи масивів.Списочное уявлення бінарних дерев грунтується на елементах, відповідних вузлам дерева. Кожен елемент має полі даних, і два поля покажчиків. Один покажчик використовується для зв'язування елемента з правим нащадком, а з лівим. Листя мають порожні покажчики нащадків. За такої способі уявлення дерева обов'язково випливає зберігати покажчик на вузол, є коренем дерева.

Можна зауважити, що такий спосіб уявлення має схожість із простими лінійними списками. І ця подібність невипадково. Насправді розглянутий спосіб подачі бінарного дерева є різновидоммультисписка, освіченого комбінацією безлічі лінійних списків. Кожен лінійний список об'єднує вузли, що входять до шлях від деревокореня до жодного з листя.


>Рис.10. Уявлення бінарного дерева яксписковой структури

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

>Рис.11. Уявлення бінарного дерева як масиву

Якщо рівнів дерева у процесі опрацювання нічого очікувати істотно змінюватися, такий спосіб подачі повного бінарного дерева буде набагато економічнішими, ніж будь-якасписковая структура.

Проте зовсім в усіх бінарні дерева є повними. Для неповних бінарних дерев застосовують наступний спосіб подачі.Бинарное дерево доповнюється до дерева, вершини послідовно нумеруються. У масив заносяться ті вершини, що у вихідному неповному дереві. За такої поданні елемент масиву виділяється незалежно від цього, чи він буде утримувати вузол вихідного дерева. Отже, слід зазначити невикористовувані елементи масиву. Це можна зробити занесенням спеціального значення відповідні елементи масиву. Через війну структура дерева перенесено у одновимірний масив. Адреса будь-який вершини в масиві обчислюється як

адресу =2к-1+i-1,

деk-номер рівня вершини, і- номер лише на рівніk у його бінарному дереві. Адреса кореня дорівнюватиме одиниці. Для будь-який вершини можна визначити адреси лівого і правого нащадків

>адрес_L =2к+2(i-1)

>адрес_R =2к+2(i-1)+1

Головним недоліком розглянутої способу уявлення бінарного дерева і те, що структура даних є статичної. Розмір масиву вибирається з якомога більшої кількості рівнів бінарного дерева. Причому що менш повним є дерево, проте раціонально використовується пам'ять.


Додаток

Як приклад використання бінарного дерева як масиву використали масив – a[ і ], що з 15 елементів (від 1 до 15). Через війну дерево повинен мати вид:


Текст програми

дерево нелінійне масив бінарну

#>include <>fstream.h>

#>include <>stdio.h>

#>include <>conio.h>

#>include <>windows.h>

>charbufRus[256];

>char*Rus(constchar*text){

        CharToOem(text,bufRus);

        returnbufRus;

}

>intmain()

{inti,k;

        inta[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

 

        cout <<Rus("Дерево:") <<endl;

        cout <<Rus("Корень дерева -a[0] = ") <<a[0] <<endl;

        k=0;

        for (>i=1;i<=14; і++)

         {       

                  if (>i%2==0)k=k+1;

                  if (>i%2!=0)cout <<Rus(" лівий син вузла a[") <<i-k-1 << "]=" <<a[i] <<endl;

                  if (>i%2==0)cout <<Rus(" правий син вузла a[") <<i-k-1 << "]=" <<a[i] <<endl; 

         }

        return 0;


Результат виконання програми:


Список літератури

1) Ахо А.,Хопкрофт Д., Ульман Д. Структури даних, і алгоритми.

2) Д.РайлиАбстракция і структури даних.Вводний курс.

3) Д. Батіг Мистецтво програмування для ЕОМ.Т1, Основні алгоритми.


Схожі реферати:

Навігація