Программирование Тимур 0

Реализация бинарного дерева поиска в СИ

Реализация бинарного дерева поиска в СИ

Бинарное дерево поиска — это набор узлов, который удовлетворяет следующим условиям:

  1. Он может быть пустым.
  2. Либо обладает следующими элементами: корнем, правым и левым поддеревом.
  3. Ключи правого поддерева больше ключей левого поддерева.

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

Разновидности деревьев

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

Начало начал

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

Комментарии к коду
  • Используем typedef для создания нового типа, чтобы в дальнейшем не писать слово struct.
  • int key — ключ, может быть любого типа.
  • struct tree *left —  указатель на левое поддерево.
  • struct tree *right — указатель на правое поддерево.
  • struct tree *parent — указатель на родителя.
  • node — название структуры.

Инициализируем дерево

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

Добавим узел в дерево

Комментарии к коду
  • tmp -> left и tmp -> right имеют значение NULL, так как указатель tmp расположен в конце дерева.
  • Указатель root2 использовался для того, чтобы сохранить адрес на родителя вставляемого узла.
  • Мы не проверяем дерево на пустоту, так как ранее дерево был инициализировано (имеется корень).

Найдем нужный узел в дереве

Поиск в дереве реализовать очень просто. Как и раньше, мы будем руководствоваться следующим правилом: слева расположены элементы с меньшим значением ключа, справа — с большим.

Комментарий к коду

Данная функция рекурсивная, поэтому комментарий «Если дерево пусто или ключ корня равен искомому ключу, то возвращается указатель на корень» является не совсем верным, потому что root указывает на корень только во время первой итерации, далее root ссылается на другие узлы дерева, но из-за рекурсивности функции условие if ((root == NULL) || (root -> key = key)) будет проверяться всегда.

Найдем узел с минимальным и максимальным ключом

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

Удалим узел из дерева

Итак, пришло время освоить, наверное, самое сложное действие с деревом, а именно, удалить узел. Удаление элемента из дерева реализуется намного сложнее, чем в списках. Это связано с особенностью построения деревьев (см. начало статьи, пункт 3).

  1. Рассмотрим самый простой случай: у удаляемого узла нет левого и правого поддерева. В данной ситуации мы просто удаляем данный лист (узел).Реализация бинарного дерева поиска в СИ
  2. У удаляемого узла одно поддерево. В данной ситуации мы просто удаляем данный узел, а на его место ставим поддерево.
    Реализация бинарного дерева поиска в СИ

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

Общая функция поиска следующего за удаляемым элемента:

Комментарий к коду

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

Функция удаления узла из дерева:

Вывод элементов дерева

Реализация бинарного дерева поиска в СИ

Принято выделять три типа обхода дерева:

  1. Обход дерева в прямом порядке, будет напечатано A B D C E G F H J.
  2. Обход дерева в обратном порядке, будет напечатано D B G E H J F C A.
  3. Обход дерева в симметричном порядке, будет напечатано D B A E G C H F J

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

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Добавить комментарий

Вход
Apple Microsoft Google Samsung
  • Показать ещё
  • Сообщить об опечатке

    Текст, который будет отправлен нашим редакторам: