Дерева, види, способи подання, структури даних, обходи дерева
Дерево - це структура даних, що представляє собою сукупність елементів і відносин, що утворюють ієрархічну структуру цих елементів.
Кожен елемент дерева називається вершиною (вузлом) дерева.
Вершини дерева з'єднані спрямованими дугами, які називають гілками дерева.
Початковий вузол дерева називають коренем дерева, йому відповідає нульовий рівень.
Листям дерева називають вершини, в які входить одна гілка і не виходить жодної гілки.
Кожне дерево має такі властивості:
• існує вузол, в який не входить ні однієї дуги (корінь);
• в кожну вершину, крім кореня, входить одна дуга.
Дерева особливо часто використовують на практиці при зображенні різних ієрархій.
Нащадки - це все вершини, в які входять гілки, що виходять з однієї загальної вершини.
Предок - це вершина, з якої виходять гілки до вершин наступного рівня.
Рівень нащадка на одиницю перевищує рівень його предка.
Корінь дерева не має предка, а листя дерева не мають нащадків.
Висота (глибина) дерева визначається кількістю рівнів, на яких розташовуються його вершини. Висота порожнього дерева рана нулю, висота дерева з одного кореня - одиниці. На першому рівні дерева може бути тільки одна вершина - корінь дерева, на другому - нащадки кореня дерева, на третьому - нащадки нащадків кореня дерева і т.д.
Піддерево - частина древообразная структури даних, яка може бути представлена у вигляді окремого дерева.
Ступенем вершини в дереві називається кількість дуг, яке з неї виходить.
Ступінь дерева дорівнює максимальному ступені вершини, що входить в дерево. При цьому листям в дереві є вершини, що мають ступінь нуль.
Впорядковане дерево - це дерево, у якого гілки, що виходять з кожної вершини, впорядковані за певним критерієм.
Дерева є рекурсивними структурами, так як кожне піддерево також є деревом. Таким чином, дерево можна визначити як рекурсивну структуру, в якій кожен елемент є:
• або порожній структурою;
• або елементом, з яким пов'язано кінцеве число піддерев.
Дії з рекурсивними структурами найзручніше описуються за допомогою рекурсивних алгоритмів.
Обхід дерева - це впорядкована послідовність вершин дерева, в якій кожна вершина зустрічається тільки один раз.
При обході все вершини дерева повинен відвідувати у певному порядку. Існує кілька способів обходу всіх вершин дерева.
• прямий порядок - спочатку відвідується корінь n дерева Т, потім все вузли поддерева Т1, далі все вузли поддерева Т2, і т.д. тк;
• симетричний - спочатку відвідується все вузли поддерева Т1, далі корінь n, далі все вузли поддерева Т2, і т.д. тк;
• зворотний - спочатку відвідується все вузли поддерева Т1, далі все вузли поддерева Т2, і т.д. Тк, останнім відвідується корінь n.
Подання дерев за допомогою масивів
Двійкові дерева пошуку, операції додавання елементів.
Двійкові дерева пошуку (binary search tree. BST)
У двійковому дереві пошуку кожна вершина може мати (або не мати) лівого і правого дитини, кожна вершина, крім кореня має батька. При поданні з використанням покажчиків ми зберігаємо для кожної вершини дерева, крім значення ключа key також покажчики left, right і р (піддерева ліве, праве і батько). Якщо дитину (або батька - для кореня) немає, відповідне поле містить NULL.
Ключі в довічним дереві пошуку зберігаються з дотриманням властивості впорядкованості.
Нехай х довільна вершина двійкового дерева пошуку. Якщо вершина у знаходиться в лівому поддереве вершини х, то key [y]
Node (T w): inf (w), left (0), right (0) <>
Node * _Add (Node * r, T s)
else if (s
r-> left = _Add (r-> left, s);
r-> right = _Add (r-> right, s);