Бінарні дерева На відміну від списків, які базуються на лінійній організації зв'язків між елементами, дерева є розгалуженими ієрархічно організованими динамічними структурами. Елемент дерева називають вузлом або вершиною. Найстарший вузол (вершина всього дерева ) – корінь. Корінь розташований на найвищому першому рівні. Вузол може мати нащадків, його називають батьківським, а вузли- нащадки – дочірніми вузлами. Кожен дочірній вузол повязаний з одним батьківським, а рівень дочірніх вузлів на один нижчий, ніж у батьківського. Кількість дочірніх елементів визначає степінь вузла, а найільший для вузлів степінь називають степенем дерева. Елементи, які не мають дочірніх вузлів, називають листками (кінцевими елементами). Частину дерева, що зберігає деревоподібну структуру, називають піддеревом.

Дані NULL Бінарними ( або двійковими ) називають дерева, кожен елемент яких складається з інформаційної частини та двох вказівників: на лівий і на правий дочірній вузли. Степінь усіх вузлів бінарного дерева не перевищує двох. Висотою дерева називають максимальну кількість рівнів від кореня до кінцевого елемента.

Вузол дерева оголошується як структура, яка містить інформаційне поле і вказівники на дочірні елементи (лівий і правий ) typedef stuct tree_elem { elemtype val; struct tree_elem *left, *right; } tree; Дерево пошуку – впорядковане бінарне дерево, в якому кожен лівий дочірній вузол містить дані, ключовий елемент яких менший, ніж у батьківського вузла, а кожен правий вузол – дані, ключовий елемент яких більший за ключ батьківського вузла (ключ – певна ознака, за якою здійснюється впорядкування).

Впорядковане дерево з тими самими вершинами може мати різну конфігурацію і висоту. Дерево може виродитись у лінійний список (висота дорівнює загальній кількості вузлів). Дерево вважається збалансованим, якщо коефіцієнт розбалансованості для кожного його піддерева потрапляє в межі від -1 до 1 ( коефіцієнт – різниця висот лівого і правого піддерев ). Пошук даних базується на впорядкованості дерев, не потребує перегляду всіх елементів. В найгіршому випадку кількість кроків перегляду дорівнює висоті дерева (кількості елементів по найбільшій гілці дерева). Для збалансованого дерева, що має n вузлів, кількість кроків становить [ log n ] + 1, де [ ] - є ціла частина виразу. 2

Прийоми роботи з деревами пошуку розглянемо на прикладі формування дерева, елементами якого є слова- терміни та їх переклади. Потрібно відобразити структуру дерева, організувати пошук перекладів заданих слів, реалізувати очищення дерева. #include #include typedef struct words {//Оголошення типу для дерева typedef struct words {//Оголошення типу для дерева char eng[15], ukr[15]; char eng[15], ukr[15]; words *left,*right; words *left,*right; } tree; } tree; tree *head=NULL; //Вказівник на вершину дерева tree *head=NULL; //Вказівник на вершину дерева

void place(tree *pnew, tree **addr); //Встановлення позиції для нового елементу //Встановлення позиції для нового елементу void Add(char eng[], char ukr[]);//Додавання нового // елементу // елементу char *Find(char eng[], tree *xz);//Знаходження //необхідного слова //необхідного слова int TreeHeight( tree *xz); //Висота дерева void PrintTree( tree *xz); //Відображення всіх //елементів і перекладів //елементів і перекладів void ShowTree( tree *xz,int k);//Показ дерева void ClearTree( tree *xz);//Видалення дерева з //динамічної пам'яті //динамічної пам'яті

void main() { //Додавання елементів в дерево //Додавання елементів в дерево Add("I",Я"); Add("I",Я"); Add("You",Ти"); Add("You",Ти"); Add("We",Ми"); Add("We",Ми"); Add("He",Він"); Add("He",Він"); Add("She",Вона"); Add("She",Вона"); Add("It",Воно"); Add("It",Воно"); Add("They",Вони"); Add("They",Вони"); puts(Вигляд дерева\n"); puts(Вигляд дерева\n"); ShowTree(head,0); ShowTree(head,0); puts("\nВсі слова(симетричний обхід)\n"); puts("\nВсі слова(симетричний обхід)\n"); PrintTree(head); PrintTree(head);

printf(Висота дерева - %d\n",TreeHeight(head)); printf(Висота дерева - %d\n",TreeHeight(head)); char sl[15]; char sl[15]; printf(Введіть слово:"); printf(Введіть слово:"); scanf("%s",&sl); scanf("%s",&sl); printf(Переклад - %s\n",Find(sl,head)); printf(Переклад - %s\n",Find(sl,head)); ClearTree(head); ClearTree(head);}

