Язык СИ, пишу на dev cpp. Задача: Реализовать программу, сохраняющую числа из входного файла в двоичном дереве. Имя файла приходит как аргумент командной строки. Числа необходимо хранить в сбалансированом дереве двоичного поиска. После построения дерева вывести его содержимое на экран в порядке возрастания.
Что-то никак не могу понять как это делается... Половину из того, что там написано в тексте программы не знаю...
IUnknown
26.11.2011 3:06
Так. Давай уточним: тебе надо это дело просто сбалансировать один раз после того, как дерево было заполнено, или надо постоянно поддерживать его в сбалансированном виде (то есть, чтобы в любой момент высота левой/правой ветки не отличались больше, чем на 1)?
Просто тот алгоритм, ссылку на который я привел, подразумевает, что ему передаются уже упорядоченные данные. Если тебе надо однократно перебалансировать дерево, уже после создания обычного бинарного дерева поиска - то это возможно (тебе уже известно количество элементов, и сами элементы очень просто получить в упорядоченном виде). Если же надо при добавлении каждого элемента заниматься перестроениями - это уже не бинарное, а, скорее, AVL-дерево (информация есть здесь: http://volvo71.narod.ru/faq_folder/avl.htm , если надо - помогу написать его на чистом С)
Гость
26.11.2011 9:15
Нам нужно бинарное дерево, чтобы в любой момент высота не отличалась более, чем на 1.
IUnknown
26.11.2011 15:54
Значит, надо будет после каждого добавления элемента полностью перестраивать дерево, другого варианта просто не существует. Очень неэффективный метод, надо сказать: дерево из 10 элементов будет создаваться 11 раз (один раз - то самое, несбалансированное, которое есть у тебя, и еще 10 раз будет создаваться/удаляться новое дерево, в котором высоты почти равны). Чуть позже покажу, как это сделать...
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);
/* Это добавляет новый элемент к бинарному дереву, не изменял, то что было то и осталось, только переформатировалось (у меня AStyle настроен на другой стиль) */ struct tree *add_tree(struct tree * head, int data) { struct tree *a = head;
/* Здесь я сделал 2 разных функции для вывода деревьев по одной простой причине: чтобы вывести в отсортированном порядке узлы обычного бинарного дерева - надо обходить его в *симметричном* порядке: (Левое поддерево - Корень - Правое поддерево).
Для того же, чтобы вывести упорядоченные узлы сбалансированного дерева, надо его обойти в *прямом* порядке: (Корень - Левое поддерево - Правое поддерево). */ void print_tree(struct tree *root) { if(!root) return;
/* Здесь я записываю всё содержимое бинарного дерева, упорядоченное по возрастанию, в буфер, чтобы потом оттуда заполнять дерево сбалансированное. Обход - симметричный. */ 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;
/* А это - подготовительная функция. Как только у нас есть дерево, которое надо сбалансировать - мы 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);
int main() { int n = 0; int g = 0; int n_count = 0; /* Это - указатель на обычное дерево */ struct tree* head = NULL; /* Это - указатель на сбалансированное дерево */ struct tree* b_tree = NULL;
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
Eichhorn
28.11.2011 21:31
Спасибо за ещё один вариант решения. Но, возвращаясь к моей проге... Нам преподаватель сказал заменить строку
Код
printf("%d",tree->data);
на
Код
printf("%d",tree->balance);
в функции dump_tree. При этом баланс неправильно выводится. Например при числах 5 1 8 7 6 9 10 балансировку делает правильно, но в некоторых местах пишет, что баланс равен 2, хотя он по определению либо 1, либо -1, либо 0.
Как думаешь что произойдет? При выходе из функции чему будет равен a->balance, учитывая, что b->balance равен 0? Чуть ниже есть такой же момент с a->balance, но в другую сторону, в (-2), то есть, теоретически, при некотором стечении обстоятельств, баланс может быть и (+2) и (-2).
Надо добавить еще одну ветку, что делать, если b->balance == 0
Eichhorn
29.11.2011 21:12
Что-то я никак не могу придумать... В голову пришло только
Код
if(b -> balance == 0){ a -> balance --; }
и
Код
if(b -> balance == 0){ a -> balance ++; }
IUnknown
29.11.2011 21:39
А если сделать вот так:
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); }
// ...
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); }
(понимаешь идею да? Всё равно баланс отрицательный или положительный, зачем еще усиливать), то произойдет чудо, и вывод из вот такого
((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 11:03
Спасибо!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.