Приклад

Для цього бінарного дерева,

· Прямий порядок: 2, 7, 2, 6, 5, 11, 5, 9, 4.

· Зворотній порядок: 2, 5, 11, 6, 7, 4, 9, 5, 2.

· Центрований (центральний) порядок: 2, 7, 5, 6, 11, 2, 5, 4, 9.

Порядок та властивості обходу вузлів дерева.

Є три операції обходу вузлів дерева, що відрізняються порядком обходу вузлів.

Перша операція – INFIX_TRAVERSE – дозволяє обійти всі вузли дерева в порядку зростання ключів і застосувати до кожного вузла задану користувачем функцію call_back_function. Ця функція працює тільки з парою (K,V), яка зберігається у вузлі. Операція INFIX_TRAVERSE реалізується рекурсивно: спочатку вона запускає себе для лівого піддерева, потім запускає дану функцію для корення , далі запускає себе для правого піддерева.

Infix_traverse ( call_back_function ) - обійти все дерево, слідуючи порядку (ліве піддерево, корінь, праве піддерево).

Prefix_traverse ( call_back_function ) - обійти все дерево, слідуючи порядку (корінь, ліве піддерево, праве піддерево).

Postfix_traverse ( call_back_function ) - обійти все дерево, слідуючи порядку (ліве піддерево, праве піддерево, корінь).

Infix_traverse:

Дано: дерево Т і функція f

Задача: застосувати f до всіх вузлів дерева Т в порядку зростання ключів

Алгоритм:

· Якщо дерево порожнє, зупинитися.

· Інакше

· Рекурсивно обійти праве піддерево Т.

· Застосувати функцію f до кореневого вузла.

· Рекурсивно обійти ліве піддерево Т.

У простому випадку, функція f може виводити значення пари (K,v). При використанні операції Infix_traverse будуть виведені всі пари в порядку зростання ключів. Якщо ж використовувати Prefix_traverse, то пари будуть виведені в порядку, відповідним опису дерева.

Розділ 5. Комбінаторні обчислювання на скінчених множинах.

5.1 Предмет теорії комбінаторних алгоритмів (обчислювань)

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

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

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

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

Теорію конфігурацій, що включає блок - схеми, групи підстановок, теорію кодування.

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

Теорію порядку, що включає кінцеву впорядковану безліч і грати, матроїди і теореми існування, подібне до теорем Холла і Рамсея.

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

<== попередня сторінка	\|	наступна сторінка ==>
Порядок та властивості обходу дерева.	\|	Правила множення і суми для знаходження

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.