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

[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

[IUnknown]

Так. Давай уточним: тебе надо это дело просто сбалансировать один раз после того, как дерево было заполнено, или надо постоянно поддерживать его в сбалансированном виде (то есть, чтобы в любой момент высота левой/правой ветки не отличались больше, чем на 1)?

Просто тот алгоритм, ссылку на который я привел, подразумевает, что ему передаются уже упорядоченные данные. Если тебе надо однократно перебалансировать дерево, уже после создания обычного бинарного дерева поиска - то это возможно (тебе уже известно количество элементов, и сами элементы очень просто получить в упорядоченном виде). Если же надо при добавлении каждого элемента заниматься перестроениями - это уже не бинарное, а, скорее, AVL-дерево (информация есть здесь: http://volvo71.narod.ru/faq_folder/avl.htm , если надо - помогу написать его на чистом С)