Найти все элементы дерева, что принадлежат отрезку - 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;
}

Объяснение кода листинга программы

  1. Структура узла дерева (node_t) содержит целочисленное значение, количество элементов в поддереве (count) и указатели на левое и правое поддеревья (left и right).
  2. Функция print_node выводит все элементы в узле (поскольку count всегда равно 1 в этом коде).
  3. Функция print_tree рекурсивно выводит все элементы в дереве.
  4. Функция print_bounded_nodes выводит только те элементы в дереве, значение которых находится в заданном диапазоне.
  5. Функция add_value добавляет новый элемент в дерево, используя принцип разделяй и властвуй.
  6. Функция kill_tree освобождает память, выделенную для всех узлов в дереве.
  7. В main сначала добавляются некоторые значения в дерево, затем выводятся все элементы в дереве, после чего пользователю предлагается ввести два числа (min и max), чтобы вывести только элементы, находящиеся в заданном диапазоне.
  8. После того, как пользователь вводит min и max, выводится сообщение, а затем программа завершается.

Оцени полезность:

11   голосов , оценка 3.818 из 5
Похожие ответы