Двоичные деревья, СИ, Помогите с балансировкой, пожалуйста! |
1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!
Двоичные деревья, СИ, Помогите с балансировкой, пожалуйста! |
Eichhorn |
25.11.2011 15:48
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 50 Пол: Женский Реальное имя: Сафиуллина Алёна Репутация: 1 |
Язык СИ, пишу на 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 |
25.11.2011 18:48
Сообщение
#2
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
|
Eichhorn |
25.11.2011 19:51
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 50 Пол: Женский Реальное имя: Сафиуллина Алёна Репутация: 1 |
Что-то никак не могу понять как это делается... Половину из того, что там написано в тексте программы не знаю...
-------------------- Жизнь похожа на собачью упряжку: если не идёшь впереди, то всё время видишь одно и то же...
|
IUnknown |
25.11.2011 23:06
Сообщение
#4
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Так. Давай уточним: тебе надо это дело просто сбалансировать один раз после того, как дерево было заполнено, или надо постоянно поддерживать его в сбалансированном виде (то есть, чтобы в любой момент высота левой/правой ветки не отличались больше, чем на 1)?
Просто тот алгоритм, ссылку на который я привел, подразумевает, что ему передаются уже упорядоченные данные. Если тебе надо однократно перебалансировать дерево, уже после создания обычного бинарного дерева поиска - то это возможно (тебе уже известно количество элементов, и сами элементы очень просто получить в упорядоченном виде). Если же надо при добавлении каждого элемента заниматься перестроениями - это уже не бинарное, а, скорее, AVL-дерево (информация есть здесь: http://volvo71.narod.ru/faq_folder/avl.htm , если надо - помогу написать его на чистом С) |
Гость |
26.11.2011 5:15
Сообщение
#5
|
Гость |
Нам нужно бинарное дерево, чтобы в любой момент высота не отличалась более, чем на 1.
|
IUnknown |
26.11.2011 11:54
Сообщение
#6
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Значит, надо будет после каждого добавления элемента полностью перестраивать дерево, другого варианта просто не существует. Очень неэффективный метод, надо сказать: дерево из 10 элементов будет создаваться 11 раз (один раз - то самое, несбалансированное, которое есть у тебя, и еще 10 раз будет создаваться/удаляться новое дерево, в котором высоты почти равны). Чуть позже покажу, как это сделать...
|
Eichhorn |
26.11.2011 17:08
Сообщение
#7
|
Пионер Группа: Пользователи Сообщений: 50 Пол: Женский Реальное имя: Сафиуллина Алёна Репутация: 1 |
У меня сейчас есть такой код:
Код #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; } Но нам сказали, что эта программа не совсем корректно работает. Балансировку не правильно считает. -------------------- Жизнь похожа на собачью упряжку: если не идёшь впереди, то всё время видишь одно и то же...
|
IUnknown |
26.11.2011 17:30
Сообщение
#8
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Но это уже не совсем бинарные деревья. У тебя изменена struct tree (добавлено новое поле balance). Если надо именно с бинарными - то:
Много кода (Показать/Скрыть)
file.txt Цитата 48 1 0 29 2 6 4 9 5 Вывод: Unbalanced: Сообщение отредактировано: IUnknown - 26.11.2011 17:37 |
Eichhorn |
28.11.2011 17:31
Сообщение
#9
|
Пионер Группа: Пользователи Сообщений: 50 Пол: Женский Реальное имя: Сафиуллина Алёна Репутация: 1 |
Спасибо за ещё один вариант решения. Но, возвращаясь к моей проге... Нам преподаватель сказал заменить строку
Код printf("%d",tree->data); на Код printf("%d",tree->balance); в функции dump_tree.При этом баланс неправильно выводится. Например при числах 5 1 8 7 6 9 10 балансировку делает правильно, но в некоторых местах пишет, что баланс равен 2, хотя он по определению либо 1, либо -1, либо 0. Сообщение отредактировано: Eichhorn - 28.11.2011 17:32 Эскизы прикрепленных изображений -------------------- Жизнь похожа на собачью упряжку: если не идёшь впереди, то всё время видишь одно и то же...
|
IUnknown |
28.11.2011 18:56
Сообщение
#10
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата хотя он по определению либо 1, либо -1, либо 0. По определению - это конечно, хорошо, но... Смотри на момент отладки:Как думаешь что произойдет? При выходе из функции чему будет равен a->balance, учитывая, что b->balance равен 0? Чуть ниже есть такой же момент с a->balance, но в другую сторону, в (-2), то есть, теоретически, при некотором стечении обстоятельств, баланс может быть и (+2) и (-2). Надо добавить еще одну ветку, что делать, если b->balance == 0 |
Eichhorn |
29.11.2011 17:12
Сообщение
#11
|
Пионер Группа: Пользователи Сообщений: 50 Пол: Женский Реальное имя: Сафиуллина Алёна Репутация: 1 |
Что-то я никак не могу придумать... В голову пришло только
Код if(b -> balance == 0){ a -> balance --; } и Код if(b -> balance == 0){ a -> balance ++; } -------------------- Жизнь похожа на собачью упряжку: если не идёшь впереди, то всё время видишь одно и то же...
|
IUnknown |
29.11.2011 17:39
Сообщение
#12
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
А если сделать вот так:
if(a -> balance == 1){(понимаешь идею да? Всё равно баланс отрицательный или положительный, зачем еще усиливать), то произойдет чудо, и вывод из вот такого ((1(0))-1(0))1((0)2((0)1((0)0((0)0(0)))))depth is 6 станет таким: ((1(0))-1(0))0(((0)0(0))0((0)0((0)0(0))))depth is 5 (тестировалось на данных "5 1 8 7 6 9 10 17 3 12 22 25 14 31") Почему это? |
Eichhorn |
3.12.2011 7:03
Сообщение
#13
|
Пионер Группа: Пользователи Сообщений: 50 Пол: Женский Реальное имя: Сафиуллина Алёна Репутация: 1 |
Спасибо!
Сообщение отредактировано: Eichhorn - 3.12.2011 7:17 -------------------- Жизнь похожа на собачью упряжку: если не идёшь впереди, то всё время видишь одно и то же...
|
Текстовая версия | 28.09.2024 20:45 |