Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Обхід дерева в глибинуОбхід в глибину проводиться рекурсивно або з використанням стека. В обох випадках можна обходити вузли дерева в різній послідовності. Обхід починається від кореня. Виділяють три найбільш важливих порядку обходу в глибину:
- префіксний (прямий) обхід – спочатку обробляється поточний вузол, потім ліве і праве піддерева; - інфіксний (симетричний) обхід – спочатку обробляється ліве піддерево поточного вузла, потім корінь, потім праве піддерево; - постфіксний (зворотний) обхід – спочатку обробляються ліве і праве піддерева поточного вузла, потім сам вузол. Як приклад розглянемо наступне дерево: префіксний обхід: A, B, D, H, E, C, F, I, J, G інфіксний обхід: D, H, B, E, A, I, F, J, C, G постфіксний обхід: H, D, E, B, I, J, F, G, C, A
Запишемо як приклад рекурсивну процедуру, що виводить на екран вузли дерева в порядку префіксного обходу. void prefix(t *curr) { if (!curr) return; printf("%d ", curr->data); prefix(curr->left); prefix(curr->right); } Операції над бінарними деревами: Додавання Додавання елемента в бінарне дерево – операція, яка має логарифмічну складність по відношенню розміром дерева (logn). Це дуже цікава операція, тому що кожен елемент в бінарному дереві має певну позицію. Тому спочатку треба знайти, куди його поставити, а потім і здійснити це. Код на C / C ++: void insert_tree(tree **t, item_type item, tree *parent) { tree *p; if (*t == NULL) { p = (tree *)malloc(sizeof(tree)); p->left = p->right = NULL; p->parent = parent; p->item = item; *t = p; return; }
if (item < (*t)->item) { insert_tree(&((*t)->left), item, *t); } else { insert_tree(&((*t)->right), item, *t); } } Пошук Операцію пошуку в бінарному дереві виглядає як додавання і займає логарифмічний час (logn). Це відноситься до добре збалансованому дереву, звичайно! Код в C / C ++: tree *search_tree(const tree *t, item_type i) { if (t == NULL) return NULL; if (t->item == i) return t; if (i < t->item) { return search_tree(t->left, i); } else { return search_tree(t->right, i); } } Приклад пошуку мінімального елемента: tree *find_min(const tree *t) { if (t == NULL) return NULL; tree *min = t; while (min->left!= NULL) { min = min->left; } return min; } Видалення Видалення елемента з дерева найважча операція. Проте вона також забирає logn час. Є кілька спеціальних ситуацій, які повинні бути вирішені: 1. Видалення елемента без дітей – просто звільняємо пам'ять. 2. Видалення елемента з однією дитиною – зміна покажчика батька вказувати директно до дитини видаляється елемента і звільнення пам'яті. 3. Видалення елемента з тільки однією дитиною і це КОРІНЬ – переміщення дитини на місце кореня і звільнення пам'яті. 4. Видалення елемента з двома дітьми – це найскладніша операція. Самий відповідний спосіб виконання це розміняти вартості видаляється елемента і максимальну вартість лівого піддерева або мінімальну правого піддерева (бо це збереже характеристики дерева) і тоді видаляємо елемент без або з однією дитиною. void delete_element(tree **t, item_type item) { if (t == NULL) return; tree *element = search_tree(*t, item); if (element == NULL) return; int hasParent = element->parent!= NULL; int isLeft = hasParent && element->item < element->parent->item; if (element->left == NULL && element->right == NULL) {//no children if (hasParent) { if (isLeft) { element->parent->left = NULL; } else { element->parent->right = NULL; } } free(element); } else if (element->left!= NULL && element->right == NULL) {//only left child element->left->parent = element->parent;//even if it does not have a parent it will be cool if (hasParent) { if (isLeft) { element->parent->left = element->left; } else { element->parent->right = element->left; } } else { *t = element->left; } free(element); } else if (element->left == NULL && element->right!= NULL) {//only right child element->right->parent = element->parent; if (hasParent) { if (isLeft) { element->parent->left = element->right; } else { element->parent->right = element->right; } } else { *t = element->right; } free(element); } else {//it has two children... //find the minimum of the right subtree and relabel the current element with it + delete the newly found element. tree *right_min = find_min(element->right); element->item = right_min->item;//relabel //delete the new minimum delete_element(&right_min, right_min->item); } }
|