Двоичное дерево. Логическое описание

Модуль "Деревья" • урок 5 из 11 • ~8 минут

Отсутствие базового типа данных

В отличие от языков функционального и логического программирования (Лисп, Пролог), где деревья и списки являются базовыми примитивами, в процедурных языках программирования программист должен сам конструировать дерево. В стандартных библиотеках (например, в STL для C++) есть структуры данных, основанные на деревьях (std::set, std::map), но нет универсального абстрактного "дерева", так как слишком велико многообразие вариантов их обхода и модификации.

Таким образом, процедурная реализация средств работы с деревьями полностью ложится на плечи разработчика. Так же, как и в связных списках, цепная структура дерева состоит из динамически порождаемых элементов памяти, в которых предусмотрены ссылки на очередные компоненты структуры.

Двоичное дерево. Логическое описание: структура узла

В двунаправленных (двусвязных) списках у нас были указатели next (вперед) и prev (назад). В двоичном дереве линейное предшествование и следование заменяется нелинейным разветвлением. Указатели направлены влево вниз и вправо вниз.

Программное моделирование на языке C выглядит как естественное расширение узла двусвязного списка:

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

// Описание структуры узла дерева
struct node {
    int data;           // Информационная часть (полезные данные)
    struct node* left;  // Указатель на корень левого поддерева
    struct node* right; // Указатель на корень правого поддерева
};

// Синоним для удобства работы с указателями
typedef struct node* pnode;

Корнем дерева служит обычный указатель (pnode root = NULL;), который содержит адрес самого первого (верхнего) элемента. Если дерево пустое, этот указатель равен NULL. Узел, у которого оба указателя left и right равны NULL, называется листом.

Создание узла и сборка дерева

Для того чтобы не писать выделение памяти каждый раз вручную, удобно создать функцию-конструктор, которая берет на себя выделение памяти через malloc и инициализацию полей нулями (NULL):

pnode createNode(int value) {
    pnode newNode = (pnode)malloc(sizeof(struct node));
    if (newNode == NULL) {
        printf("Ошибка выделения памяти\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Теперь мы можем собрать дерево руками, просто связывая указатели друг с другом. Это полностью соответствует абстрактной функции ПОСТРОИТЬ из функциональной спецификации (которая принимает два поддерева и корень).

int main() {
    // Создаем узлы
    pnode root = createNode(10);
    pnode leftChild = createNode(5);
    pnode rightChild = createNode(15);
    
    // Связываем их в дерево
    root->left = leftChild;
    root->right = rightChild;
    
    // Добавим еще листья к левому поддереву
    leftChild->left = createNode(2);
    leftChild->right = createNode(7);
    
    return 0;
}

Рекурсивная визуализация (печать)

Из-за того, что дерево - структура рекурсивная, любые операции по его обработке тоже удобнее всего писать рекурсивно. Например, чтобы распечатать дерево на экране консоли в понятном виде, можно использовать обход, передавая текущий уровень глубины (для отступов).

void printTree(pnode root, int level) {
    if (root == NULL) {
        return;
    }
    
    // Сначала печатаем правое поддерево (оно будет сверху в консоли)
    printTree(root->right, level + 1);
    
    // Делаем отступ, пропорциональный уровню
    for (int i = 0; i < level; i++) {
        printf("    ");
    }
    // Печатаем сам узел
    printf("%d\n", root->data);
    
    // Затем левое поддерево (оно будет снизу)
    printTree(root->left, level + 1);
}

Этот простой рекурсивный алгоритм (обратный обход "право-корень-лево") выведет дерево боком. Корень окажется слева, а ветви будут уходить вправо. Это отличный способ быстрой отладки деревьев в консоли, без необходимости привлекать сложные графические библиотеки.