Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 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);

}

}

Date: 2015-12-12; view: 672; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию