0Pricing
C Academy · Урок

Узлы и структура дерева

Моделируйте узел с указателями.

«Узлы и структура дерева» — бесплатный урок C Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

Что такое двоичное дерево

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

Самый верхний узел называется корнем. Узлы без потомков — листья. Благодаря такой структуре двоичные деревья отлично подходят для быстрого поиска, сортировки и рекурсивной обработки.

Структура Node

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

Каждый указатель указывает на другой Node или на NULL, если потомка с этой стороны нет.

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

Зачем нужны указатели на узлы того же типа

Узел не может содержать другой полный узел по значению, поскольку это потребовало бы бесконечного объёма памяти. Вместо этого он хранит указатели на своих потомков.

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

struct Node {
    int value;
    struct Node *left;   /* 8 bytes on 64-bit */
    struct Node *right;  /* 8 bytes on 64-bit */
};

typedef для удобства

Писать struct Node повсюду утомительно. typedef позволяет записывать просто Node.

Имя структуры всё ещё требуется внутри неё, поскольку в этот момент тип ещё не определён полностью.

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

Выделение памяти для Node

Узлы хранятся в куче и создаются с помощью malloc. Мы задаём значение и инициализируем оба указателя на потомков значением NULL.

Всегда проверяйте, что malloc не вернул NULL, прежде чем использовать память.

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (n == NULL) return NULL;
    n->value = value;
    n->left = NULL;
    n->right = NULL;
    return n;
}

Создание небольшого дерева вручную

Чтобы понять связи, давайте вручную соединим три узла: корень с двумя потомками.

Эта программа создаёт дерево и выводит значения, а затем обычно освобождает память (это будет рассмотрено позднее).

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

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

Node *create_node(int v) {
    Node *n = malloc(sizeof(Node));
    n->value = v; n->left = NULL; n->right = NULL;
    return n;
}

int main(void) {
    Node *root = create_node(10);
    root->left = create_node(5);
    root->right = create_node(15);
    printf("%d %d %d\n", root->left->value, root->value, root->right->value);
    return 0;
}

Переход к внукам

Перемещаться по дереву можно, объединяя операции со стрелочным оператором. root->left->right перемещается к левому потомку, а затем к его правому потомку.

Перед переходом по указателю убедитесь, что он не равен NULL, иначе программа завершится с ошибкой.

/* root
 *   \
 *    right (15)
 *        \
 *         right->right (20)
 */
if (root->right != NULL && root->right->right != NULL)
    printf("%d\n", root->right->right->value);

Рекурсивный подсчёт узлов

Рекурсия естественным образом подходит для работы с деревьями. Чтобы посчитать узлы, у пустого поддерева их ноль; в противном случае нужно посчитать текущий узел и оба его поддерева.

Проверка на NULL — это базовый случай, останавливающий рекурсию.

int count_nodes(Node *root) {
    if (root == NULL) return 0;
    return 1 + count_nodes(root->left)
             + count_nodes(root->right);
}

Измерение высоты

Высота дерева — это длина самого длинного пути от корня до листа, измеренная в рёбрах.

Мы берём большую из высот двух поддеревьев и прибавляем единицу. Пустому дереву назначается высота -1, поэтому высота дерева из одного узла равна 0.

int height(Node *root) {
    if (root == NULL) return -1;
    int l = height(root->left);
    int r = height(root->right);
    return 1 + (l > r ? l : r);
}

Определение листьев

Лист — это узел без потомков: и left, и right равны NULL.

Эта небольшая вспомогательная функция полезна во многих процедурах обхода и подсчёта.

int is_leaf(Node *n) {
    return n != NULL && n->left == NULL && n->right == NULL;
}

Использование структуры

Здесь создаётся небольшое дерево, а его количество узлов и высота вычисляются с помощью рекурсивных вспомогательных функций.

Обратите внимание: вспомогательные функции не предполагают фиксированную форму дерева. Они работают с любым деревом, поскольку рекурсия следует фактическим указателям.

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

typedef struct Node { int value; struct Node *left, *right; } Node;

Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }

int main(void){
    Node *root = nn(10);
    root->left = nn(5); root->right = nn(15);
    root->left->left = nn(2);
    printf("nodes=%d height=%d\n", count(root), height(root));
    return 0;
}

Быстрая проверка

Проверьте, насколько хорошо Вы поняли структуру узла.

Повторение

Узел двоичного дерева хранит значение и два указателя на узлы того же типа (left, right), которым присваивается NULL, если соответствующий потомок отсутствует.

Мы выделяем узлы с помощью malloc, соединяем их вручную и обрабатываем рекурсивно. Проверка на NULL всегда является базовым случаем для подсчёта узлов, вычисления высоты и проверки листьев.

Часто задаваемые вопросы

Урок «Узлы и структура дерева» бесплатный?

Да — полный текст урока «Узлы и структура дерева» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Чему я научусь в уроке «Узлы и структура дерева»?

Моделируйте узел с указателями. Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Узлы и структура дерева»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Узлы и структура дерева
  2. Вставка в BST
  3. Обходы
  4. Поиск и освобождение
← Назад к C Academy