Пов'язаний список - це ланцюжок вузлів, з'єднаних через «next» покажчики. Дерево схоже на пов'язаний список, але кожен вузол може бути пов'язаний із кількома вузлами.
Коли ми говоримо про дерево, ми маємо на увазі двійкове дерево, тобто структуру, яка має два дочірні елементи, ліворуч і праворуч.
Представлення двійкового дерева
Вузол двійкового дерева представлений структурою, що містить частину даних та два покажчики на інші структури того ж типу.
struct node
{
int data;
struct node *left;
struct node *right;
};
Спеціальний покажчик, званий ROOT , вказує на вузол, який є батьком усіх інших вузлів.
Крім того, вузли, які не мають дочірніх елементів, мають свої лівий і правий покажчики, що вказують на NULL .
Базове двійкове дерево з трьома вузлами може бути створене так:
/* Initialize nodes */ struct node *root; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->left = two; one->right = three; two->left = NULL; two->right = NULL; three->left = NULL; three->right = NULL; /* Save address of first node in root */ root = one;
За кілька кроків ми створили двійкове дерево з трьома вузлами.
Дерева можуть бути набагато глибшими та складнішими, ніж це. Дані, що зберігаються в кожному вузлі, можуть бути складнішими, і мати набагато більше дочірніх елементів, ніж два.
Застосування дерев
Дерева та їх варіанти є надзвичайно корисною структурою даних з безліччю практичних застосувань.
- Дерева бінарного пошуку (BST) використовуються для швидкої перевірки наявності елемента в наборі.
- Heap (Багато) – це вид дерева, який використовується для сортування безлічі елементів.
-
Модифікована версія дерева під назвою Tries використовується у сучасних маршрутизаторах для зберігання інформації про маршрутизацію.
Найпопулярніші бази даних використовують B-Trees (B-дерева) та T-Trees (T-дерева), які є варіантами деревоподібної структури, яку ми вивчили вище для зберігання своїх даних.
Компілятори використовують синтаксичне дерево для перевірки (підтвердження) синтаксису кожної написаної вами програми.
Повна програма C для реалізації Tree
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* left;
struct node* right;
};
struct node* createNode(value){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct node* insertLeft(struct node *root, int value) {
root->left = createNode(value);
return root->left;
}
struct node* insertRight(struct node *root, int value){
root->right = createNode(value);
return root->right;
}
int main(){
struct node *root = createNode(1);
insertLeft(root, 2);
insertRight(root, 3);
printf("The elements of tree are %d %d %d", root->data, root->left->data, root->right->data);
}
Виведення програми
1 2 3
