Создать бинарное дерево с типом узлов enum - C (СИ)
Формулировка задачи:
нужно создать бинарное дерево с типом узов enum
как будет выглядить структура и создание такого дерева?
Решение задачи: «Создать бинарное дерево с типом узлов enum»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> enum item { ITEM1, ITEM2, ITEM3 }; struct node { enum item item; struct node* left; struct node* right; }; struct bin_tree { struct node* root; }; void init(struct bin_tree*); void insert(struct bin_tree*, enum item); int member(const struct bin_tree*, enum item); void destroy(struct bin_tree*); #define TEST(EXPR) printf(#EXPR ": %s\n", ((EXPR) != 0 ? "true" : "false")) int main(void) { enum item items[] = {ITEM2, ITEM1, ITEM2}; size_t i; struct bin_tree tree; init(&tree); for(i = 0; i < sizeof(items) / sizeof(*items); ++i) insert(&tree, items[i]); TEST(member(&tree, ITEM1)); TEST(member(&tree, ITEM2)); TEST(member(&tree, ITEM3)); destroy(&tree); exit(0); } void init(struct bin_tree* tree) { tree->root = NULL; } struct node* insert_node(struct node* node, enum item item) { if(node == NULL) { node = malloc(sizeof(struct node)); node->left = node->right = NULL; node->item = item; } else if(item < node->item) node->left = insert_node(node->left, item); else if(item > node->item) node->right = insert_node(node->right, item); return node; } void insert(struct bin_tree* tree, enum item item) { tree->root = insert_node(tree->root, item); } int member_node(const struct node* node, enum item item) { if(node == NULL) return 0; if(item < node->item) return member_node(node->left, item); if(item > node->item) return member_node(node->right, item); return 1; } int member(const struct bin_tree* tree, enum item item) { return member_node(tree->root, item); } void destroy_node(struct node* node) { if(node != NULL) { destroy_node(node->left); destroy_node(node->right); free(node); } } void destroy(struct bin_tree* tree) { destroy_node(tree->root); tree->root = NULL; }
Объяснение кода листинга программы
В данном коде реализована реализация двоичного дерева с использованием enum для определения типа узла. Список действий, которые происходят в коде:
- #include
Указывает компилятору включить в программу функции файла стандартного ввода/вывода. - #include
Указывает компилятору включить в программу функции файла стандартного ввода/вывода и malloc. - enum item Определяет перечисление (enum) с тремя значениями.
- struct node Определяет структуру узла с полями: enum item item; struct node left; struct node right.
- struct bin_tree Определяет структуру связного списка с полем root.
- *void init(struct bin_tree)** Инициализирует связный список пустым.
- struct node insert_node(struct node node, enum item item) Рекурсивная функция для вставки нового узла в дерево. Если узел пуст, то создается новый узел, иначе рекурсивно вызывается функция для левого или правого поддерева в зависимости от значения enum.
- *void insert(struct bin_tree, enum item item)** Вставляет новый узел в корень дерева.
- *int member_node(const struct node node, enum item item)** Рекурсивная функция для проверки наличия enum в поддереве, начиная с указанного узла.
- *int member(const struct bin_tree, enum item item)** Проверяет наличие enum в дереве.
- *void destroy_node(struct node node)** Рекурсивная функция для удаления узла и всех его потомков.
- *void destroy(struct bin_tree tree)** Удаляет все узлы дерева.
- int main(void) Главная функция программы.
- enum item items[] = {ITEM2, ITEM1, ITEM2}; Массив для тестовых значений enum.
- size_t i; Переменная для итерации по массиву.
- struct bin_tree tree; Создание связного списка для хранения дерева.
- init(&tree); Инициализация связного списка.
- *for(i = 0; i < sizeof(items) / sizeof(items); ++i)** Цикл для добавления всех тестовых значений enum в дерево.
- TEST(member(&tree, ITEM1)); Вывод результата проверки наличия первого тестового значения enum в дереве.
- TEST(member(&tree, ITEM2)); Вывод результата проверки наличия второго тестового значения enum в дереве.
- TEST(member(&tree, ITEM3)); Вывод результата проверки наличия третьего тестового значения enum в дереве.
- destroy(&tree); Удаление всех узлов дерева.
- exit(0); Завершение программы.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д