43337

Обхід дерев

Курсовая

Информатика, кибернетика и программирование

Теоретична частина Обробка даних у вершинах дерева Лівий спадний обхід Лівий висхідний обхід Лівий змішаний обхід Приклад лівого спадного обходу LPreorder 10 Перелік використаної літератури 11 Код програми реалізації обходу дерев мовою С. На сьогоднішній день дерева є найбільш поширеною структурою. Вони популярні серед людей з технічним напрямком занять і не дарма: дерева забезпечують найшвидші і найоптимальніші умови для знаходження елемента серед інших в певній структурі. Звичайно існують...

Украинкский

2013-11-04

22.23 MB

6 чел.

10

Міністерство освіти і науки, молоді і спорту України

Національний технічний університет України

«Київский політехнічний інститут»

Навчально-науковий комплекс «Інститут прикладного системного аналізу»

Кафедра Системного Проектування

Курсова робота

З дисципліни «Програмування і алгоритмічні мови»

«Обхід дерев»

Виконала студентка групи Да-01

Тарасенко Оксана Геннадієвна

                                                            Керівник

                                                            доц. Романов Валерій Володимирович

2011г.

Зміст

Вступ 2

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

Обробка даних у вершинах дерева 5

· Лівий спадний обхід 6

· Лівий висхідний обхід 6

· Лівий змішаний обхід 7

Приклад лівого спадного обходу LPreorder 10

Перелік використаної літератури 11

Код програми реалізації обходу дерев мовою С. 12

Вступ

Ця робота присвячена дослідженню засобів обходу дерев.

На сьогоднішній день дерева є найбільш поширеною структурою. Вони використовуються майже в кожній галузі, що стосується програмування, моделювання інформаційних процесів, комунікаційних систем, системного аналізу і систематизації взагалі. Вони популярні серед людей з технічним напрямком занять, і не дарма: дерева забезпечують найшвидші і найоптимальніші умови для знаходження елемента серед інших в певній структурі. Звичайно, існують багато типів дерев, в залежності від мети їх створення, і багато операцій над деревами: створення дерева, включення елемента в дерево, обробка даних у вершинах дерев, видалення елемента з дерева, збереження і відновлення бінарного дерева, знищення бінарного дерева.  Але в будь-якому дереві найважливішою операцією все одно залишатиметься пошук (локалізація) елемента в дереві, бо на ній побудовані ледь не всі інші операції. Наприклад, включення елемента в дерево складається з трьох дій: пошуку місця включення, виділення динамічної пам’яті і безпосереднього занесення даних. При чому при пошуку місця для елемента ми повинні впевнитись у тому, що такого елемента ще не існує в цьому дереві. А це означає ще одну операцію обходу. Взагалі, дереваце така структура, що забезпечує найоптимальніші умови зберігання даних і також найменший час їх пошуку, а в збалансованих деревах взагалі можна знайти елемент зробивши лише один крок. Недарма розв’язанням проблем, пов’язаних з деревами, займаються не тільки національні і державні університети та дослідницькі інститути, а ще й великі комерційні підприємства та фірми. У дерева пошуку, дерева сортування й у взагалі таку область дискретної математики, як дерева вкладено величезну купу грошей, нескінченні роки розумової праці найяскравіших інтелектуалів планети. Проте щоб збалансовані дерева залишалися такими при тому, що в них зберігатимуться величезні об’єми даних, треба винайти ще більш ефективні методи обходу дерев, що займають менше часу і, крім того, ще б по ходу дєла сортували данні у відповідності з принципами, що я наводжу у теоретичній частині. Саме такі задачі поставлені перед нашою сьогоднішньою технічною елітою, і перед нами в тому ж числі. 

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

Обхід дерев найчастіше проходить задля пошуку елемента. А пошук елемента має на меті різні завдання. По-перше, визначити, чи належить шуканий елемент дереву, чи ні. В цьому випадку результатом буде повернення  ознаки про наявність елемента чи його відсутність( true or false, 1 чи 0 відповідно). По-друге, пошук з метою вибірки й опрацювання даних елементу, тоді результат пошуку повертається у вигляді адреси вершини. По-третє, пошук з метою видалення елементу, такий пошук часто є лиш частиною повної операції видалення, а не самостійною операцією. 

Сам алгоритм пошуку залежить від виду дерева. В ідеально збалансованому дереві пошук доводиться проводити обходом вершин в деякій послідовності. Мінімальна довжина пошуку тоді дорівнює 1, максимальна жn, ну а середня тодіn/2. 

Алгоритм пошуку в бінарному дереві пошуку, як в простому, так і в збалансованому, достатньо простий. Пошук проходить цілеспрямованим рухом вздовж ребер дерева. Якщо ключ пошуку дорівнює ключу у вершині, тоді ключ вважається знайденим і його адреса повертається через параметр-вказівник. Якщо ж ключ пошуку менший від ключа у вершині, тоді ми рухаємося по лівому піддереву, якщо ж навпаки, то тоді по правому піддереву. Якщо ж у черговій вершині рух вниз неможливий (вказівник дорівнює NULL), то це означає, що шуканого ключа в дереві не знайденойого там немає. Максимальна довжина пошуку дорівнює висоті дерева. 

Обробка даних у вершинах дерева

Розрізняють два види обробки: вибіркову обробку окремої вершини і послідовну обробку всіх вершин. Вибіркова обробка включає в себе пошук елементу, і обробку даних у вершині лише в тому випадку, коли шуканий елемент знайдений. Обробка даних залежить від задачі, що вирішується і може зводитись до вилучення данних з вершини без їх змін, або оновленню даних у вершині дерева.

При послідовній обробці проходить так званий обхід дерева. Обхід дерева –процес одноразового відвідування й обробки даних кожної вершини дерева. В залежності від того, в якому напрямку здійснюється рух вздовж гілок дерева і коли обробляються дані у вершинах, шість видів обходів: 

  •  Лівий спадний обхід LPreorder –рух згори до низу, від кореневої вершини до листків, реалізується таким алгоритмом: 

procedure ПРЕФІКСНИЙ ОБХІД(:дерево);

begin 
   Відвідати корінь  дерева ;

 if не лист then

Нехай                        піддерева кореня ;

        for i := 1 to k do ПРЕФІКСНИЙ-ОБХІД(

    ) end 

 end

end.

Таким чином проходить обробка даних у вузлі, потім лівий спадний обхід лівого піддерева, і нарешті лівий спадний одхід правого піддерева. В нашому випадку це буде така послідовність вершин: 12, 4, 2, 1, 3, 8, 6, 5, 7, 10, 9, 11, 17, 14, 13, 16, 15, 20, 19, 18, 21.

  •  Лівий висхідний обхід LPostorderрух зліва направо, від самого лівого листка догори до кореня, потім донизу до самого правого листка. Реалізується таким алгоритмом:

 procedure ПОСТФІКСНИЙ ОБХІД(:дерево);

begin 
   Відвідати корінь  дерева ;

 if не лист then

Нехай                        піддерева кореня ;

        for i := 1 to k do ПОСТФІКСНИЙ-ОБХІД(     ) end 

 end

end.

 Таким чином в нас проходить спочатку лівий висхідний обхід лівого піддерева, потім лівий висхідний обхід правого піддерева, і тільки потім обробка даних у вузлі. Цьому алгоритму відповідає така послідовність вершин: 1, 3, 2, 5, 7, 6, 9, 11, 10, 8, 4, 13, 15, 16, 14, 18, 19, 21, 20, 17, 12. 

  •  Лівий змішаний обхід LІnorderрух зліва направо, від самого лівого листка догори до кореня, потім донизу до самого правого листка. Реалізується таким алгоритмом: 

procedure ІНФІКСНИЙ ОБХІД(:дерево);

begin 
   Відвідати корінь  дерева ;

 if не лист then

Нехай                        піддерева кореня ;

        for i := 1 to k do ІНФІКСНИЙ-ОБХІД(      ) end 

 end

end.

Таким чином в нас проходить спочатку лівий змішаний обхід лівого піддерева, потім обробка даних у вузлі, а вже потімлівий змішаний обхід правого піддерева.  Цьому алгоритму в нашому випадку відповідає послідовність вершин: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21.

При всіх обходах рух по гілкам дерева продовжується до тих пір, поки вказівник на вузол дерева не стане нульовим.

 Застосовуються також і праві обходи дерев: правий спадний RPreorder, правий висхідний RPostorder і правий змішаний RInorder. Їх алгоритми отримуються з алгоритмів лівих обходів шляхом заміни «лівий» на «правий». Тому їх іноді називають зворотніми обходами.

 Окрім спадного, висхідного й змішаного обходів, що були вже розглянуті нами, іноді застосовують обхід дерева по рівням. При такому обході вузли дерева відвідуються згори до низу і зліва на право, тобто спочатку корінь дерева, потім вузли першого рівня зліва на право, потім вузли другого рівня зліва на право, і т.д.

 Функції обходу дерев можуть бути як рекурсивними, так і ітеративними, найбільш просто реалізуються рекурсивні функції перших шести видів обходу, що ми вже розглядали, в них рекурсивний обхід відповідає рекурсивній структурі дерева. В них, природно, використовуються системні стеки. У не рекурсивних функціях доводиться використовувати явний стек, який, як відомо, реалізується правилом LIFO –ввійшов останнім, вийшов першим. 

Обхід вздовж рівнів (коріньперший рівеньдругий рівеньтретій рівень –…) не відповідає рекурсивній структурі дерева (коріньпіддерево кореняпіддерево піддерева –…). В не рекурсивній функції обходу по рівням замість стеку доводиться використовувати чергу типу FIFO –ввійшов першим, першим вийшов.  

             

Очевидно, ця функція обробки даних у вершинах дерева залежить від конкретного застосування дерева. В той же час алгоритми обходів дерев залишаються стабільними і працюють незалежно від конкретної структури. Бінарні дерева пошуку можуть бути використані не тільки відповідно зі своїм прямим призначеннямпошуком елементів, а й для сортування даних. Проводячи лівий змішаний обхід бінарного дерева пошуку і розташовуючи дані з вузлів у тому порядку, в якому вони зустрічаються, отримаємо послідовну множину елементів-ключів дерева, впорядковану за зростанням. Аналогічно, правий змішаний обхід дерева дасть нам послідовну множину елементів-ключів дерева, впорядковану за спаданням. Тому інколи про дерева пошуку кажуть як про дерева сортування.

При роботі з деревами виникає ситуація, коли до певних елементів звертаються частіше, до іншихрідше. Трапляються ситуації, коли необхідно повторно звертатись до елементів, до яких були зверненні найсвіжіші запити. Час досягнення цих елементів було б логічно скоротити, помістивши їх ближче до кореня дерева. Для цього достатньо помістити в корінь дерева вузол, до якого був звернений останній запит. Таким чином всі елементи, що використовувались найчастіше, опиняться в такій близькості від кореня, яка б відповідала частоті їх застосування. Це буде зручно для користувача, якщо, звісно, він ставить перед собою таку мету. Якщо ж використання елементів залежить напряму від теорії вірогідності (кожен елемент використовуватиметься вдруге не раніше, ніж всі інші елементи використаються вперше, або взагалі один раз), то має логічне місце пересунення «використаних» вершин в листки або взагалі їх видалення. 

Приклад лівого спадного обходу LPreorder:   

Перелік використаної літератури

  1.  Н. Вирт Алгоритми і структури даных. М.: Мир, 1989. Глава 4.5 (С. 272-286)
  2.  Г. М. Адельсон-Вельский, Е. М. Ландис. Один алгоритм організації інформації // Доповіді АН СССР. 1962. Т. 146, 2. C. 263.
  3.  Б. С. Хусаїнов. Структури і алгоритми обробки даних. Приклади мовою Сі, Вид-во: Фінанси й статистика, 2004, (С. 155-196), 464 стр.
  4.  Ф. В. Лактионов, В. А. Філіпов, О. В. Андреев //Журнал наукових публікацій аспірантів и докторантів. 2008.4. С. 207-210.
  5.   http://algolist.ru/

Код програми реалізації обходу дерев мовою С.

#include <cstdlib>

#include <iostream>

#include <cstring>

using namespace std;

struct record {//Структура узла дерева

       int data;//Ключ

       record *leftPtr, *rightPtr;//Левый и правый указатели

       int bal;//Признак сбалансированности дерева

       };

void instructions(void);//Список возможных действий

int  insert(int, record **, int *);//Добавление ключа в дерево

void del(int, record **,int *);//Удаление ключа из дерева

void balanceL(record **, int *);

void balanceR(record **, int *);

void delbal(record**, record **, int*);

void rotL(record**);//Ротация влево

void retR(record**);//Ротация вправо

void preorder(record*);//Нисходящий обход

void inorder(record*);//Смешанный обход

void postorder(record*);//Восходящий обход

int main()

{

cout<<"Coursework. Work with AVL-trees."<<endl;

   cout<<"Made by Andrew Grushko, KPI, IASA, SP-SAPR, first course."<<endl;

record *root=NULL;

int *h=new int,choice,key;

instructions();

cin>>choice;

if(!choice) {

cout<<"Error in choice. Run again"<<endl;

return 0;

}

while(choice!=3) {

 switch(choice) {

  case 1:

cout<<"Type a number to insert into the tree: ";

cin>>key;

   insert(key,&root,h);//Добавление ключа в дерево

   inorder(root);//Вывод на экран

  break;

  case 2:

      cout<<"Type a number to delete from the tree: ";

       cin>>key;

   del(key,&root,h);//Удаления ключа из дерева

inorder(root);

  break;

  default:

   cout<<"Invalid choice."<<endl<<"? ";

  break;

 }

 instructions();

 cin>>choice;

}

cout<<"End of run."<<endl;

return 0;

}

//=================================inctructions()=========================

void instructions()

{

cout<<"Enter your choice:\n\

to insert a number into the tree.\n\

to delete a number from the tree.\n\

to end."<<endl;

cout<<"? ";

}

//=================================insert()===============================

int insert(int key, record **t, int *h)

{

record *t1, *t2, *T; int ret=0;

T=*t;

if(T==NULL) {//дерево пустое

       T=new record;

T->data=key;

T->bal=0;

*h=1;

T->leftPtr=T->rightPtr=NULL;

}//поиск ключа в дереве

   else if(key<T->data) {

       insert(key, &T->leftPtr,h);

if(*h) {

switch(T->bal) {

case 1:T->bal=0; *h=0; break;

case 0:T->bal=-1;break;

case -1: {

t1=T->leftPtr;

if(t1->bal==-1){//LL-поворот

                       T->leftPtr=t1->rightPtr;

t1->rightPtr=T;

T->bal=0;

T=t1;

}

else {//Двукратный LR-поворот

                       t2=t1->rightPtr;

t1->rightPtr=t2->leftPtr;

t2->leftPtr=t1;

T->leftPtr=t2->rightPtr;

t2->rightPtr=T;

if(t2->bal==-1)

T->bal=1;

else

T->bal=0;

if(t2->bal==1)

t1->bal=-1;

else

t1->bal=0;

T=t2;

}

T->bal=0;*h=0;

}

}

}

}

else if(key>T->data) {

insert(key,&T->rightPtr,h);

if(*h==1)

switch (T->bal){

case -1: T->bal=0; *h=0; break;

case 0: T->bal=1; break;

case 1: {//балансировка

               t1=T->rightPtr;

if(t1->bal==1) {//RR-поворот

                   T->rightPtr=t1->leftPtr;

t1->leftPtr=T;

T->bal=0; T=t1;

}

else {//двукратный RL-поворот

                   t2=t1->leftPtr;

t1->leftPtr=t2->rightPtr;

t2->rightPtr=t1;

T->rightPtr=t2->leftPtr;

t2->leftPtr=T;

if(t2->bal==1)

T->bal=-1;

else

T->bal=0;

if(t2->bal==-1)

t1->bal=1;

else

t1->bal=0;

T=t2;

}

T->bal=0;

*h=0;

}

}

}

else {

cout<<"/nDuplicate key: "<<key<<endl;

ret=-1;

}

*t=T;

return ret;

}

//====================================del()===============================

void del(int key, record **T, int *h)

