Головна

Алгоритм проходження дерева вглиб

  1. IV. Розробити алгоритм розв'язку та програму до задач з даної теми. Задачі вибираються за варіантом в додатку.
  2. Адаптивные квадратурные алгоритмы
  3. Алгоритм
  4. Алгоритм
  5. Алгоритм
  6. Алгоритм
  7. Алгоритм

Лекція 11. Нелінійні структури даних. Дерева

План

1. Поняття дерева. Бінарні дерева.

2. Подання дерев у зв'язній пам'яті комп'ютера.

3. Алгоритми проходження дерев вглиб і вшир.

4. Застосування бінарних дерев у алгоритмах пошуку.

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

- є один спеціально позначений вузол, який називається коренем дерева;

- інші вузли (крім кореня) містяться в m>=0 попарно не пересічних множинах T1, T2, ..., Tm, кожна з яких, у свою чергу, є деревом.

Дерева T1, T2, ..., Tm називаються піддеревами такого кореня.

Дерева зображаються такими способами:

- графічно,

- за допомогою множин,

- як модифікація багатозв'язних списків.

Продемонструємо зображення структури дерева:

Графічний спосіб

А: T1={B, D, E, F}, T2={C, H};

B: T11={D}, T12={E}, T13={F};

C: T21={H}.

За допомогою множин

Якщо підмножини T1, T2, ..., Tm упорядковані, то дерево називають упорядкованим. Якщо два дерева вважаються рівними й тоді, коли вони відрізняються порядком, то такі дерева називаються орієнтованими деревами. Кінцева множина непересічних дерев називається лісом.

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

Кількість підмножин для заданого вузла називається ступенем вузла. Якщо така кількість дорівнює нулю, то вузол є листом. Максимальний ступінь вузла в дереві - ступінь дерева. Рівень вузла - довжина шляху від кореня до розглянутого вузла. Максимальний рівень дерева - висота дерева.

Структуру дерева можна зображати й за допомогою інших способів.

Вкладені множини

(А (В (Е) (Р) (О)) <С (Н)))

Дужкова форма

2. Розрізняють три основні способи подання дерев у зв'язній пам'яті: стандартний, інверсний, змішаний. Розглянемо ці способи для дерева

При стандартному способі вузли, що перебувають на одному рівні є братами. Якщо ж вузол перебуває на нижчому рівні, то він вважається сином.

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

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

Функція побудови дерева стандартним способом:

struct tree // структура дерева

{

int el;

struct btree *l, *r;

}; // вказівники на лівого та правого сина

//вказівники на корінь дерева та поточний елемент

struct btree *root, *cur

//функція додавання елемента у дерево

struct btree *insert (struct btree *c, int k, struct btree *new1)

{

struct btree *p, *l; int a;

if (!c) //поточний елемент є порожнім (відсутнім)

{

c=(struct btree*) malloc (size of(struct btree));

c->el = k;

c->l = NULL;

c->r = NULL;

//якщо задано значення а, то дерево вже містить вузли

// і ми здійснюємо прив'язку створенного елемента

//як лівого (а=1) або правого (а=2) сина

if (a==1) new->l=c;

if (a==2) new->r=c;

return (c);

}

else

//спускаємося далі по дереву

{

new1=с;

if (c->el>k)

//переходимо до лівого сина

{

с=с->l; а=1;

р=insert(c,k,new1);

}

else

//переходимо до правого сина

{

с=с->г; а=2;

p=insert(c,k,new1);

}

}

}

void main ()

//виклик функції побудови дерева

{

int k, n=5, l;

scanf("%d", &k);

root = insert(NULL, k, cur);

for (i=2; i<=n; i++)

{

scanf ("%d", &k);

cur = insert (root, k, cur);

}

}

3. Алгоритми проходження дерев углиб і вшир

При проходженні вглиб зображеного дерева, список його вершин, записаних у порядку їхнього відвідування, буде виглядати так

А, В, С, F, G, Н, D, Е, І, J, К.

Алгоритм проходження дерева вглиб

<порожній стек S>;

<пройти корінь і включити його в стек S>;

while <стек S не порожній> dо

begin

{нехай Р - вузол, що перебуває у вершині стека S}

if <не всі сини вузла Р пройдені>

then <пройти старшого сина й включити його в стек S>

else begin

<виключити з вершини стека вузол Р>;

if <не всі брати вершини Р пройдені>

then <пройти старшого брата й включити його в стек S>

end;

end;

При проходженні зображеного дерева вшир (по рівнях), список його вершин, записаних у порядку їхнього відвідування, буде таким:

А, В, С, D, Е F, G, H, I, J K

Наведемо алгоритм проходження дерева вширину:

<взяти дві черги О1 І О2>;

<помістити корінь у чергу О1>;

while <О1 або О2 не порожня> do

begin

if <О1 не порожня> then

{Р - вузол, що перебуває в голові черги 01}

begin

<виключити вузол із черги О1 і пройти його>;

<помістити всі вузли, що відносяться до братів цього вузла Р, у чергу 02>;

end;

else <О1=O2; О2=¤

end;

Між деревами загального вигляду (де вузол дерева може мати більше двох синів) і бінарними деревами існує взаємно однозначна відповідність, тому бінарні дерева часто використають для подання дерев загального виду. Так, наприклад, вищенаведений граф матиме вигляд:

Для такого подання використають наступний алгоритм:

1) зображуємо корінь дерева;

2) по вертикалі зображуємо старшого сина цього кореня;

3) по горизонталі вправо від цього вузла подаємо всіх його братів;

4) пп. 1, 2, 3 повторюємо для всіх його вузлів.

Отже, вертикальні ребра зображають ліві піддерева, а горизонтальні - праві.

Такий алгоритм можна використати й для лісу.

Теорема. Кількість бінарних дерев з n вершинами можна визначити за формулою:

.

При поданні бінарних дерев у зв'язній пам'яті, розрізняють три основних способи подання:

· стандартний,

· інверсний,

· змішаний.

Вузли дерева при кожному такому поданні виглядають так:

Data   Parent   Parent Data
L_Son R_Son   Data   L_Son R_Son
             

стандартний інверсний змішаний

Симетричним проходженням бінарного дерева є таке проходження, копи ми проходимо спочатку ліве піддерево, потім відвідуємо корінь і останнім відвідуємо праве піддерево.

4. Застосування бінарних дерев в алгоритмах пошуку

В однозв'язному списку неможливо використати бінарні методи, вони можуть використовуватися тільки в послідовній пам'яті. Однак, якщо використати бінарні дерева, то в такій зв'язній структурі можна одержати алгоритм пошуку зі складністю О(log2N). Таке дерево реалізується в такий спосіб: для будь-якого вузла дерева із ключем Тi всі ключі в лівому піддереві повинні бути менші від Ti, а в правому - більше Ti. У дереві пошуку можна знайти місце кожного ключа, рухаючись, починаючи від кореня й переходячи на ліве або праве піддерево, залежно від значення його ключа, З n елементів можна організувати бінарне дерево (ідеально збалансоване) з висотою не більшою ніж log2N, що визначає кількість операцій порівняння при пошуку.

Function Search (x:integer; t: EIPtr): EIPtr;

{поле Data замінимо на поле key}

var f:boolean;

begin

f:=false;

while (t < > nill) and not f do

if x=t^.key then f:=true

else

if x>t^.key

then

t:=t^.R_Son

else

t:=t^.L_Son;

Search:=t;

end;

Якщо одержимо, що значення функції = nil, то ключа зі значенням х у дереві не знайдено.

Function Search (x:integer; t: EIPtr): EIPtr;

begin

S^.key:=x;

while t^.key < > x do

if x>t^.key

then

t:=t^.R_Son

else

t:=t^.L_Son;

Search:=t;

end;

Контрольні запитання:

1. Дайте означення дерева?

2. Що називають коренем дерева? піддеревом?

3. Якими способами можна зобразити дерева?

4. Яке дерево називають упорядкованим? орієнтованим?

5. Що називається лісом?

6. Що називається бінарним деревом? лівим (правим) піддеревом?

7. Що називається ступенем вузла, ступенем дерева?

8. Що називається рівнем вузла, висотою дерева?

9. Якими способами можна подати дерево у зв'язній пам'яті? Охарактеризуйте їх.

10. Які вузли називають батьками, братами, синами?

11. Опишіть алгоритми проходження дерев углиб і вшир.

12. Як встановити взаємнооднозначну відповідність між деревами загального вигляду та бінарними деревами?

13. Як визначити кількість бінарних дерев з n вершинами?

14. Що таке симетричне проходження бінарного дерева?

15. Наведіть приклад застосування бінарних дерев в алгоритмах пошуку.



Програми Western NIS Enterprise Fund | Поточний контроль
© um.co.ua - учбові матеріали та реферати