Деревья и графы в C

Деревья и графы — это нелинейные структуры данных, используемые для представления иерархических данных и данных, связанных в сети.

В этом уроке Вы узнаете:

• Как устроены деревья и графы.
• Как реализовать двоичное дерево в C.
• Как представлять графы с помощью списков смежности и матриц смежности.

Что такое дерево?

Дерево — это иерархическая структура данных, состоящая из узлов.

Основные термины:

• Корень — верхний узел.
• Родитель и потомок — узлы, соединённые напрямую.
• Лист — узел без потомков.

Пример: Node двоичного дерева

В C узел двоичного дерева определяется с помощью struct с указателями на левого и правого потомка.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct Node *root = createNode(10);
    return 0;
}

Обход двоичного дерева

Методы обхода:

• Inorder (LNR) — левый, Node, правый.
• Прямой обход (NLR) — Node, левый, правый.
• Обратный обход (LRN) — левый, правый, Node.

Пример: обход Inorder

Эта программа выполняет обход Inorder двоичного дерева.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

Что такое граф?

Граф — это совокупность узлов (вершин), соединённых рёбрами.

Графы могут быть:

• Ориентированными — рёбра имеют направление.
• Неориентированными — рёбра не имеют направления.

Представление графов

Графы можно представлять с помощью:

• Матрицы смежности — двумерного массива, представляющего соединения.
• Списка смежности — списка, в котором каждый узел указывает на своих соседей.

Обход графа

Распространённые методы обхода:

• Поиск в ширину (BFS) — посещает всех соседей, прежде чем перейти глубже.
• Поиск в глубину (DFS) — исследует граф настолько глубоко, насколько возможно, прежде чем вернуться назад.

Итоги

В этом уроке Вы узнали:

• Как устроены деревья и графы.
• Как выполнять обходы деревьев.
• Как представлять графы и выполнять их обход.

На этом раздел «Структуры данных в C» завершён!