Двоичные деревья, СИ, Помогите с балансировкой, пожалуйста! Опции

[Eichhorn]

Язык СИ, пишу на dev cpp.
Задача:
Реализовать программу, сохраняющую числа из входного файла в двоичном дереве. Имя файла приходит как аргумент командной строки. Числа необходимо хранить в сбалансированом дереве двоичного поиска. После построения дерева вывести его содержимое на экран в порядке возрастания.

Пример:
input.txt
48 1 0 29

Вывод:
0 1 29 48

Код

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
    struct tree *pred;
};

struct tree * create(int data) {

    struct tree *p = (struct tree*)calloc(1,sizeof(struct tree));
    p->data=data;    
    p->left=NULL;
    p->right=NULL;
    return p;        
}

struct tree *add_tree(struct tree * head,int data) {
    struct tree *a = head;

    if(head==NULL){
        head=create(data);
        return head;
    }

    while(1) {
        if(a->data < data) {
            if(!a->right) {
                a->right = create(data);
                break;
            }
            a = a->right;
        } else {
            if(!a->left) {
                a->left = create(data);
                break;
            }
            a = a->left;
        }
    }


    return head;
}

int depth_tree(struct tree *head) {
if(head) {
  return 1 + depth_tree(head->left) + depth_tree(head->right);
}
return 0;
}

void print_tree(struct tree *tree) {
    if(tree==NULL){
        return;
    }

    print_tree(tree->left);
    printf("%i\n",tree->data);
    print_tree(tree->right);

}

void balance_tree(){
    
}

int main() {
    int n=0;
    int g=0;
    struct tree* head = NULL;    

    FILE * f=fopen("file.txt","r");

    
        if(f==0){
            printf("%s","Fail ne otkrit\n");
            return -1;
        }
    while(!feof(f)){
        g=fscanf(f,"%d",&n);
        head = add_tree(head,n);
        if(g!=1){
            printf("%s","fail pust\n");
        
            return -1;
        }        
    }
    
    print_tree(head);
    printf("depth is %i\n",depth_tree(head));
    getch();
    return 0;
}

Здесь просто вывод дерева. А как сделать балансировку?

Сообщение отредактировано: Eichhorn - 25.11.2011 15:51

[Eichhorn]

У меня сейчас есть такой код:

Код

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
    int balance; //-1, 0, 1
};

struct tree * create(int data) {

    struct tree *p = (struct tree*)calloc(1,sizeof(struct tree));
    p->data=data;    
    p->left=NULL;
    p->right=NULL;

    return p;        
}

struct tree * small_RR(struct tree *a){
    struct tree *b = a->right;
    struct tree *c = b->right;
    a->right = b ->left;
    b->left=a;
    a->balance = 0;
    b->balance = 0;
    return b;    
}

struct tree * big_RR(struct tree *a){
    struct tree *b = a -> right;
    struct tree *c = b -> left;
    b -> left = c->right;
    c -> right = b;
    a -> right = c;
    a=small_RR(a);

    return a;
}

struct tree * small_LR(struct tree *a){
    struct tree *b = a->left;
    struct tree *c = b->left;
    a->left = b ->right;
    b->right=a;
    a->balance = 0;
    b->balance = 0;
    return b;    
}

struct tree * big_LR(struct tree *a){
    struct tree *b = a -> left;
    struct tree *c = b -> right;
    b -> right = c->left;
    c -> left = b;
    a -> left = c;
    a=small_RR(a);

    return a;
}

int add_tree(struct tree ** head,int data) {
    struct tree *a = *head;
    if(a==NULL){
        *head = create(data);
        return 1;
    }
    if(a->data < data) {
        int changed = add_tree(&(a->right),data);

        if(!changed)
        return 0;

        if(a -> balance == -1){
            a -> balance ++;
            return 0;
        }    

        if(a -> balance == 0){
            a -> balance ++;
            return 1;
        }

        if(a -> balance == 1){
            struct tree *b;
            a -> balance ++;
             b = a -> right;
            if(b -> balance == 1){
                *head = small_RR(a);
            }
            if(b -> balance == -1)
                *head = big_RR(a);
        }
    
    }

    else {
        int changed = add_tree(&(a->left),data);

        if(!changed)
        return 0;

        if(a -> balance == 1){
            a -> balance --;
            return 0;
        }

        if(a -> balance == 0){
            a -> balance --;
            return 1;
        }

        if(a -> balance == -1){
            struct tree *b;
            a -> balance --;

            b = a -> left;

            if(b -> balance == -1){
                *head = small_LR(a);
            }

            if(b -> balance == 1)
                *head = big_LR(a);
            
        }

    }

}


int depth_tree(struct tree *head) {
    if(head) {
        return 1 + maxx(depth_tree(head->left), depth_tree(head->right));

    }
    return 0;
}

int maxx(int a, int b){
    if(a>b)
    return a;
    return b;
}

void print_tree(struct tree *tree) {
    if(tree==NULL){
        return;
    }

    print_tree(tree->left);
    printf("%i\n",tree->data);
    print_tree(tree->right);
}

void dump_tree(struct tree * t) {
    if(t->left) {
        printf("(");
        dump_tree(t->left);
        printf(")");
    }
    printf("%d", t->data);
    if(t->right) {
        printf("(");
        dump_tree(t->right);
        printf(")");
    }
}

void balance_tree(){

}

int main() {
    int n=0;
    int g=0;
    struct tree* head = NULL;    

    FILE * f=fopen("input.txt","r");


    if(f==0){
        printf("%s","Fail ne otkrit\n");
        return -1;
    }
    while(!feof(f)){
        g=fscanf(f,"%d",&n);
        add_tree(&head,n);
        if(g!=1){
            printf("%s","fail pust\n");

            return -1;
        }        
    }

    dump_tree(head);
    printf("depth is %i\n",depth_tree(head));

    getch();
    return 0;
}

Но нам сказали, что эта программа не совсем корректно работает. Балансировку не правильно считает.