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<<", ";

}

}


 

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

6920. Характеристики РЭС вне основных полос частот излучения и приема радиосигналов 49.5 KB
  Характеристики РЭС вне основных полос частот излучения и приема радиосигналов Любое РЭС характеризуется совокупностью параметров: функциональные - отражают основные функции выполняемые РЭС влияющие на ЭМС Функциональные параметры...
6921. Внеполосное радиоизлучение 136 KB
  Внеполосное радиоизлучение Внеполосное радиоизлучение - нежелательное излучение в полосе частот примыкающей к необходимой полосе частот, является результатом модуляции сигнала. Причины появления: применение для передачи сигналов с большой...
6922. Антенные устройства и среда распространения 67 KB
  Антенные устройства и среда распространения Энергетические характеристики Степень воздействия ИП на РП зависит: от коэффициентов ослабления помех в фидерах...
6923. Характеристики среды распространения влияющих на ЭМС 70 KB
  Характеристики среды распространения влияющих на ЭМС Ослабление определяется: особенностями распространения радиоволн различных частотных диапазонов отражение и рассеяние в тропосфере образование тропосферных волноводов отраж...
6924. Излучающие свойства и связь экранов 44 KB
  Излучающие свойства и связь экранов. Из-за неполного экранирования на внешних поверхностях экранов и элементов фидеров протекают электрические токи. Связь элементов ИП с РП определяется: действие полей на антенны РП появление наведенных...
6925. Блокирование, перекрестные искажения и интермодуляция 64.5 KB
  Блокирование, перекрестные искажения и интермодуляция. Воздействие помехи, значительно превышающей по уровню полезный сигнал, возможно помимо основного и побочного каналов приема. Влияние проявляется в виде: блокирование - изменение уровн...
6926. Индустриальные помехи 44.5 KB
  Индустриальные помехи. - электромагнитные помехи создаваемые различными электронными и электротехническими устройствами используемые в технике и быту. Причины появления: в цепях устройств протекают переменные электрические токи и создание поме...
6927. Методы анализа ЭМС 38 KB
  Методы анализа ЭМС. Анализ ЭМС проводят с целью определения возможности совместной работы радиотехнических, электронных и электротехнических средств. Группы задач: Исследование показателей ЭМС устройств и их элементов. Исследование элект...
6928. Расчет источников вторичного питания 132.5 KB
  Расчет источников вторичного питания Расчет трансформатора. Типовой источник электропитания содержит трансформатор, выпрямитель и сглаживающий фильтр, поэтому расчет состоит из определения параметров трансформатора, выборе диодов выпрямителя и...