Бінарні дерева На відміну від списків, які базуються на лінійній організації зв'язків між елементами, дерева є розгалуженими ієрархічно організованими. - презентация

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

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

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

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

5 Прийоми роботи з деревами пошуку розглянемо на прикладі формування дерева, елементами якого є слова- терміни та їх переклади. Потрібно відобразити структуру дерева, організувати пошук перекладів заданих слів, реалізувати очищення дерева. #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; //Вказівник на вершину дерева

6 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);//Видалення дерева з //динамічної пам'яті //динамічної пам'яті

7 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);

8 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);}

9 /*Функція додавання нового елементу*/ 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);//Знаходження //позиції для елементу //позиції для елементу}

10 /* Знаходження позиції буде виконуватись в залежності /* Знаходження позиції буде виконуватись в залежності від порівняння двох слів функцією 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; }

11 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);//Ввести у ліве піддерево}

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

13 /* Функція симетричного обходу, для виведення всіх елементів дерева (при цьому будуть почергово виведені всі елементи разом з перекладом):*/ 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);} eng,xz->ukr); printf("%15s %s\n",xz->eng,xz->ukr); PrintTree(xz->right); PrintTree(xz->right);}">

14 /*Цей же обхід використовується для виведення дерева функцією 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);//Відображення //лівого піддерева //лівого піддерева} eng);//Термін printf("%*c%s\n",k*8, ' ', xz->eng);//Термін ShowTree(xz->left,k+1);//Відображення ShowTree(xz->left,k+1);//Відображення //лівого піддерева //лівого піддерева}">

15 /*Рекурсивне обчислення висоти дерева:*/ 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;}

eng);//Порівняння " title="/*Функція знаходження заданого елемента та виведення його на екран*/ char *Find(char eng[],tree *xz) { if (xz==NULL) return "ERROR;//Даного if (xz==NULL) return "ERROR;//Даного //елемента немає //елемента немає int K=strcmp(eng,xz->eng);//Порівняння " class="link_thumb"> 16 /*Функція знаходження заданого елемента та виведення його на екран*/ 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);} eng);//Порівняння "> 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);}"> eng);//Порівняння " title="/*Функція знаходження заданого елемента та виведення його на екран*/ char *Find(char eng[],tree *xz) { if (xz==NULL) return "ERROR;//Даного if (xz==NULL) return "ERROR;//Даного //елемента немає //елемента немає int K=strcmp(eng,xz->eng);//Порівняння ">

17 Результат роботи: Вигляд дерева: 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 Введіть слово: Ми