Связанный список - это цепочка узлов, соединенных через «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
