Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Roulen
9 / 1 / 3
Регистрация: 15.06.2016
Сообщений: 224
1

Построение бинарного дерева

21.05.2018, 10:52. Просмотров 210. Ответов 0
Метки нет (Все метки)

Собственного проблема стала на построении идеально сбалансированного дерева.
Есть сортированный массив структуры листов, необходимо распределить листы в ветви.

Пытаюсь делать так:
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
struct library {
    unsigned int UDK : 10; // 929 max
    char author[40];
    char name[40];
    unsigned int year : 11; // 2018 max  - MAKE SYS TIME
    unsigned int copies : 27; // 100 000 000 max 
    library *left = NULL;
    library *right = NULL;
};
 
void MakeTree(library *books, int number, int current) {
 
    int root = current / 2 + 0.01, left = root + (current - root) / 2, right = root - (current - root) / 2;
    //if (root - left)
    if (root != 0 && number != root) {
        //cout << "root  = " << root << endl;
        //cout << "left  = " << left << endl;
        //cout << "right = " << right << endl;
        (books + root)->left = (books + left);
        (books + root)->right = (books + right);
        MakeTree(books, number, left);
        MakeTree(books, number, right);
    }
    else {
        if (root == 0) books->left = NULL;
        else if (root == number) books->right = NULL;
    }
}
Тестирую на 15 элементах.
Первый элемент 8-й, возьму первый треугольник 4<-8->12 , отлично. Далее смотрю треугольник от 12, получаю
11<-12->13. В сторону 13 сформировал верно, в сторону 11 - ветки расположены подобающе, но 10 он просто выкинул.
Не могу найти тут ошибку...

Добавлено через 2 часа 30 минут
То что написал - бред.
Задача актуальна...
Есть отсортированный массив, из него нужно собрать бинарное дерево поиска.

Добавлено через 35 секунд
На данный момент хорошо хожу только в лево...

C++
1
2
3
4
5
6
7
8
9
10
11
12
Tree(books, number, double(number) / 2. + 0.6);
 
void Tree(library *books, int number, int now) {
    int left = double(now) / 2., right = double(now) + double(now) / 2.0;
    if (left != 0 && right != number) {
        cout << "number= " << number << endl;
        cout << "root  = " << now << endl;
        cout << "left  = " << left << endl;
        cout << "right = " << right << endl;
        Tree(books, left, double(now) / 2. + 0.6);
    }
}
Добавлено через 55 минут
никто не поможет?
Весь интернет перерыл, казалось бы, из сортированного массива связи никто не делал...

Добавлено через 37 минут
Кину на всякий весь код, что сейчас имею. Решил что следует получить глубину и двигаться от нее, больше ничего не придумал...
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
#pragma warning(disable:4996)
#include <iostream>
#include <string>
#include <cctype> // for isalpha
using namespace std;
 
 
struct library {
    unsigned int UDK : 10; // 929 max
    char author[40];
    char name[40];
    unsigned int year : 11; // 2018 max  - MAKE SYS TIME
    unsigned int copies : 27; // 100 000 000 max 
    library *left = NULL;
    library *right = NULL;
};
 
FILE *file;
 
void print(string text);
int GetNum(string path);
int GetPrioriry();
void GetData(library *data, string path, int number);
void sort(library *data, int number, int priority);
int Deep(library *books, int number, int now, int n);
 
int main() {
    // declaring start instructions
    setlocale(LC_ALL, "Russian");
    cout << endl;
    print("Please, write data path");
    cout << "Path : ";
    string path;
    cin >> path;
 
    // get books number
    int number = GetNum(path);
 
    fclose(file);
    // get data
    library *books = new library[number], *uk = books;
    int priority = GetPrioriry(); // get sort priority
    GetData(books, path, number);
    //sort(books, number, priority);
 
    // sort data
    sort(books, number / 2, priority);
 
    // create tree
 
 
    //for (int k = 0; k < number; k++) {
    //  cout << k << " | UDK = " << (books + k)->UDK << " | Author = " << (books + k)->author << " | Name = " << (books + k)->name << " | Year = " << (books + k)->year << " | Books = " << (books + k)->copies << endl;
    //}
 
    cout << Deep(books, number, double(number) / 2. + 0.6, 0) << endl;
 
    /*for (int k = 0; k < number; k++) {
    cout << "UDK   = " << (books+k)->UDK << endl;
    cout << "self  = " << books + k << endl;
    cout << "left  = " << (books + k)->left << endl;
    cout << "right = " << (books + k)->right << endl;
    cout << endl;
    }*/
 
    system("pause");
    return 0;
}
 
 
int GetNum(string path) {
    library book;
    file = fopen(path.c_str(), "r+b");
    int number = -1;
    while (!feof(file)) {
        fread(&book, sizeof(library), 1, file);
        number++;
    }
    fclose(file);
    return number;
}
 
// format text
void print(string text) {
    cout << "\t\t\t" << text << endl << "\t\t\t";
    for (int i = 0; i < text.length(); i++) cout << '-';
    cout << endl;
}
 
 
// return sort priority
int GetPrioriry() {
    int priority = -1;
    while (priority < 0 || priority > 5) {
        print("Please, write sort priority");
        cout << "1 - UDK" << endl;
        cout << "2 - Author" << endl;
        cout << "3 - Book name" << endl;
        cout << "4 - Release date" << endl;
        cout << "5 - Number of book copies" << endl;
        cout << "-------------------------" << endl;
        cout << "Priority : ";
        cin >> priority;
    }
    return priority;
}
 
// include data
void GetData(library *data, string path, int number) {
    FILE *file;
    file = fopen(path.c_str(), "r+b");
    fread(data, sizeof(library), number, file);
    fclose(file);
}
 
// sort data
void sort(library *data, int number, int priority) {
    library save;
    int good = number - 1;
    switch (priority)
    {
    case 1:
        while (good != 0) {
            good = number - 1;
            for (int k = 0; k < number - 1; k++) {
                if ((data + k)->UDK < (data + k + 1)->UDK) {
                    save = *(data + k);
                    *(data + k) = *(data + k + 1);
                    *(data + k + 1) = save;
                }
                else (good--);
            }
        }
        good = number - 1;
        break;
    case 2:
        while (good != 0) {
            good = number - 1;
            for (int k = 0; k < number - 1; k++) {
                if (string((data + k)->author) < string((data + k + 1)->author)) {
                    save = *(data + k);
                    *(data + k) = *(data + k + 1);
                    *(data + k + 1) = save;
                }
                else (good--);
            }
        }
        good = number - 1;
        break;
    case 3:
        while (good != 0) {
            good = number - 1;
            for (int k = 0; k < number - 1; k++) {
                if (string((data + k)->name) < string((data + k + 1)->name)) {
                    save = *(data + k);
                    *(data + k) = *(data + k + 1);
                    *(data + k + 1) = save;
                }
                else (good--);
            }
        }
        good = number - 1;
        break;
    case 4:
        while (good != 0) {
            good = number - 1;
            for (int k = 0; k < number - 1; k++) {
                if ((data + k)->year < (data + k + 1)->year) {
                    save = *(data + k);
                    *(data + k) = *(data + k + 1);
                    *(data + k + 1) = save;
                }
                else (good--);
            }
        }
        good = number - 1;
        break;
    case 5:
        while (good != 0) {
            good = number - 1;
            for (int k = 0; k < number - 1; k++) {
                if ((data + k)->copies < (data + k + 1)->copies) {
                    save = *(data + k);
                    *(data + k) = *(data + k + 1);
                    *(data + k + 1) = save;
                }
                else (good--);
            }
        }
        good = number - 1;
        break;
    default:
        break;
    }
}
 
// get tree deep
int Deep(library *books, int number, int now, int n) {
    int left = double(now) / 2., right = double(now) + double(now) / 2.0;
    if (left != 0 && right != number) {
        n = Deep(books, left, double(now) / 2. + 0.6, n+1);
    }
    return n;
}
 
void GetTree(library *books, int number, int now, int n) {
    //???
}
 
 
/*
// debug text
cout << endl << "number= " << number << endl;
cout << "root  = " << now << endl;
cout << "left  = " << left << endl;
cout << "right = " << right << endl;
 
// create test data file
file = fopen(path.c_str(), "wb");
library book1 = { 1, "Bogorad O.A.", "Full stack developing", 2018 ,1 };
library book2 = { 2, "Hockens J.V.", "Way of my life", 2011 ,323 };
library book3 = { 3, "Boggy F.F.", "Boggy's job", 2015, 123 };
library book4 = { 4, "Roylad A.F.", "Best cars ever", 2018, 4221 };
library book5 = { 5, "Vesered O.E.", "Malware software", 2017, 5 };
library book6 = { 6, "Hello W.D.", "Hello world!", 2013, 171 };
library book7 = { 7, "Bye W.D.", "Bye, Bye word!", 2013, 19 };
fwrite(&book1, sizeof(library), 1, file);
fwrite(&book2, sizeof(library), 1, file);
fwrite(&book3, sizeof(library), 1, file);
fwrite(&book4, sizeof(library), 1, file);
fwrite(&book5, sizeof(library), 1, file);
fwrite(&book6, sizeof(library), 1, file);
fwrite(&book7, sizeof(library), 1, file);
fclose(file);*/
Добавлено через 8 часов 18 минут
UP..

Добавлено через 46 минут
Вымучал...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
GetTree(books, number / 2. + 0.6, number / 2. + 0.6, Deep(books, number, double(number) / 2. + 0.6, 0));
 
//            ук. на массив , текущий эл. , гл. родитель, глубина
void GetTree(library *books, int number, int root, int n) {
    n--;
    if (n > -1) {
        int left = number - pow(2, n), right = number + pow(2, n);
        if (number < root) {
            (books + number - 1)->right = books + left - 1;
            (books + number - 1)->left = books + right - 1;
        }
        else {
            (books + number - 1)->left = books + left - 1;
            (books + number - 1)->right = books + right - 1;
        }
        GetTree(books, right, root, n);
        GetTree(books, left, root, n);
    }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.05.2018, 10:52
Ответы с готовыми решениями:

Построение бинарного дерева на основе не бинарного
В лабораторной работе есть такое задание: Создайте процедуру построения...

Построение бинарного дерева
Написать программу построения бинарного дерева с помощью связных структур и...

Построение бинарного дерева
Доброй ночи! Пятые сутки не могу разобрать реализацию алгоритма на С++ Console...

Построение бинарного дерева из строки
Доброго времени суток, уважаемые. Хотел бы спросить у вас спросить совета...

Построение бинарного дерева. Где ошибка?
Насколько понял, tree-&gt;left, tree-&gt;right указывает на NULL. Почему, не могу...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.05.2018, 10:52

Построение бинарного дерева из двумерного массива
Стыдно, если честно, об этом просить, но &quot;возник стопор&quot; и путных идей не...

Код Хаффмана реализованный через построение бинарного дерева
Здравствуйте, есть код Хаффмана реализованный через построение бинарного...

Запись бинарного дерева в файл и восстановление из него этого дерева
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя...


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

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

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