Дървета Цел



Дата30.05.2017
Размер18.97 Kb.
ЛУ- 11

Дървета



Цел: Придобиване на пракически навици в дефинирането на дървовидни структури от данни, действия над тях и използването им в програми на С/С++

Теоретична част:

Дървото може да бъде определено като рекурсивна структура, състояща се от корен и поддървета, като поддървото също е дърво. Възлите се представят като структури(в C/C++), с членове - за значение( поне един) и указатели за следващ възел.

При двоичното дърво указателите са 2 – един за ляв и един за десен “син”. Пример за такова дърво е даден на следващата фиг.11.1:


Ред за

пристигане

на числата:

15,8,5,10,23 114,28

Фиг.11.1. Сортирано дърво по метода : “ляво_поддръво-корен-дясно_поддърво”


Задача 1: Сортиране и търсене в двоично дърво


Сортирането в двоично дърво е всъщност процесът на изграждане на дървото по реда на пристигащите елементи[9]. Един от алгоритмите подрежда всеки пристигнал елемент в лявото поддърво на корена, ако той е по-малък от корена, и в дясното поддърво – в обратен случай и това се повтаря рекурсивно, като всеки следващ възел става корен. Сортирането на дървото се свежда до намиране на място за новопостъпил елемент. При този подход оценката за сложността е

Т ср.мин = O(N*log N)

Тср.макс= О(N*N)

и зависи от големината на образуваното до момента дърво. Ако дървото е балансирано, то разстоянието от кой да е възел до корена не надвишава log N – оценката е минимална. Оценката е максимална при изродено (в линеен списък) дърво.

Следващата функция сортира (вмъква елемент в) двоично дърво.

void B_tree(pointer p){

if (p==NULL) {

p->L=NULL; p->R=NULL;}

else {

if (new_key>p->x)



B_tree(p->R);

else


B_tree(p->L);

}

Въпроси по темата и задачи за изпълнение:

1. Дайте пример с поредица от числени стойности, при постъпването на които, изгражданото дърво се изражда в линеен списък, ако сортирането е по метода “ляво_поддърво – корен – дясно_поддърво”?

2. Какви са оценките за Тср.мин и Тср.макс при претърсване на едно неизродено дърво? А при изродено дърво?



3. Да се напише програма на С/С++, която реализира сортиране на двоично дърво от числени елементи по метода “ляво_поддърво – корен – дясно_поддърво”


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница