Deprecated: mysql_connect(): The mysql extension is deprecated and will be removed in the future: use mysqli or PDO instead in /home/studb20/public_html/index.php on line 4
 1.19.4 Двійкові дерева - Програмування С, С++теорія та практика (частина 1) - Studbook
ГоловнаЗворотній зв'язок

Категорії

загрузка...

Програмування С, С++теорія та практика (частина 1)

1.19.4 Двійкові дерева

Бінарне дерево - це динамічна структура даних, що складається з вузлів (елементів), кожен з яких містить, окрім даних, не більше двох посилань на інші бінарні дерева. На кожен вузол припадає рівно одне посилання. Початковий вузол називається коренем дерева (рис 1.23.).

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

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

Дерево є рекурсивною структурою даних, так як кожне піддерево є також деревом. Дії з такими структурами даних простіше всього описувати за допомогою рекурсивних алгоритмів.

корінь

ліве

піддерево

праве

піддерево

Рис. 1.32. Схематичне зображення дерева

 

Наприклад, функцію обходу всіх вузлів дерева в загальному вигляді можна описати так :

£ипсЬіоп мау(дерево)

{

мау(ліве піддерево);

обробка кореня;

мау(праве піддерево);

};

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

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

Для бінарних дерев визначені наступні операції :

•     включення вузла у дерево;

•     пошук по дереву;

•     обхід дерева;

•     видалення вузла.

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

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

£урегіе£ з'Ьгис'Ь зЬ'Ьгее {

іп'Ь Vа1;

зїгисї зЬ^гее *1е£^,*гідЬ^;

} Ь£гее;

Реалізація деяких операцій з бінарними деревами.

1)       . Рекурсивний пошук в бінарному дереві. Функція повертає покажчик на знайдений вузол.:

Ь£гее *8еагсЬ(Ь'Ьгее *р, іп'Ь V)

{

і£ (р==!ИиііІі) ге'Ьиг^ОТЬЬ); /* вітка порожня */ і£ (р-^а1 == V) ге'Ьигп(р) ; /*     вершина                         знайдена   */

і£ (р-^а1 > V) /* порівняння з поточним вузлом */ ге'Ьигп(8еагсЬ(р->1е£'Ь^));  /*     ліве піддерево */

е1зе

ге'Ьигп(8еагсЬ(р->гідЬ'Ь^));  /* праве піддерево  */

}

2)    . Включення значення в двійкове дерево (рис 1.33.):

Ь£гее *Іпзег^(Ь^гее *рр, Іп£ V)

{

і£ (рр == ОТЬЬ) /* знайдена порожня вітка */

{

Ь£гее *д = (Ь£гее*) са11ос(1,зігео£(Ь^гее));

/* створити вершину дерева */ д-^а1 = V; /* і повернути покажчик */ д->1е££ = д->гідЬ^ = ОТЬЬ; ге'Ьигп д;

}

і£ (рр->Vа1 == V) ге'Ьигп рр;

і£ (рр-^а1 > V) /* перейти в ліве піддерево */ рр->1е£'Ь=Іпзег'Ь(рр->1е£'Ь,V) ; е1зе

рр->гідЬ^=Іпзег^(рр->гідЬ^,V);

/* перейти в праве піддерево*/

ге'Ьигп рр;

}

3)    . Рекурсивний обхід двійкового дерева : VОій 8сап(Ь£гее *р)

{

}

 

 

 

 

 

 

 

[1]   Порозрядне заперечення ! заміняє змінює кожну 1 на 0, а 0 на 1. Приклад : ~ (10011010) == (01100101).

•      Порозрядна кон’юнкція & (порозрядне І) порівнює послідовно розряд за розрядом два операнди. Для кожного розряду результат рівний 1, якщо тільки два відповідних розряди операндів рівні 1, в інших випадках результат 0.

•      Приклад : (10010011) & (00111101) == (00010001).

•      Порозрядна диз’юнкція |               (порозрядне АБО) порівнює

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

Приклад : (10010011) | (00111101) == (10111111)

 

99