Найти все элементы дерева, что принадлежат отрезку - C (СИ)
Формулировка задачи:
При решении задачи использовать динамическую структуру бинарного дерева поиска.
Найти все елементы дерева ,что пренадлежат отрезку [a,b] ,где a ,b -данные числа.
Решение задачи: «Найти все элементы дерева, что принадлежат отрезку»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <time.h> typedef struct NODE { int value; size_t count; struct NODE * left; struct NODE * right; } node_t, * tree_t; void print_node(const node_t * pNode) { size_t i; for ( i = 0; i < pNode->count; ++i ) printf("%d ", pNode->value); } void print_tree(const tree_t tree) { if ( tree ) { print_tree(tree->left); print_node(tree); print_tree(tree->right); } } void print_bounded_nodes(const tree_t tree, const int min, const int max) { if ( tree ) { if ( tree->value > min ) print_bounded_nodes(tree->left, min, max); if ( tree->value >= min && tree->value <= max ) print_node(tree); if ( tree->value < max ) print_bounded_nodes(tree->right, min, max); } } void add_value(tree_t * pTree, const int value) { if ( ! *pTree ) { assert ( *pTree = malloc(sizeof(node_t)) ); (*pTree)->value = value; (*pTree)->count = 1; (*pTree)->left = NULL; (*pTree)->right = NULL; } else { if ( (*pTree)->value > value ) add_value(&((*pTree)->left), value); else if ( (*pTree)->value < value ) add_value(&((*pTree)->right), value); else (*pTree)->count += 1; } } void kill_tree(tree_t * pTree) { if ( *pTree ) { kill_tree(&((*pTree)->left)); kill_tree(&((*pTree)->right)); free(*pTree); *pTree = NULL; } } #define VALUES_COUNT (20) #define TOP_VALUE (100) int main(void) { tree_t tree = NULL; int i, min, max; node_t * pNode; srand(time(NULL)); printf("Values to tree:\n"); for ( i = 0; i < VALUES_COUNT; ++i ) { min = rand() % TOP_VALUE; printf("%d ", min); add_value(&tree, min); } printf("\nValues in tree:\n"); print_tree(tree); while ( printf("\nSpace separated min and max: ") && scanf("%d %d", &min, &max) == 2 ) print_bounded_nodes(tree, min, max); printf("\n"); kill_tree(&tree); return 0; }
Объяснение кода листинга программы
- Структура узла дерева (node_t) содержит целочисленное значение, количество элементов в поддереве (count) и указатели на левое и правое поддеревья (left и right).
- Функция print_node выводит все элементы в узле (поскольку count всегда равно 1 в этом коде).
- Функция print_tree рекурсивно выводит все элементы в дереве.
- Функция print_bounded_nodes выводит только те элементы в дереве, значение которых находится в заданном диапазоне.
- Функция add_value добавляет новый элемент в дерево, используя принцип
разделяй и властвуй
. - Функция kill_tree освобождает память, выделенную для всех узлов в дереве.
- В main сначала добавляются некоторые значения в дерево, затем выводятся все элементы в дереве, после чего пользователю предлагается ввести два числа (min и max), чтобы вывести только элементы, находящиеся в заданном диапазоне.
- После того, как пользователь вводит min и max, выводится сообщение, а затем программа завершается.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д