{

record *t, *K; t=*T;

if(*T==NULL) {

cout<<"Element "<<key<<" is not found"<<endl;

*h=0;

}

else if(key<t->data) {

del(key,&t->leftPtr,h);

if(*h) balanceL(&t, h);

}

else if(key>t->data) {

del(key,&t->rightPtr,h);

if(*h) balanceR(&t,h);

}

   else {//Удаление

K=t;//Узел найден

if(K->rightPtr==NULL) {//Имеет только левую ветвь

t=K->leftPtr;

delete K;

*h=1;

}

else if(K->leftPtr==NULL) {//Имеет только правую ветвь

           t=K->rightPtr;

delete K;

*h=1;

}

else {

delbal(&K->leftPtr,&K,h);

if(*h) balanceL(&t,h);

}

}

*T=t;

}

//====================================delbal()============================

void delbal(record **R, record **K, int *h)

{

record *r, *k;

r=*R; k=*K;

if(r->rightPtr!=NULL) {//спускаемся по правым ветвям до конца

delbal(&r->rightPtr,&k,h);

if(*h) balanceR(R,h);

}

else {

k->data=r->data;

*R=r->leftPtr;

delete r;

*h=1;

}

}

//====================================balanceL()==========================

void balanceL(record **t, int *h)//h=1 => Левая ветвь короче

{

record *t1, *t2, *T;

int b1, b2;

T=*t;

switch(T->bal) {

case -1:T->bal=0; break;

case 0:T->bal=1; *h=0; break;

case 1: {//балансировка

           t1=T->rightPtr;

b1=t1->bal;

if(b1>=0) {//однократный RR-поворот

               T->rightPtr=t1->leftPtr;

t1->leftPtr=T;

if(!b1) {

T->bal=1;

t1->bal=-1;

*h=0;

}

else {

T->bal=0;

t1->bal=0;

}

T=t1;

}

else {//двукратный RL-поворот

               t2=t1->leftPtr;

b2=t2->bal;

t1->leftPtr=t2->rightPtr;

t2->rightPtr=t1;

T->rightPtr=t2->leftPtr;

t2->leftPtr=T;

if(b2==1) T->bal=-1;

else T->bal=0;

if(b2==-1) t1->bal=1;

else t1->bal=0;

T=t2;

t2->bal=0;

}

}

}

*t=T;

}

//====================================balanceR()==========================

void balanceR(record **t, int *h)//h=-1 =>Правая ветвь короче

{

record *t1, *t2, *T;

int b1, b2;

T=*t;

switch(T->bal) {

case 1:T->bal=0; break;

case 0:T->bal=-1; *h=0; break;

case -1: {//балансировка

           t1=T->leftPtr;

b1=t1->bal;

if(b1<=0) {//однократный LL-поворот

               T->leftPtr=t1->rightPtr;

t1->rightPtr=T;

if(!b1) {

T->bal=-1;

t1->bal=1;

*h=0;

}

else {

T->bal=0;

t1->bal=0;

}

T=t1;

}

else {//Двукратный LR-поворот

               t2=t1->rightPtr;

b2=t2->bal;

t1->rightPtr=t2->leftPtr;

t2->leftPtr=t1;

T->leftPtr=t2->rightPtr;

t2->rightPtr=T;

if(b2==-1) T->bal=1;

else if(b2==1) T->bal=-1;

else T->bal=0;

T=t2;

t2->bal=0;

}

}

}

*t=T;

}

//====================================preorder()==========================

void preorder(record *T)

{

if(T){

cout<<T->data<<", ";

preorder(T->leftPtr);

preorder(T->rightPtr);

}

}

//====================================inorder()===========================

void inorder(record *T)

{

if(T){

inorder(T->leftPtr);

cout<<T->data<<", ";

inorder(T->rightPtr);

}

}

//====================================postorder()=========================

void postorder(record *T)

{

if(T){

postorder(T->leftPtr);

postorder(T->rightPtr);

 cout<<T->data<<", ";

}

}


 

А также другие работы, которые могут Вас заинтересовать

25299. Філософський доробок С.Семковського 93 KB
  Тут він заснував першу в Україні кафедру марксизму і марксознавства яка потім перетворилася на Український інститут марксизму в якому до 1931 р. інституті марксизмуленінізму був створений філсоціолог. марксизму У 1918 р. кафедру марксизму і марксознавства яка потім перетв.
25300. В.Юринець та його філософський спадок 28.5 KB
  Юринець та його філософський спадок Юринець Володимир Олександрович 18911937.
25301. Слуховой анализатор 48.5 KB
  Средняя сосудистая оболочка в передней части глаза образует ресничное тело и радужную оболочку обуславливающую цвет глаз. Внутренняя сетчатая оболочка сетчатка или ретина содержит фоторецепторы глаза палочки и колбочки и служит для преобразования световой энергии в нервное возбуждение. Светопреломляющие среды глаза преломляя световые лучи обеспечивают четкое изображение на сетчатке. Основными преломляющими средами глаза человека являются роговица и хрусталик.
25302. Вкусовой и обонятельный анализатор 23.5 KB
  Хеморецепторы вкуса представляют собой вкусовые луковицы расположенные в эпителии языка задней стенке глотки и мягкого неба. Микроворсинки рецепторных клеток выступают из луковицы на поверхность языка и реагируют на растворенные в воде вещества. Рецепторы разных частей языка воспринимают четыре основных вкуса: горького задняя часть языка кислого края языка сладкого передняя часть языка и соленого яердняя часть и края языка.
25303. РОЛЬ СЕНСОРНЫХ СИСТЕМ В УПРАВЛЕНИИ ДВИЖЕНИЯМИ. СОМАТОСЕНСОРНАЯ ЧУВСТВИТЕЛЬНОСТЬ И КОРРЕКЦИЯ ДВИЖЕНИЙ 35.5 KB
  СОМАТОСЕНСОРНАЯ ЧУВСТВИТЕЛЬНОСТЬ И КОРРЕКЦИЯ ДВИЖЕНИЙ Выполнение движений сопряжено с растягиванием кожи и давлением на отдельные ее участки поэтому кожные рецепторы оказываются включенными в анализ движений. Эта функциональная связь является физиологической основой комплексного кинестетического анализа движений при котором импульсы кожных рецепторов дополняют мышечную проприоцептивную чувствительность. Благодаря проприоцепции возможны коррекция уточнение движений в соответствии с текущими потребностями выполнения произвольного действия....
25304. Физиологические реакции живого организма 39 KB
  Раздражение Раздражителем живой клетки или организма как целого может оказаться любое изменение внешней среды или внутреннего состояния организма если оно достаточно велико возникло достаточно быстро и продолжается достаточно долго. Клетки значительно более чувствительны по отношению к своим адекватным раздражителям чем к неадекватным. Возбудимость Некоторые клетки и ткани нервная мышечная и железистая специально приспособлены к осуществлению быстрых реакций на раздражение.
25305. Стресс 33.5 KB
  0004 ГОМЕОСТАЗ Внутренняя среда организма в которой живут все его клетки это кровь лимфа межтканевая жидкость. Ее характеризует относительное постоянство гомеостаз различных показателей так как любые ее изменения приводят к нарушению функций клеток и тканей организма особенно высокоспециализированных клеток центральной нервной системы. Способность сохранять гомеостаз в условиях постоянного обмена веществ и значительных колебаний факторов внешней среды обеспечивается комплексом регуляторных функций организма. существовать и двигаться...
25306. Адаптация 28 KB
  У человека адаптация выступает как свойство организма которое обеспечивается автоматизированными самонастраивающимися саморегулирующимися системами сердечнососудистой дыхательной выделительной и др. Адаптация это эффективная и экономная адекватная приспособительная деятельность организма к воздействию факторов внешней среды. Чем выше уровень интеграции координированности сложных регуляторных процессов тем эффективнее адаптация.
25307. Природа потенциала покоя 28.5 KB
  Согласно этой теории биоэлектрические потенциалы обусловлены неодинаковой концентрацией ионов К' N3' СГ внутри и вне клетки и различной проницаемостью для них поверхностной мембраны. Протоплазма нервных и мышечных клеток содержит в 3050 раз больше ионов калия в 810 раз меньше ионов натрия и в 50 раз меньше ионов хлора чем внеклеточная жидкость. На структурных элементах мембраны фиксируются различные ионы что придает стенкам ее пор тот или иной заряд и тем самым затрудняет или облегчает прохождение через них ионов. Так предполагается...