Структура данных - Дерево
Дерево — это типичная нелинейная структура данных, состоящая из узлов и рёбер, соединяющих узлы, используемая для представления иерархической связи «один ко многим» между элементами.
Основная терминология деревьев
Диаграмма терминологии дерева
AКорневой узел
Глубина 0
Глубина 0
BГлубина 1
CГлубина 1
DЛистовой узел
Глубина 2
Глубина 2
EЛистовой узел
FЛистовой узел
Корневой узелНет родителя, уникален
Дочерний узелПрямой дочерний узел
Листовой узелНет дочерних узлов
ГлубинаКоличество рёбер от корня до этого узла
ВысотаКоличество рёбер от этого узла до самого глубокого листа
Бинарное деревоКаждый узел имеет не более 2 дочерних узлов
Чтобы понять структуры деревьев, сначала нужно освоить несколько основных терминов:
| Термин | Значение |
|---|---|
| Корневой узел (Корень) | Начальный узел дерева, не имеющий родительского узла |
| Дочерний узел (Child) | Узел на следующем уровне, непосредственно связанный с данным узлом |
| Родительский узел (Parent) | Узел на предыдущем уровне, непосредственно связанный с данным узлом |
| Листовой узел (Leaf) | Узел, не имеющий дочерних узлов, т. е. конец дерева |
| Глубина (Depth) | Количество рёбер от корневого узла до данного узла; корневой узел имеет глубину 0 |
| Высота (Height) | Количество рёбер от этого узла до самого глубокого листового узла |
Обход бинарного дерева
Четыре метода обхода бинарных деревьев — на примере одного и того же дерева
1
2
3
4
5
Прямой обход (корень → левый → правый)
1 2 4 5 3Симметричный обход (левый → корень → правый)
4 2 5 1 3Обратный обход (левый → правый → корень)
4 5 2 3 1Обход по уровням (уровень за уровнем)
1 2 3 4 5Четыре распространённых метода обхода выглядят следующим образом:
| Метод обхода | Порядок посещения | Типичное применение |
|---|---|---|
| Прямой обход | Корень → левый → правый | Копирование деревьев, генерация префиксных выражений |
| Симметричный обход | Левый → корень → правый | BST выводит отсортированную последовательность |
| Обратный обход | Левый → правый → корень | Удаление деревьев, генерация постфиксных выражений |
| Обход по уровням | Слой за слоем, слева направо | BFS, вывод по слоям |
Пример
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int value) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
/* Прямой обход: корень → левый → правый */
void preOrder(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data); /* Сначала посетить корень */
preOrder(root->left); /* Затем обойти левое поддерево */
preOrder(root->right); /* Наконец обойти правое поддерево */
}
/* Симметричный обход: левый → корень → правый */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left); /* Сначала обойти левое поддерево */
printf("%d ", root->data); /* Затем посетить корень */
inOrder(root->right); /* Наконец обойти правое поддерево */
}
/* Постпорядковый обход: левый → правый → корень */
void postOrder(struct TreeNode* root) {
if (root == NULL) return;
postOrder(root->left); /* Сначала обойти левое поддерево */
postOrder(root->right); /* Затем обойти правое поддерево */
printf("%d ", root->data); /* Наконец посетить корень */
}
int main() {
/* Построить следующее бинарное дерево:
1
/ \
2 3
/ \
4 5 */
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Прямой обход: "); preOrder(root); printf("\n"); /* 1 2 4 5 3 */
printf("Симметричный обход: "); inOrder(root); printf("\n"); /* 4 2 5 1 3 */
printf("Обратный обход: "); postOrder(root); printf("\n"); /* 4 5 2 3 1 */
return 0;
}
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int value) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
/* Прямой обход: корень → левый → правый */
void preOrder(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data); /* Сначала посетить корень */
preOrder(root->left); /* Затем обойти левое поддерево */
preOrder(root->right); /* Наконец обойти правое поддерево */
}
/* Симметричный обход: левый → корень → правый */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left); /* Сначала обойти левое поддерево */
printf("%d ", root->data); /* Затем посетить корень */
inOrder(root->right); /* Наконец обойти правое поддерево */
}
/* Постпорядковый обход: левый → правый → корень */
void postOrder(struct TreeNode* root) {
if (root == NULL) return;
postOrder(root->left); /* Сначала обойти левое поддерево */
postOrder(root->right); /* Затем обойти правое поддерево */
printf("%d ", root->data); /* Наконец посетить корень */
}
int main() {
/* Построить следующее бинарное дерево:
1
/ \
2 3
/ \
4 5 */
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Прямой обход: "); preOrder(root); printf("\n"); /* 1 2 4 5 3 */
printf("Симметричный обход: "); inOrder(root); printf("\n"); /* 4 2 5 1 3 */
printf("Обратный обход: "); postOrder(root); printf("\n"); /* 4 5 2 3 1 */
return 0;
}
Двоичное дерево поиска (BST)
Двоичное дерево поиска (BST) — слева меньше, справа больше
50
30
70
20
40
60
80
Свойства и операции BST
Свойство: все значения в левом поддереве < корень < все значения в правом поддереве
Вставка/поиск: переходим в левое поддерево, если меньше, переходим в правое поддерево, если больше, O(log n) при сбалансированном дереве
Симметричный обход выводит возрастающую последовательность: 20 30 40 50 60 70 80
Примечание: вставка по порядку 1,2,3... вырождается в связный список O(n); AVL-дерево может решить эту проблему
Двоичное дерево поиска (BST)Требование: для каждого узла все значения в левом поддереве меньше узла, а все значения в правом поддереве больше узла.
Пример
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
/* Вставка в BST: рекурсивно найти подходящую позицию на основе величины значения
Временная сложность: O(h), h — высота дерева, O(log n) при сбалансированном дереве. */
struct TreeNode* insert(struct TreeNode* root, int value) {
if (root == NULL) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = node->right = NULL;
return node;
}
if (value < root->data) {
root->left = insert(root->left, value); /* Если меньше корня, вставить в левое поддерево */
} else if (value > root->data) {
root->right = insert(root->right, value); /* Если больше корня, вставить в правое поддерево */
}
return root; /* Если равно, игнорировать (BST обычно не хранит дублирующиеся значения) */
}
/* Поиск в BST: сравнить с текущим узлом, чтобы решить, искать слева или справа */
struct TreeNode* search(struct TreeNode* root, int target) {
if (root == NULL || root->data == target) {
return root; /* Целевое значение найдено или достигнут листовой узел */
}
if (target < root->data) {
return search(root->left, target); /* Целевое значение меньше, искать в левом поддереве */
}
return search(root->right, target); /* Целевое значение больше, искать в правом поддереве */
}
/* Симметричный обход (проверить упорядоченность BST) */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
int main() {
struct TreeNode* root = NULL;
int values[] = {50, 30, 70, 20, 40, 60, 80};
/* Последовательно вставляйте для построения BST */
for (int i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
printf("Симметричный обход BST (по возрастанию): ");
inOrder(root); /* Вывод: 20 30 40 50 60 70 80 */
printf("\n");
/* Тест поиска */
int target = 40;
struct TreeNode* found = search(root, target);
printf("%d %s\n", target, found ? "Найдено!" : "Не найдено");
/* Вывод: 40 Найдено! */
return 0;
}
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
/* Вставка в BST: рекурсивно найти подходящую позицию на основе величины значения
Временная сложность: O(h), h — высота дерева, O(log n) при сбалансированном дереве. */
struct TreeNode* insert(struct TreeNode* root, int value) {
if (root == NULL) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = node->right = NULL;
return node;
}
if (value < root->data) {
root->left = insert(root->left, value); /* Если меньше корня, вставить в левое поддерево */
} else if (value > root->data) {
root->right = insert(root->right, value); /* Если больше корня, вставить в правое поддерево */
}
return root; /* Если равно, игнорировать (BST обычно не хранит дублирующиеся значения) */
}
/* Поиск в BST: сравнить с текущим узлом, чтобы решить, искать слева или справа */
struct TreeNode* search(struct TreeNode* root, int target) {
if (root == NULL || root->data == target) {
return root; /* Целевое значение найдено или достигнут листовой узел */
}
if (target < root->data) {
return search(root->left, target); /* Целевое значение меньше, искать в левом поддереве */
}
return search(root->right, target); /* Целевое значение больше, искать в правом поддереве */
}
/* Симметричный обход (проверить упорядоченность BST) */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
int main() {
struct TreeNode* root = NULL;
int values[] = {50, 30, 70, 20, 40, 60, 80};
/* Последовательно вставляйте для построения BST */
for (int i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
printf("Симметричный обход BST (по возрастанию): ");
inOrder(root); /* Вывод: 20 30 40 50 60 70 80 */
printf("\n");
/* Тест поиска */
int target = 40;
struct TreeNode* found = search(root, target);
printf("%d %s\n", target, found ? "Найдено!" : "Не найдено");
/* Вывод: 40 Найдено! */
return 0;
}
Другие расширенияВ идеальном случае (когда дерево остаётся сбалансированным) вставка, удаление и поиск в BST могут выполняться за O(log n). Однако если сами данные упорядочены (например, вставка 1, 2, 3, 4...), BST вырождается в связный список, и эффективность падает до O(n). Чтобы решить эту проблему, в информатике были разработаныAVL-деревои другие самобалансирующиеся двоичные деревья поиска.