Как создать двоичное дерево в C

Как создать двоичное дерево в C. Двоичные деревья в C — это хороший способ динамической организации данных для удобного поиска. Однако для их обслуживания требуется много работы.

Создание двоичного дерева

Шаг 1

Структурируйте бинарное дерево. Каждому бинарному дереву потребуется структура, даже если оно имеет только одну переменную. Выберите имя, затем используйте typedef для его создания:typedef struct student_data STUDENT_DATA;

Шаг 2

Определите структуру. Включите два указателя на одну и ту же структуру:struct student_data { int student_ID; инт студент_класс; STUDENT_DATA слева, справа;};

Шаг 3

Выделите указатель на эту структуру данных, инициализировав ее значением NULL, чтобы она была головой дерева:STUDENT_DATA *students =NULL;

Добавить в двоичное дерево

Шаг 1

Выделите два временных указателя на структуру данных:STUDENT_DATA new_student, курс_студент;

Шаг 2

Используйте malloc() для создания нового элемента, всегда проверяя наличие ошибки:if ((new_student =malloc(sizeof(STUDENT_DATA))) ==NULL) { abort();

Шаг 3

Заполните поля нового элемента. Задайте для его левого и правого полей значение NULL:new_student->student_ID =newID;new_student->student_size =newsize;new_student->left =NULL;new_student->right =NULL;

Шаг 4

Рассмотрим переменную головы. Если переменная head имеет значение NULL, это первый элемент, добавленный в дерево, поэтому установите переменную head так, чтобы она указывала на него, и все готово:if (!students) { student =new_student; возвращаться;

Шаг 5

Начните с вершины дерева:cur_student =студенты; пока (cur_student) {

Шаг 6

Обработайте повторяющуюся запись, если новое значение и текущее значение равны:if (newID ==cur_student->student_ID) { abort();

Шаг 7

Работа с неравными значениями. Если новое значение меньше текущего значения, новый элемент идет слева. Добавьте его немедленно, если ничего не осталось. В противном случае пройдите влево и выполните цикл:if (newID student_ID) { if (cur_student->left ==NULL) { cur_student->left =newstudent; вернуть 1; } cur_student =cur_student->слева;

Шаг 8

Сделайте то же самое справа, иначе:} else { if (cur_student->right ==NULL) { cur_student->right =newstudent; вернуть 1; } cur_student =cur_student->право; }}

Поиск в двоичном дереве

Шаг 1

Создайте временную переменную, указывающую на структуру данных:STUDENT_DATA *cur_student;

Шаг 2

Установите временную переменную в переменную head:cur_student =student_head;

Шаг 3

Перебираем элементы, проверяя нужное значение:while (cur_student) { if (cur_student->student_ID ==15) { return cur_student->student_grade;

Шаг 4

Переход влево или вправо и цикл, если он не найден:if (cur_student->student_ID <15) { cur_student =cur_student->right; } else { cur_student =cur_student->left;

Шаг 5

Посмотрите, заканчивается ли петля. Если это так, значит, вы так и не нашли элемент:}return 0;

Очистить

Шаг 1

Освобождайте двоичное дерево, когда ваша программа завершает работу, так как не все операционные системы справятся с этим автоматически. Лучше всего это сделать с помощью рекурсивной функции:void Deallocate_binary_tree(STUDENT_DATA *tree) {

Шаг 2

Обратите внимание:если дерева нет, то и делать нечего:if (!tree) return;

Шаг 3

Рекурсивно освободить левое и правое поддеревья:Deallocate_binary_tree(tree->left); освободить_бинарное_дерево(дерево->справа);

Шаг 4

Освободите элемент, и все готово:free(tree);

Совет

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

Предупреждение

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