Найти все элементы дерева, что принадлежат отрезку - 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, выводится сообщение, а затем программа завершается.