Казанський Державний Технічний Університет
ім. А. Н. Туполєва
В В В В В В В В В
Курсова робота
з програмування
на тему
Структури даних:
бінарне впорядковане незбалансоване дерево
В В
В В В В В
Виконав: Звєрєв І. М.
В
Перевірив: Рахматуллін А. І.
В В В В В В В В В В
Казань
2003
План роботи:
В
1) Постановка завдання
2) Опис програми
3) Код програми на мовах Pascal і С + +
1. Постановка завдання
Потрібно написати програму, що реалізовує основні операції роботи з деревом. Причому, обов'язковим умовою є використання структури даних клас для опису дерева і методів роботи з ним.
2. Опис програми
В
Опис ведеться для коду на Pascalе, відмінності для С + + будуть вказані нижче.
У програмі основним елементом є клас TTree. Його методи - це основні процедури роботи з деревом:
Create - конструктор класу - процедура, що створює дерево,
Add - метод додавання елемента в дерево,
Del - метод видалення елемента з дерева,
View - метод виведення елементів дерева на екран,
Exist - метод перевірки існування елемента з деяким ключем, по суті пошук елемента,
Destroy - деструктор класу - процедура, що видаляє дерево.
Розглянемо алгоритми роботи процедур.
Create - створення дерева. Присвоює полю Root (корінь) значення nil - покажчика, який нікуди не вказує.
Add - додавання елемента в дерево. Для побудови дерева використовуємо наступний алгоритм. Перший елемент поміщаємо в корінь (инициализируем дерево). Далі поступаємо таким чином. Якщо додається в дерево елемент має ключ більший, ніж ключ вузла, то, якщо сайт не лист, обходимо його справа. Якщо додається елемент має ключ не більший ніж ключ вузла, то, якщо сайт не лист, обходимо його ліворуч. Якщо дійшли до листа, то додаємо елемент відповідно праворуч або ліворуч.
Del - видалення елемента з дерева.
Видалення вузла досить просто якщо він є листом або має одного нащадка. Наприклад, якщо потрібно видалити вузол з ключем М треба просто замінити праву посилання вузла К на покажчик на L. Складність полягає у видаленні вузла з двома нащадками, оскільки ми не можемо вказати одним покажчиком на два напрями.
В
Наприклад, якщо просто видалити вузол з ключем N, то лівий покажчик вузла з ключем Т повинен вказувати одночасно на К і R що неможливо. У цьому випадку видаляється вузол потрібно замінити на інший вузол з дерева. Виникає питання, яким же вузлом його замінити? Цей вузол повинен володіти двома властивостями: по-перше, він повинен мати не більше одного нащадка, по-друге, для збереження впорядкованості ключ...
