Форум программистов, компьютерный форум CyberForum.ru

Дерево: приоритет элемента - это - C++

Восстановить пароль Регистрация
 
Gudsaf
103 / 14 / 3
Регистрация: 29.11.2010
Сообщений: 325
22.05.2013, 22:39     Дерево: приоритет элемента - это #1
Парни сижу и не могу понять: стоит задача реализовать вставку элемента с определённым приоритетом в дерево и удаление элемента из дерева. Что за приоритет? Как его определить? Вот пример моего "листочка"
C++
1
2
3
4
5
6
7
struct leaf
{
    int val;
    leaf *parent;
    leaf *son_l;
    leaf *son_r;
};

Не по теме:

Мой код....

Кликните здесь для просмотра всего текста
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
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
#include <iostream>
#define EXIT_WHILE 7                            /// const for exit from infinite loop
/*! @struct leaf
    @brief  Struct for elements of tree.
    @param val      Value of leaf.
    @param *parent  Pointer to parent.
    @param *son_l   Pointer to left son.
    @param *son_r   Pointer to right son.
*/
struct leaf
{
    int val;
    int key;
    leaf *parent;
    leaf *son_l;
    leaf *son_r;
};
 
void delete_tree(leaf *root);
void create_tree(leaf *root);
int give_val();
int give_mFlag();
int give_cFlag(leaf *nowRoot);
leaf* up_root(leaf *root);
leaf* cr_left_son(leaf *parent);
leaf* cr_right_son(leaf *parent);
void inorder(leaf *root);
void preorder(leaf *root);
void postorder(leaf *root);
void print_tree(leaf* root);
 
 
int main ()
{
    short flag = 11;                            /// flag for menu
    leaf *root;                                 /// root of tree
 
    root = new leaf;
    root->parent = NULL;                        /// totaly null root of tree
    root->son_l = NULL;                         ///
    root->son_r = NULL;                         ///
    root->val = NULL;                           ///
    root->key = 1;                              ///
 
    while(1)
    {
        switch (give_mFlag())                   /// give flag
        {
        case 1: 
            create_tree(root);                  /// create tree
            printf("\n....tree was created");
            break;
        case 2:
            print_tree(root);                   /// print tree
            break;
        case 0:
            delete_tree(root);                  /// destroy tree 
            printf("\n....tree was destroied"); 
            flag = EXIT_WHILE;                  /// and exit from programm
            break;
        }
        if (flag == EXIT_WHILE) break;
    }
 
    getchar();
    getchar();
}
 
 
/*! @fn     int give_val()
    @brief  Give value of leaf.
    
    @return int val Value of leaf.
*/
int give_val()
{
    int val;
        printf ("....value of leaf: ");
        scanf("%d", &val);
    return val;
}
 
 
/*! @fn     int give_mFlag()
    @brief  Give value of command for main menu.
    
    @return int flag Value of command.
*/
int give_mFlag()
{
    int flag = 11;
        while (flag != 2 && flag != 1 && flag != 0)
        {
            printf ("\n# Create tree\t\t[input: 1]");
            printf ("\n# Print tree\t\t[input: 2]");
            printf ("\n# Destroy and exit\t[input: 0]");
            printf ("\n#\tCommand: ");  scanf("%d", &flag);
            printf(" ");
        }
    return flag;
}
 
 
/*! @fn     int give_cFlag(leaf *nowRoot)
    @brief  Give value of command for menu of creating tree.
            
            Using this function, the program understands what the user wants.
    @param  *nowRoot    A pointer to the leaf of the tree to which the program works
    @return int flag    Value of command.
*/
int give_cFlag(leaf *nowRoot)
{
    int flag = 11;
        while (flag != 3 && flag!=2 && flag != 1 && flag != 0)
        {
            printf ("\n# Add left leaf for\t(%d)\t[input: 1]",nowRoot->val);
            printf ("\n# Add right leaf for\t(%d)\t[input: 2]",nowRoot->val);
            if(nowRoot->parent == NULL)
                printf ("\n# Up to root\t\t(--)\t[No parent]");
            else
                printf ("\n# Up to root\t\t(%d)\t[input: 3]",nowRoot->parent->val);
            printf ("\n# Exit to main menu\t\t[input: 0]");
            printf ("\n#\tCommand: ");  scanf("%d", &flag);
        }
    return flag;
}
 
 
/*! @fn     leaf* up_root(leaf *root)
    @brief  Moves the user to a higher level
 
    @param  *root   A pointer to the leaf of the tree to which the program works
    @return leaf    root Adrees of this leaf in memory.
*/
leaf* up_root(leaf *root)
{
    if (root->parent)
    {
        printf("....now you at leaf \t(%d)\n", root->parent->val);
        return root->parent;
    }
    else
    {
        printf("....now you at leaf (%d), (%d) - ROOT of all tree!\n", root->val, root->val);
        return root;
    }
}
 
 
/*! @fn     leaf* cr_left_son(leaf *parent)
    @brief  Create left son for leaf.
 
    @param  *parent A pointer to the leaf of the tree to which the program works. 
                    For this leaf function create left son.
    @return tmpSon  Adrees of son in memory.
*/
leaf* cr_left_son(leaf *parent)
{
    leaf *tmpSon;
    tmpSon = new leaf;
        if (parent->son_l)                      /// if we already has son
        {
            delete tmpSon;
            printf ("....parent (%d) has left son (%d)", parent->val, parent->son_l->val);
            printf ("\n....return pointer to left son (%d)\n", parent->son_l->val);
            return parent->son_l;
        }
    parent->son_l = tmpSon;
    tmpSon->parent = parent;
    tmpSon->val = give_val();
    tmpSon->son_l = NULL;
    tmpSon->son_r = NULL;
    return tmpSon;
}
 
 
/*! @fn     leaf* cr_right_son(leaf *parent)
    @brief  Create right son for leaf.
 
    @param  *parent A pointer to the leaf of the tree to which the program works. 
                    For this leaf function create right son.
    @return tmpSon  Adrees of son in memory.
*/
leaf* cr_right_son(leaf *parent)
{
    leaf *tmpSon;
    tmpSon = new leaf;
        if (parent->son_r)                      /// if we already has son
        {
            delete tmpSon;
            printf ("....parent (%d) has right son (%d)", parent->val, parent->son_r->val);
            printf ("\n....return pointer to right son (%d)\n", parent->son_r->val);
            return parent->son_r;
        }
    tmpSon->val = give_val();
    tmpSon->parent = parent;
    tmpSon->son_l = NULL;
    tmpSon->son_r = NULL;
    parent->son_r= tmpSon;
    return tmpSon;
}
 
 
/*! @fn     void create_tree(leaf *root)
    @brief  Create tree.
 
            Whith help of simple fuctions this function create binar tree.
    @param  *root   A pointer to root of tree.
    @return void
*/
void create_tree(leaf *root)
{
    short flag = NULL;
    printf ("\nLet\'s create binar tree.");
    printf ("\n....Input value of root: ");
    scanf ("%d", &(root->val));
        while (1)
        {
            switch (give_cFlag(root))           /// give flag
            {
                case 1:
                    root = cr_left_son(root);   /// create left son
                    break;
                case 2:
                    root = cr_right_son(root);  /// create right son
                    break;
                case 3:
                    root = up_root(root);       /// go up to parent
                    break;
                case 0:
                    flag = EXIT_WHILE;          /// exit from create part
                    break;
                default:
                    ;
            }
            if (flag == EXIT_WHILE) break;
        }
}
 
 
/*! @fn     void inorder(leaf *root)
    @brief  Print tree in simmetric order.
 
    @param  *root   A pointer to root of tree.
    @return void
*/
void inorder(leaf *root)
{
    if(!root) return;
 
    inorder(root->son_l);
    if(root->val) printf("%d ", root->val);
    inorder(root->son_r);
}
 
 
/*! @fn     void preorder(leaf *root)
    @brief  Print tree in direct order.
 
    @param  *root   A pointer to root of tree.
    @return void
*/
void preorder(leaf *root)
{
    if(!root) return;
 
    if(root->val) printf("%d ", root->val);
    preorder(root->son_l);
    preorder(root->son_r);
}
 
 
/*! @fn     void postorder(leaf *root)
    @brief  Print tree in back order.
 
    @param  *root   A pointer to root of tree.
    @return void
*/
void postorder(leaf *root)
{
    if(!root) return;
 
    postorder(root->son_l);
    postorder(root->son_r);
    if(root->val) printf("%d ", root->val);
}
 
 
/*! @fn     void print_tree(leaf* root)
    @brief  Print tree in different order.
 
    @param  *root   A pointer to root of tree.
    @return void
*/
void print_tree(leaf* root)
{
    printf("\nPrinted tree:");
    printf("\nSimmetric order:\t");
    inorder(root);
    printf("\nDirect order:\t\t");
    preorder(root);
    printf("\nBack order:\t\t");
    postorder(root);
    printf("\n");
}
 
 
/*! @fn     void delete_tree(leaf *root)
    @brief  Delete tree.
 
    @param  *root   A pointer to root of tree.
    @return void
*/
void delete_tree(leaf *root)
{
    if(!root) return;
 
    delete_tree(root->son_l);
    delete_tree(root->son_r);
    if(root->val) 
    {
        printf("\n....destroy (%d)", root->val);
        delete root;
    }

Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.05.2013, 22:39     Дерево: приоритет элемента - это
Посмотрите здесь:

C++ Вставка элемента в дерево
Дерево поиска. добавление элемента C++
C++ Бинарное дерево, удаление элемента
Напишите программу, которая бы читала дерево в формате (а) и затем печатала бы это дерево в формате (б). C++
C++ Бинарное дерево (передать адрес первого (корневого) элемента дерева в метод)
Бинарное дерево поиска (удаление, добавление элемента) C++
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента. Вывести C++
Добавления элемента в бинарное дерево C++

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

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

Текущее время: 07:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru