Язык C в примерах: сортировка массива двоичным деревом

После нашего весьма поверхностного знакомства с utf8 в языке C хочется привести какой-нибудь пример кода со структурами данных. Пусть это будет двоичное дерево, используемое для сортировки числовых данных в массиве. Почему именно сортировка — не знаю, просто это элементарный пример и просто так получилось 🙂 . Сначала посмотрим текст программы, а потом уже поговорим, что к чему:

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

// Структура данных "узел двоичного дерева"
struct tree_node {
  int data;
  struct tree_node *l_node;
  struct tree_node *r_node;
};

// Функция добавления данных в дерево
struct tree_node * add_data(struct tree_node *t_node, int data) {
  if (t_node == NULL) {
    t_node = (struct tree_node *)malloc(sizeof(struct tree_node));
    (*t_node).data = data;
    (*t_node).l_node = NULL;
    (*t_node).r_node = NULL;
  } else {
    if (data < (*t_node).data) {
      (*t_node).l_node = add_data((*t_node).l_node, data);
    } else {
      (*t_node).r_node = add_data((*t_node).r_node, data);
    }
  }
  return t_node;
}

// Функция для вывода на экран всех элементов двоичного дерева
void print_tree(struct tree_node *t_node) {
  if (t_node != NULL) {
    print_tree((*t_node).l_node);
    printf("%5d", (*t_node).data);
    print_tree((*t_node).r_node);
  }
}

// Функция полного удаления двоичного дерева
struct tree_node * delete_tree(struct tree_node *t_node) {
  if (t_node != NULL) {
    (*t_node).l_node = delete_tree((*t_node).l_node);
    (*t_node).r_node = delete_tree((*t_node).r_node);
    free(t_node);
  }
  return NULL;
}

int main() {
  // Указатель на структуру struct tree_node, это будет "корень" дерева
  struct tree_node *my_tree = NULL;

  // Массив из 10 элментов типа int, содержащий ряд произвольных значений
  int arr[10] = {5, 3, 17, -4, -7, -13, 33, 0, 21, 2};

  printf("Исходные данные: ");

  // В цикле наполняем дерево значениями из массива
  for (int i = 0; i < 10; i++) {
    printf("%5d", arr[i]);
    my_tree = add_data(my_tree, arr[i]);
  }
  printf("\n");

  printf("Данные в дереве: ");

  // Выводим на экран всё содержимое дерева
  print_tree(my_tree);

  printf("\n");

  // Удаляем дерево со всем его содержимым
  my_tree = delete_tree(my_tree);

  return 0;
}

Не буду подробно рассказывать о двоичном дереве, предполагая, что многие и так знают, что это такое. Тем более что двоичное дерево — это всего лишь модель организации данных. У нас есть базовый элемент дерева — «узел». Это структура, содержащая три поля данных — поле с некой полезной информацией (например целым числом) и два указателя. Каждый из указателей может быть либо пустым (равным NULL), либо содержать адрес («указывать на…») такой же структуры типа «узел». Один из указателей условно назовем «левым», другой — «правым». В итоге каждый узел содержит указатели на два таких же узла. Поэтому дерево и называется двоичным. А поскольку один узел «связан» указателями с двумя другими узлами, каждый из которых также связан с парой таких же узлов и так далее — получаем древовидную структуру (поэтому дерево и называется «деревом»). У каждого узла может быть до двух «веток». Дерево не обязано быть симметричным — «ветки» могут быть разной длины («глубины») или отсутствовать вовсе.

У подобной структуры есть ряд полезных свойств:

• поскольку все узлы одного типа (структуры и размера), к ним можно применять однотипные операции;
• из одного узла можно «добраться» до всех последующих («дочерних», тех, что находятся в «ветвях»);
• имея «в руках» корневой («верхний») узел, можно обойти все элементы дерева;
• решение, в какую сторону двигаться при обходе элементов по ссылкам — «влево» или «вправо», — можно принимать в зависимости от некоторого условия.

Именно последнее свойство будем использовать в реализации алгоритма сортировки данных.

Теперь собственно к коду. Текст программы сохраним в файле proj05.c (наш прошлый эксперимент с языком C — proj04.c). Опишем структуру данных «узла»:

// Структура данных "узел двоичного дерева"
struct tree_node {
  int data;    // Поле данных - целое число со знаком
  struct tree_node *l_node;  // "Левый" указатель
  struct tree_node *r_node;  // "Правый" указатель
};

Простая и часто применяемая структура данных (кстати, её можно использовать для организации так называемого «двусвязного списка»). В поле data типа int будем помещать «полезные» данные. К полям-указателям l_node и r_node будем «цеплять» дочерние узлы.

Идем дальше. Объявляем функцию добавления данных в дерево:

// Функция добавления данных в дерево
struct tree_node * add_data(struct tree_node *t_node, int data) {
  if (t_node == NULL) {  // Если t_node равен NULL, то есть указатель пустой...
    // ...на t_node выделяем память нужного размера, другими словами - "создаем" узел
    t_node = (struct tree_node *)malloc(sizeof(struct tree_node));
    (*t_node).data = data;    // Сохраняем входящие данные
    (*t_node).l_node = NULL;    // Инициализируем значением NULL "левый" указатель
    (*t_node).r_node = NULL;    // Инициализируем значением NULL "правый" указатель
  } else {    // ...иначе сравниваем входящее значение с тем, что уже есть
    if (data < (*t_node).data) {  // Если число меньше того, что в узле
      (*t_node).l_node = add_data((*t_node).l_node, data);  // Рекурсия по "левой" ветке - идем влево
    } else {  // ...иначе (если больше или равно)
      (*t_node).r_node = add_data((*t_node).r_node, data);  // Рекурсия по "правой" ветке - идем вправо
    }
  }
  return t_node;  // Возвращаем указатель
}

Функция add_data() добавляет данные в дерево, создавая при этом очередной узел. В качестве аргументов она принимает указатель на дерево (точнее — указатель на «узел») struct tree_node *t_node и целое число int data, которое будет сохраняться как «полезные данные». Возвращает эта функция также указатель на «узел» дерева (struct tree_node *).

Важно отметить, что функция добавления данных (и узлов дерева) должна быть реализована возвращающей указатель, так как основной способ передачи параметров в функцию в языке C — передача по значению (можно для указателя реализовать передачу по ссылке, но выйдет довольно громоздко). Выделение памяти внутри функции происходит на указатель, являющийся стековой копией, и при выходе из функции его непременно нужно передать «наружу» через возвращаемый функцией результат, иначе указатель просто «потеряется».

Итак, как работает добавление данных в дерево. У нас есть «корневой» указатель на дерево, с помощью которого мы будем обращаться ко всем узлам. Вызываем функцию add_data(), передавая ей в качестве аргументов корневой указатель и текущие данные, которые надо сохранить в дереве. Результат, возвращаемый функцией, помещаем в наш корневой указатель.

И внутри. Указатель t_node — аргумент. Проверяем: если t_node равен NULL (указатель «пустой», «нулевой»), дерево («узел» дерева) надо создать. Для этого выделяем на указатель t_node память в «куче» функцией malloc в количестве, необходимом для элемента типа struct tree_node. Теперь t_node указывает на элемент типа struct tree_node. Через разыменовывание указателя обращаемся к полям структуры и заполняем их значениями — полезное целое число в поле (*t_node).data и значение NULL в поля-указатели.

Если же t_node не равен NULL, считаем, что по этому указателю есть узел дерева. Поэтому сравниваем входящие данные (целое число) со значением поля (*t_node).data узла. Если число меньше сохраненного в узле значения, то «идем налево» — вызываем рекурсивно нашу функцию add_data() по «левому» указателю (передавая указатель в качестве параметра и сохраняя в него же результат, возвращаемый функцией). Если число больше или равно сохраненному в узле значению — «идем направо» (вызываем рекурсивно add_data() по правому указателю). Так и происходит упорядоченное размещение данных в двоичном дереве (в данном случае — в зависимости от значения data).

Кстати, при обращении к полям структуры через указатель вместо конструкции вида (*t_node).data можно использовать немного более простую t_node->data. Это кому как больше нравится 🙂

Далее — функция вывода на печать всего дерева (всех его элементов):

// Функция для вывода на экран всех элементов двоичного дерева
void print_tree(struct tree_node *t_node) {
  if (t_node != NULL) {  // Если указатель не пустой...
    print_tree((*t_node).l_node);  // Вызываем рекурсивно функцию печати дерева по "левой ветке"
    printf("%5d", (*t_node).data); // Выводим на печать значение поля data
    print_tree((*t_node).r_node);  // Вызываем рекурсивно функцию печати дерева по "правой ветке"
  }
}

Функция ничего не возвращает (не нужно, так как никаких изменений в дереве мы не производим), а за счет рекурсивного вызова позволяет осуществить «обход» всех элементов дерева, выводя попутно на печать сохраненные полезные данные. Здесь же можно установить порядок вывода (направление вывода) элементов — от меньшего к большему или наоборот. Или еще как-нибудь. В качестве аргумента функции — также указатель на дерево (на «узел»).

С учетом озвученного выше, принцип работы данной функции более чем очевиден: если указатель не «пустой», то запускаем рекурсивно печать по «левой» ветке дерева, затем печатаем значение data в текущем узле, затем запускаем рекурсивно печать по «правой» ветке. Так как в нашем случае при добавлении данных «влево» отправлялись данные с меньшими значениями data, а «вправо» — с большими значениями (выполнялась естественная сортировка), то и выводиться данные будут упорядоченно — от меньшего к большему. Естественно, функцию можно модифицировать для изменения порядка вывода.

И последняя функция — функция удаления дерева («узла» дерева):

// Функция полного удаления двоичного дерева
struct tree_node * delete_tree(struct tree_node *t_node) {
  if (t_node != NULL) {  // Если указатель не пустой...
    (*t_node).l_node = delete_tree((*t_node).l_node);  // Выполняем удаление по "левой ветке"
    (*t_node).r_node = delete_tree((*t_node).r_node);  // Выполняем удаление по "правой ветке"
    free(t_node);  // Освобождаем память по указателю
  }
  return NULL;  // Функция возвращаем "пустой" указатель в качестве признака освобождения памяти
}

Функция принимает в качестве аргумента указатель на дерево (на «узел»), возвращает также указатель на дерево, но уже со значением NULL. Функция позволяет рекурсивно обойти все элементы дерева, удаляя их при этом (освобождая память по соответствующим указателям). Работает примерно так же, как и функция печати элементов дерева. Если указатель не пустой, выполняется рекурсивное удаление «левой» ветки, потом удаление «правой» ветки, а затем освобождение памяти на текущем указателе с помощью функции free(). На «выход» отправляем значение NULL. Последнее можно было бы и не делать — все элементы удаляются корректно в силу их положения в дереве, — но тогда «корневой» («первый и он же последний») указатель после освобождения памяти остался бы не обнуленным (с неопределенным значением). Поэтому следуем логике: корневой указатель «пришел в работу» со значением NULL — и «ушел» со значением NULL 🙂

Все необходимые функции мы описали, теперь собственно программа.

Объявляем указатель на структуру struct tree_node и инициализируем его значением NULL:

struct tree_node *my_tree = NULL;

Это наш «корневой» указатель, через него мы будем получать доступ ко всем элементам дерева.

Объявляем массив из десяти (например) элементов типа int и наполняем его некоторыми неупорядоченными значениями:

int arr[10] = {5, 3, 17, -4, -7, -13, 33, 0, 21, 2};

Данные для наполнения дерева будем брать из этого массива. Это исключительно для простоты иллюстрации — мы могли бы вводить данные с клавиатуры и наполнять дерево по мере ввода значений. Можете сделать это самостоятельно.

Используя цикл, наполняем дерево значениями из массива. В качестве аргументов передаем функции add_data() каждый раз наш корневой указатель и очередное значение из массива. Значение указателя, возвращаемое функцией, помещаем в наш корневой указатель (так мы сохраняем связь корневого указателя с другими элементами дерева). Для самопроверки и последующего сравнения выводим исходные значения из массива на экран.

for (int i = 0; i < 10; i++) {
    printf("%5d", arr[i]);
    my_tree = add_data(my_tree, arr[i]);  // Добавляем очередной элемент в дерево
  }

Выводим на экран всё содержимое дерева (все значения в его узлах):

print_tree(my_tree);  // Обход всех элементов дерева с выводом данных

Удаляем дерево (и освобождаем всю выделенную под его элементы память):

my_tree = delete_tree(my_tree);  // После этого my_tree содержит значение NULL

Скомпилируем программу и запустим её, чтобы увидеть результат:

username ~/Папка_с_программой $ gcc -Wall -o proj05 proj05.c
username ~/Папка_с_программой $ ./proj05
Исходные данные:     5    3   17   -4   -7  -13   33    0   21    2
Данные в дереве:   -13   -7   -4    0    2    3    5   17   21   33
username ~/Папка_с_программой $

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

Пусть и многословно, но пока так 🙂