Деревом называется связный ориентированный граф, не содержащий циклов.


Дерево — одна из наиболее широко распространённых структур данных в информатике. Для деревьев выделяются следующие понятия:


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


Бинарное дерево – дерево, в котором каждый узел может иметь не более двух потомков. Очевидно, что каждая внутренняя вершина является корнем бинарного поддерева (левого или правого) своей родительской вершины.


На рисунке представлено бинарное дерево.


Ассоциативная связь


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


Для работы с бинарным деревом можно использовать следующую рекурсивную структуру:


Ассоциативная связь


В программе дерево представляется указателем на корень. Каждый узел помимо содержательной информации хранит указатель на правого и левого сына.


Ассоциативная связь


Основные операции для работы с бинарным деревом такие же, как и для работы со списком:

  • insert
  • remove
  • display


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


  1. Прямой порядок (нисходящий)
    • попасть в корень
    • пройти в прямом порядке левое поддерево
    • пройти в прямом порядке правое поддерево
  2. Симметричный порядок (последовательный)
    • пройти в симметричном порядке левое поддерево
    • попасть в корень
    • пройти в симметричном порядке правое поддерево
  3. Обратный порядок (восходящий)
    • пройти в обратном порядке левое поддерево
    • пройти в обратном порядке правое поддерево
    • попасть в корень


Многие задачи в информатике решаются с помощью разновидности бинарных деревьев – бинарных деревьев поиска, для которых выполняются следующие дополнительные условия:


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


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


Пример бинарного дерева поиска приведен на рисунке:


Ассоциативная связь


Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки.


Для реализации функций для работы с бинарным деревом поиска создадим проект. Описание структуры и объявления функций разместим в файле tree.h, а описания функций - в файле tree.c.


Ассоциативная связь


Новый элемент всегда будет вставляться как листовой узел дерева.


Ассоциативная связь


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


Ассоциативная связь


При реализации функции удаления узла необходимо, чтобы не нарушались свойства двоичного бинарного дерева поиска. Т.е. дерево должно оставаться бинарным и при этом для каждого узла все его левые потомки должны иметь меньшие ключевые значения, чем данный узел, а правые - большие. Этого можно добиться разными способами. Рассмотрим следующий алгоритм:

Пусть нам дано дерево, изображенное на рисунке.


Ассоциативная связь


Мы хотим удалить вершину с ключевым значением 20. Для этого мы ищем самый большой элемент среди ее левых потомков. Для нашего дерева это будет узел с ключевым значением 17. Очевидно, что у него нет правого потомка. Этот элемент мы помещаем на место удаляемого, а на его место передвигаем его левого потомка (поддерево с вершиной 15). Полученное в результате дерево представлено на следующем рисунке.


Ассоциативная связь


Ниже приведен листинг функции, реализующей рассмотренный алгоритм.


Ассоциативная связь