Ильницкий В.Г.

Старший преподаватель кафедры программного обеспечения

Костанайского государственного университета им.А.Байтурсынова. Казахстан

Сортировка данных с использованием бинарного дерева

При работе с бинарными деревьями поиска, поиск и обход всех элементов дерева осуществляется намного быстрее, чем в массиве или линейном списке. При симметричном обходе дерева поиска данные выводятся в отсортированном порядке. Это свойство можно использовать для быстрой сортировки данных. Сначала при вводе данных строим дерево поиска, затем обходим все его элементы применяя симметричный обход. Программа выглядит следующим образом:

Сначала прописываем структуру, содержащую описание элемента дерева.

struct tre {

int val;

tre *l,*r;

};

Задаем первоначальное значение вершины дерева как NULL

tre *mytop=NULL;

При вводе очередных данных обращаемся к процедуре void searchtree(tre **t,int x), которая сначала ищет место для соответствующего элемента, затем вставляет его.

void searchtree(tre **t,int x) {

if ((*t)==NULL) {(*t)=new tre; (*t)->r=(*t)->l=NULL; (*t)->val=x; return;}

if (x>(*t)->val) {searchtree(&(*t)->r, x);} else {searchtree(&(*t)->l, x);};

}

И наконец процедура void obxod(tre *t) осуществляет симметричный обход дерева поиска, выводя данные в отсортированном порядке.

void obxod(tre *t) {

if (t->l!=NULL) obxod(t->l);

Form1->Label1->Caption=Form1->Label1->Caption+" "+t->val;

if (t->r!=NULL) obxod(t->r);

}

Можно так-же применить еще одну процедуру void ris(tre *t,int aa,int bb, int y), которая при вводе данных для наглядности рисует на форме дерево, что облегчает понимание данного метода.

void ris(tre *t,int aa,int bb, int y) {

if (t->l!=NULL) ris(t->l,aa,(aa+bb)/2,y+30);

Form1->Image1->Canvas->TextOutA((aa+bb)/2,y,t->val);

if (t->r!=NULL) ris(t->r,(aa+bb)/2,bb,y+30);

}

Литература:

1.А.Я. Архангельский «Язык С++ в С++ Builder»:БХВ – Петербург, 2002.

2. http://www.cyberforum.ru/cpp-beginners/thread117835.html

3. http://ci-plus-plus-snachala.ru/?p=89