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

[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 19:51

[IUnknown]

Но это уже не совсем бинарные деревья. У тебя изменена struct tree (добавлено новое поле balance). Если надо именно с бинарными - то:

Много кода (Показать/Скрыть)

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

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

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;
}

/*
   Это добавляет новый элемент к бинарному дереву,
   не изменял, то что было то и осталось, только
   переформатировалось (у меня AStyle настроен на другой
   стиль)
*/
struct tree *add_tree(struct tree * head, int data)
{
    struct tree *a = head;

    if(!head)
    {
        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;
    */

    if(head)
    {
        int l_d = depth_tree(head->left);
        int r_d = depth_tree(head->right);
        return 1 + (l_d > r_d ? l_d : r_d);
    }
    return 0;
}

/*
   Здесь я сделал 2 разных функции для вывода деревьев по одной
   простой причине: чтобы вывести в отсортированном порядке узлы
   обычного бинарного дерева - надо обходить его в *симметричном*
   порядке:
   (Левое поддерево - Корень - Правое поддерево).

   Для того же, чтобы вывести упорядоченные узлы сбалансированного
   дерева, надо его обойти в *прямом* порядке:
   (Корень - Левое поддерево - Правое поддерево).
*/
void print_tree(struct tree *root)
{
    if(!root) return;

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

void print_balanced_tree(struct tree *root)
{
    if(!root) return;

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

/* Это будет удалять любое дерево */
void delete_tree(struct tree *root)
{
    if(!root) return;

    delete_tree(root->left);
    delete_tree(root->right);
}

/* Здесь я записываю всё содержимое бинарного дерева,
   упорядоченное по возрастанию, в буфер, чтобы потом
   оттуда заполнять дерево сбалансированное. Обход -
   симметричный.
*/
void buff_tree(struct tree *root, int *items, int *curr)
{
    if(!root) return;

    buff_tree(root->left, items, curr);

    items[*curr] = root->data;
    (*curr) += 1;

    buff_tree(root->right, items, curr);
}

/* Да, я знаю, что глобальные переменные - зло, но так будет проще */
int curr_item;

/*
   Собственно, эта функция и создает сбалансированное дерево, получая
   количество элементов и сами элементы.
*/
void create_balanced_tree(int n_items, int *items, struct tree **root)
{
    struct tree *new_node;
    int x, n_left, n_right;

    new_node = *root;
    if(!n_items)
        *root = NULL;
    else
    {
        n_left = n_items / 2;
        n_right = n_items - n_left - 1;
        x = items[curr_item++];
        new_node = create(x);
        create_balanced_tree(n_left, items, &((*new_node).left));
        create_balanced_tree(n_right, items, &((*new_node).right));
        *root = new_node;
    }
};

/*
   А это - подготовительная функция. Как только у нас есть дерево,
   которое надо сбалансировать - мы
   1) удаляем старое сбалансированное дерево
   2) заполняем динамически выделенный буфер упорядоченными
   значениями узлов бинарного дерева
   3) вызываем функцию построения сбалансированного дерева
*/
struct tree *create_balanced(struct tree *prev_balanced,
                             struct tree *unbalanced, int length)
{
    int curr = 0;
    struct tree *bt = NULL;

    if(prev_balanced)
    {
        delete_tree(prev_balanced);
    }

    int *buff = (int*)malloc(length * sizeof(int));
    buff_tree(unbalanced, buff, &curr);

    curr_item = 0;
    create_balanced_tree(length, buff, &bt);

    return bt;
}


int main()
{
    int n = 0;
    int g = 0;
    int n_count = 0;
    /* Это - указатель на обычное дерево */
    struct tree* head = NULL;
    /* Это - указатель на сбалансированное дерево */
    struct tree* b_tree = NULL;

    FILE *f = fopen("file.txt", "r");
    if(!f)
    {
        printf("%s\n","Fail ne otkrit");
        return -1;
    }

    while(!feof(f))
    {
        g = fscanf(f, "%d", &n);
        head = add_tree(head,n);
        n_count += 1;

        if(g != 1)
        {
            printf("%s\n","fail pust");
            return -1;
        }
        b_tree = create_balanced(b_tree, head, n_count);
    }

    printf("\nUnbalanced:\n");
    print_tree(head);

    printf("\nBalanced:\n");
    print_balanced_tree(b_tree);

    printf("unbalanced depth is %i\n",depth_tree(head));
    printf("balanced depth is %i\n",depth_tree(b_tree));

    /* Не забудь удалить деревья, чтоб не было утечек */
    getch();

    return 0;
}

file.txt

48 1 0 29 2 6 4 9 5

Вывод:

Unbalanced:
0
1
2
4
5
6
9
29
48

Balanced:
0
1
2
4
5
6
9
29
48
unbalanced depth is 7
balanced depth is 4

Сообщение отредактировано: IUnknown - 26.11.2011 21:37