/*Функція додавання нового елементу*/ void Add(char eng[], char ukr[]) { tree *q; tree *q; q=(words*)malloc(sizeof(words)); q=(words*)malloc(sizeof(words)); //Виділення динамічної пам'яті //Виділення динамічної пам'яті q->left=NULL; q->left=NULL; q->right=NULL; q->right=NULL; strcpy(q->eng,eng);//Запис термінів strcpy(q->eng,eng);//Запис термінів strcpy(q->ukr,ukr); strcpy(q->ukr,ukr); place(q,&head);//Знаходження place(q,&head);//Знаходження //позиції для елементу //позиції для елементу}

/* Знаходження позиції буде виконуватись в залежності /* Знаходження позиції буде виконуватись в залежності від порівняння двох слів функцією strcmp ( ). Приєднання нового вузла відбувається рекурсивно. Після порівняння елемента з вершиною дерева елемент визначається в ліве або праве піддерево, потім це піддерево розглядається або праве піддерево, потім це піддерево розглядається окремо цією ж функцією, доки не буде знайдено вільне місце */ void place(tree *pnew,tree **addr) void place(tree *pnew,tree **addr) { tree *root=*addr; tree *root=*addr; if (root==NULL) if (root==NULL) { *addr=pnew; *addr=pnew; return; return; }

int K=strcmp(pnew->eng,root->eng); int K=strcmp(pnew->eng,root->eng); if (K==0) //Якщо даний елемент існує if (K==0) //Якщо даний елемент існує { free(pnew); //Звільняється память, free(pnew); //Звільняється память, // виділена під нього // виділена під нього return; return; } if (K>0) if (K>0) place(pnew,&root->right);//Ввести у праве піддерево place(pnew,&root->right);//Ввести у праве піддерево else else place(pnew,&root->left);//Ввести у ліве піддерево place(pnew,&root->left);//Ввести у ліве піддерево}

/* У цьому випадку дерево повинне мати вигляд:*/ /* Практично всі функції є рекурсивними, оскільки за своєю організацією дерево є рекурсивною структурою. Обхід дерева можливий декількома способами: Симетричний – спочатку обходять одне піддерево, потім корінь, потім інше Симетричний – спочатку обходять одне піддерево, потім корінь, потім інше Прямий – корінь, потім почергово ліве та праве піддерево Прямий – корінь, потім почергово ліве та праве піддерево Нижній – спочатку почергово ліве та праве піддерево, а потім корінь */ Нижній – спочатку почергово ліве та праве піддерево, а потім корінь */ IHeYouWeSheItThey

/* Функція симетричного обходу, для виведення всіх елементів дерева (при цьому будуть почергово виведені всі елементи разом з перекладом):*/ void PrintTree(tree *xz) { if (xz==NULL) return; if (xz==NULL) return; PrintTree(xz->left); PrintTree(xz->left); printf("%15s %s\n",xz->eng,xz->ukr); printf("%15s %s\n",xz->eng,xz->ukr); PrintTree(xz->right); PrintTree(xz->right);}

/*Цей же обхід використовується для виведення дерева функцією ShowTree(), яка показує розташування вузлів, функцією ShowTree(), яка показує розташування вузлів, Друкуючи кожен елемент на своєму рівні.*/ void ShowTree(tree *xz,int k) { if (xz==NULL) return; if (xz==NULL) return; ShowTree(xz->right,k+1); //Відображення першого піддерева ShowTree(xz->right,k+1); //Відображення першого піддерева printf("%*c%s\n",k*8, ' ', xz->eng);//Термін printf("%*c%s\n",k*8, ' ', xz->eng);//Термін ShowTree(xz->left,k+1);//Відображення ShowTree(xz->left,k+1);//Відображення //лівого піддерева //лівого піддерева}

/*Рекурсивне обчислення висоти дерева:*/ int TreeHeight(tree *xz) { int lh,rh; int lh,rh; if (xz==NULL) return 0;//Дерево порожнє if (xz==NULL) return 0;//Дерево порожнє lh=TreeHeight(xz->left); //Висота лівого піддерева lh=TreeHeight(xz->left); //Висота лівого піддерева rh=TreeHeight(xz->right); //Висота правого піддерева rh=TreeHeight(xz->right); //Висота правого піддерева return lh>rh?lh+1:rh+1; return lh>rh?lh+1:rh+1;}

/*Функція знаходження заданого елемента та виведення його на екран*/ char *Find(char eng[],tree *xz) { if (xz==NULL) return "ERROR;//Даного if (xz==NULL) return "ERROR;//Даного //елемента немає //елемента немає int K=strcmp(eng,xz->eng);//Порівняння двох слів int K=strcmp(eng,xz->eng);//Порівняння двох слів if (K==0) return xz->ukr;//Дані слова однакові if (K==0) return xz->ukr;//Дані слова однакові if (K>0) return Find(eng,xz->right); if (K>0) return Find(eng,xz->right); else return Find(eng,xz->left); else return Find(eng,xz->left);}

Результат роботи: Вигляд дерева: Your Your We We They They She She It It I He He Всі слова(симетричний обхід) He Він He Він I Я I Я It Воно It Воно She Вона She Вона They Вони They Вони We Ми We Ми Your Ти Your Ти Висота дерева - 5 Введіть слово: Ми