Функция построения дерева поиска из файла - C (СИ)

Формулировка задачи:

Cколько не пытаюсь - не получается

#include <stdio.h>
#include <stdlib.h>
typedef struct NODE NODE;
typedef struct NODE *TREE;
 
struct NODE
{
    int key;
    int count;
    struct NODE *left;
    struct NODE *right;
}node;
 
TREE build_tree(int n, int tkey)
{
    TREE root = NULL;
    int nr, nl, i;
    if(n == 1)
        root = NULL;
 
    for(i = 1; i <= n; i++)
    {
        nl = n - 1;
        nr = n - nl - 1;
        root = (TREE)malloc(sizeof(node));
        root->key = tkey;
        root->left = build_tree(nl, tkey + 1);
        root->right = build_tree(nr, tkey + 1);
    }
    return root;
}
 
void print_tree(TREE tr, int h)
{
    int i;
    if(tr != NULL)
    {
        print_tree(tr->left, h + 1);
        for(i = 0; i < h; i++)
            printf("  ");
        printf("%d\n", tr->key);
        print_tree(tr->right, h + 1);
    }
}
 
int main()
{
    TREE tree;
    FILE *F;
    int a;
    if ((F=fopen("1.txt","r"))==NULL)
    {
        printf("fail F otkrit ne udalos!\n");
        exit(1);
    }
    while ((fscanf(F, "%d", &a)) == 1) {
        if (a){
    tree = build_tree(a, 1);
        }
        }
    print_tree(tree, 0);
 
    return 0;
}

Решение задачи: «Функция построения дерева поиска из файла»

Листинг программы

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
#define max(a, b) ( (a) > (b) ? (a) : (b) )
 
typedef struct NODE {
    int key;
    int count;
    int height;
    struct NODE * left;
    struct NODE * right;
} node_t;
 
node_t * node_new(const int key) {
    node_t * node = malloc(sizeof(node_t));
    if ( ! node )
        return NULL;
    
    node->key = key;
    node->count = 1;
    node->height = 1;
    node->left = NULL;
    node->right = NULL;
    
    return node;
}
 
void kill_tree(node_t * tree) {
    if ( tree ) {
        kill_tree(tree->left);
        kill_tree(tree->right);
        free(tree);
    }
}
 
int tree_height(node_t * tree) {
    return ( tree ) ? tree->height : 0;
}
 
int tree_bf(node_t * tree) {
    return tree_height(tree->right) - tree_height(tree->left);
}
 
void tree_fixheight(node_t * tree) {
    int lh, rh;
    
    assert( tree );
    lh = tree_height(tree->left);
    rh = tree_height(tree->right);
    
    tree->height = max(lh, rh) + 1;
}
 
node_t * rotate_right(node_t * n) {
    node_t * l;
    
    assert( n );
    l = n->left;
    assert( l );
    n->left = l->right;
    l->right = n;
    tree_fixheight(n);
    tree_fixheight(l);
    
    return l;
}
 
node_t * rotate_left(node_t * n) {
    node_t * r;
    
    assert( n );
    r = n->right;
    assert( r );
    n->right = r->left;
    r->left = n;
    tree_fixheight(n);
    tree_fixheight(r);
    
    return r;
}
 
node_t * tree_balance(node_t * tree) {
    assert( tree );
    
    tree_fixheight(tree);
    switch ( tree_bf(tree) ) {
        case 2 :
            if ( tree_bf(tree->right) < 0 )
                tree->right = rotate_right(tree->right);
            return rotate_left(tree);
        case -2 :
            if ( tree_bf(tree->left) > 0 )
                tree->left = rotate_left(tree->left);
            return rotate_right(tree);
        default:
            return tree;
    }
}
 
node_t * tree_insert(node_t * tree, const int key) {
    if ( ! tree )
        return node_new(key);
    else if ( tree->key == key ) {
        tree->count += 1;
        return tree;
    }
    else if ( tree->key > key )
        tree->left = tree_insert(tree->left, key);
    else
        tree->right = tree_insert(tree->right, key);
    
    return tree_balance(tree);
}
 
node_t * tree_from_file(const char * fileName) {
    FILE * f;
    node_t * tree = NULL;
    int n;
    
    if ( ! ( f = fopen(fileName, "r") ) )
        return NULL;
    
    while ( fscanf(f, "%d", &n) == 1 ) 
        tree = tree_insert(tree, n);
    
    fclose(f);
    return tree;
}
 
void tree_dump(node_t * tree, FILE * f) {
    if ( tree ) {
        int i;
        
        tree_dump(tree->left, f);
        for ( i = 0; i < tree->count; ++i )
            fprintf(f, "%d\n", tree->key);
        tree_dump(tree->right, f);
    }
}
 
int tree_to_file(node_t * tree, const char * fileName) {
    FILE * f = fopen(fileName, "w");
    if ( ! f )
        return -1;
    
    tree_dump(tree, f);
    
    return ( ferror(f) || fclose(f) );
}
 
#define INPUT_FILE_NAME "in.txt"
#define OUTPUT_FILE_NAME "out.txt"
 
int main(void) {
    node_t * tree = tree_from_file(INPUT_FILE_NAME);
    int ret = tree_to_file(tree, OUTPUT_FILE_NAME);
    kill_tree(tree);
    
    return ret;
}

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

Функция node_new создает новый узел дерева поиска с заданным ключом и инициализирует его значениями счетчика и высоты.
Функция kill_tree рекурсивно освобождает память, выделенную под узлы дерева, начиная с указанного узла.
Функция tree_height возвращает высоту поддерева, корнем которого является указанный узел.
Функция tree_bf вычисляет разницу в высотах поддеревьев, корнями которых являются левый и правый узлы указанного узла.
Функция tree_fixheight устанавливает высоту указанного узла равной максимальной высоте поддерева, корнями которого являются его левый и правый узлы.
Функция rotate_right выполняет поворот узла и его потомков вправо.
Функция rotate_left выполняет поворот узла и его потомков влево.
Функция tree_balance выполняет необходимые повороты для балансировки указанного узла.
Функция tree_insert рекурсивно добавляет новый узел с заданным ключом в указанное поддерево.
Функция tree_from_file создает дерево поиска из файла, содержащего набор целых чисел.
Функция tree_dump рекурсивно выводит содержимое указанного поддерева в файл.
Функция tree_to_file записывает дерево поиска в файл, преобразуя его в последовательность целых чисел.
В функции main создается дерево поиска из файла in.txt, а затем оно записывается в файл out.txt.