Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
xxscs
0 / 0 / 0
Регистрация: 22.05.2015
Сообщений: 6
1

Динамические структуры данных: деревья

26.06.2015, 12:19. Просмотров 834. Ответов 1
Метки нет (Все метки)

Задание

Составить программу на языке Си для построения и обработки дерева общего вида или упорядочного двоичного дерева, содержащего узлы целого типа. После того как дерево создано с ним можно выполнять следующие действия:

Добавление нового узла (для двоичного дерева положение нового узла определяется в соответствии с требованием сохранения порядка, для дерева общего вида должен задаваться путь до добавляемого узла, добавляемый узел становится младшим сыном).
Текстовая визуализация дерева (значение каждого узла выводится на отдельной строке, с отступом пропорциональным глубине узла (шаг отступа --- 2 пробела), в порядке старшинства узлов).
Удаление узла (двоичное дерево перестраивается в соответствии с требованием сохранения целостности и порядка; для дерева общего вида удаляется все поддерево, исходящее из удаляемого узла; 4. должно быть предусмотрено корректное освобождение памяти). вычисление значения некоторой функции от дерева (целой или логической) в соответствии с номером варианта.
Определения

Глубиной вершины дерева называется длина пути в эту вершину из корня.
Глубиной (высотой) дерева называется максимальная глубина его вершин.
Листом или терминальной вершиной дерева называется вершина, не имеющая поддеревьев.
Степенью вершины называется число исходящих из нее ветвей.
Степенью дерева называется максимальная степень его вершин.
Шириной уровня дерева называется число вершин на данной глубине.
Шириной дерева называется максимальная ширина по всем уровням.
Подобие деревьев отличается от равенства возможным несовпадением значений в данных, хранящихся в узлах.
AVL-деревом называется двоичное дерево, в котором высоты левого и правого поддеревьев отличаются не более, чем на 1.
Двоичное дерево называется B-деревом, если в нем нет ни одного узла степени 1
Входные данные

На стандартный ввод программе подаются команды четырех типов:

p — печать дерева;
+ 2 (или +ssbb 2) — вставка в дерево (для дерева общего вида путь задается строкой, где r создание корня, s --- переход к старшему сыну, b --- переход к брату);
- 5 — удаление из дерева элемента со значением 5 (удаление первого найденного при обходе элемента со значением 5 и его поддерева);
t [params] — выполнение заданного вариантом действия. Параметры, если они есть, перечислены через пробел.

Выходные данные

После чтения и выполнения каждой команды программа должна вывести результат операции.

Распечатать дерево (для пустого дерева вывести «Empty»).
Вывести сообщение «OK» в случае успеха (если элемент уже есть в двоичном дереве, вывести «Exists», если в дереве общего вина не существует указанного пути, вывести «Error»).
Вывести сообщение «OK» при успешном удалении или «Not found», если элемента с таким значением в дереве нет.
Вывести вычисленное значение (для логических значений выводить true или false).
Определить число листьев дерева.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.06.2015, 12:19
Ответы с готовыми решениями:

Задача на Указатели и динамические структуры данных
Дана задача: Записи содержат фамилию, год рождения. Добавлять новые записи так,...

Загвоздка с деревом, динамические структуры данных
Всем доброго времени суток. Столкнулся с такой проблемой. В языке С новичок и...

Динамические структуры данных. Ошибки в функциях
Как я понял я запутался в указателях на типы данных при объявлении, или вызове...

Динамические структуры данных. Создание списков
Собственно задание: В проекте создать однонаправленный список. Разбить список...

Динамические структуры
#include <stdio.h> #include <locale.h> #include <stdlib.h> #include...

1
Геомеханик
790 / 596 / 938
Регистрация: 26.06.2015
Сообщений: 1,409
28.06.2015, 14:28 2
Лучший ответ Сообщение было отмечено xxscs как решение

Решение

Вот тебе двоичное дерево(BST) поиска для начала.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
 
typedef struct tree {
    struct tree* left;
    struct tree* right;
    int    val;
} bstree;
 
int  bstree_add(bstree** tr, int val);
void bstree_remove(bstree** tr, int val);
void bstree_print(FILE* hout, const bstree* tr);
void bstree_clear(bstree* tr);
 
 
int main(void){
    int     i;
    bstree* tr = NULL;
 
    for(i = 0; i < 30; ++i)
        bstree_add(&tr, rand() % 10);
 
    //вывести 
    bstree_print(stdout, tr);
 
    //удалить
    bstree_remove(&tr, 1);
    bstree_remove(&tr, 4);
    bstree_remove(&tr, 9);
    bstree_remove(&tr, 6);
 
    putchar('\n');
    bstree_print(stdout, tr);
    bstree_clear(tr);
    return 0;
}
 
 
//добавление элемента в bst-дерево
int bstree_add(bstree** tr, int val){
    bstree* ptr = *tr;
 
    while(ptr != NULL){
        if(val == ptr->val)
            return 0;
        else if(val < ptr->val){
            tr  = &ptr->left;
            ptr = ptr->left;
        } else {
            tr  = &ptr->right;
            ptr = ptr->right;
        }
    }
 
    ptr = (bstree*)malloc(sizeof(bstree));
    if(ptr == NULL)
        return 0;
 
    ptr->left = ptr->right = NULL;
    ptr->val  = val;
    *tr = ptr;
    return 1;
}
 
//удаление элемента из дерева
void bstree_remove(bstree** tr, int val){
    bstree*  ptr1, *iter, *ptr2;
 
    for(iter = *tr; iter != NULL;){
        if(val == iter->val)
            break;
        else if(val < iter->val) {
            tr   = &iter->left;
            iter = iter->left;
        } else {
            tr   = &iter->right;
            iter = iter->right;
        }
    }
 
    if(iter == NULL)
        return;
 
    if(iter->right == NULL)
        *tr = iter->left; 
    else {
        ptr2 = iter->right;
        if(ptr2->left == NULL) { 
            ptr2->left = iter->left;  
            *tr = ptr2;
        } else {
            ptr1 = ptr2->left; 
            while(ptr1->left != NULL){
                ptr2 = ptr1;
                ptr1 = ptr2->left;
            }
            ptr2->left  = ptr1->right;
            ptr1->left  = iter->left;
            ptr1->right = iter->right;
            *tr = ptr1;
        }
    }
    free(iter);
}
 
//проход по-возрастанию
void bstree_print(FILE* hout, const bstree* tr){
    if(tr != NULL){
        bstree_print(hout, tr->left);
        fprintf(hout, "%d ", tr->val);
        bstree_print(hout, tr->right);
    }
}
 
//удаление всего дерева
void bstree_clear(bstree* tr){
    if(tr != NULL){
        bstree_clear(tr->left);
        bstree_clear(tr->right);
        free(tr);
    }
}
Результат работы кода
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.06.2015, 14:28

Динамические структуры ошибка
#include &quot;stdafx.h&quot; #include &quot;stdio.h&quot; #include &quot;conio.h&quot; #include...

Переписать программу под динамические структуры
Люди нужны ваши навыки !!=) Вот эта программа рекурсии, она рабочая, а мне...

Динамические структуры: проверить баланс круглых скобок в тексте
Доброе время суток.Помогите пожалуйста с след. заданием. Условие: Дан...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru