Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
frm
0 / 0 / 0
Регистрация: 23.05.2010
Сообщений: 18
#1

Обход дерева - C++

30.05.2010, 17:59. Просмотров 1352. Ответов 2
Метки нет (Все метки)

Всем доброе время суток. Не могу нормально обойти дерево и просмотреть введённое, по всей видимости, возможно я неправильно поставил указатели. В общем помогите разобраться.
Конечно немного стыдно, ведь это можно в нете найти, но у мя голова не работает уже.

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
#include <iostream>
#include <stdio.h>
using namespace std;
 
#define sz 10
 
struct Item{
       int release;
       int string;
       Item *next;
       };
 
struct Node{
       int key;
       Item *info;
       Node *left, *right;
       };
       
char * Messages[] = {
     "1) View   \n",    
    "2) Input   \n"
};
 
int MessagesCount = sizeof(Messages) / sizeof(Messages[0]);     
 
int Menu() {        
    int answer = 1;
    do {
        for (int i = 0; i < MessagesCount; i++)
            cout << Messages[i];
        cout << "Please, select menu item: ";
        cin >> answer;
    } 
    while (answer < 1 || answer > MessagesCount);
    return answer % MessagesCount;
} 
 
 
 
void Insert(Node*&);
void View(Node*&);
    Insert,
    View
};
 
 
 
 
/*void findkey(Node *tree,Item *itm, int key) {
    if(tree->key==key) {
        Item *tmp = new Item;
        tmp->release=itm->release;
        strcpy(tmp->string,itm->string);
        tmp->next=NULL;
        tree->info->next=tmp;
        cout << "\nTako*y kluch suschestvuet";
        return;
    }
} */
 
void input(Node** tree,Item *itm,int key) {
     if (*tree==NULL) {
        *tree=new Node;
     if (*tree!=NULL) {
                      (*tree)->key=key;    
                      (*tree)->info=itm;
                      (*tree)->left=NULL;
                      (*tree)->right=NULL;
                      }
                      }
     else
         if(key < (*tree)->key) 
                              input(&((*tree)->left), itm, key);
                              else
         if(key > (*tree)->key) 
                              input(&((*tree)->right), itm, key);
                              }
                      
     
 
void View(Node*& tree) {
     if(tree == NULL) 
             cout << "\nTree is NULL" << endl;
     if (tree != NULL) {
     cout<<tree->key <<"\t" ;
     View(tree->left);
     View(tree->right);
         }  }                    
 
 
Item *CreateItem(int release, int str)
{
    Item *item = new Item;
    item->release = release;
    item->string = str;
    //item->string = new char[strlen(str) + 1];
    //strcpy(item->string, str);
    item->next = NULL;
    return item;
}
 
 
 
void Insert(Node *&tree) 
{
    Item *itm=NULL;
    int key;
    int release;
    int aa;
    char string[80];
    cout << "\nVvedite key    : "; cin >> key;
  cout << "\nVvedite release: "; cin >> release;
    cout << "\nVvedite string : "; cin >> aa;
    itm=CreateItem(release,aa);
    input((&tree),itm,key); 
  cout << tree->key << endl;    
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
            
    Node *tree=NULL;
                
    for(;;) {
    int answer = 1;
    do {                            
        answer = Menu();
        func[answer](tree); 
//      cout << tree->key;
    } while (answer);
}
    return 0;
}
Item *CteateItem(int , char *);
Добавлено через 3 часа 37 минут
всё ок, разобрался

Добавлено через 16 часов 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
#include <iostream>
#include <stdio.h>
using namespace std;
 
#define sz 10
 
struct Item{
       int release;
       char *string;
       Item *next;
       };
 
struct Node{
       int key;
       Item *info;
       Node *left, *right;
       };
       
char * Messages[] = {
     "\n2) View \n",    
    "3) Input   \n",        
    "1) Delete  \n",        
            
    //"5) Exit  \n"         
};
 
int MessagesCount = sizeof(Messages) / sizeof(Messages[0]);     
 
int Menu() {        
    int answer = 1;
    do {
        for (int i = 0; i < MessagesCount; i++)
            cout << Messages[i];
        cout << "Please, select menu item: ";
        cin >> answer;
    } 
    while (answer < 1 || answer > MessagesCount);
    return answer % MessagesCount;
} 
 
 
 
void Insert(Node*&);                            
void Delete(Node*&);            
void View(Node*&);              
//void Quit(Node*);             
 
Item *CreateItem(int , char *);
 
void (*func[])(Node*&) = {      
//  Quit,
    Insert,
    Delete,
    View
};
 
 
/*Node unitDel(Node *tree) {
     Node *tmp=new Node;
     tmp=tree;*/
     
     
//ÑîçäГ*Г*ГЁГҐ ýëåìåГ*ГІГ*     
Item *CreateItem(int release, char *str)
{
    Item *item = new Item;
    item->release = release;
    item->string = new char[strlen(str) + 1];
    strcpy(item->string, str);
    item->next = NULL;
    return item;
}
 
//ÑîçäГ*Г*ГЁГҐ óçëГ*
void input(Node** tree,Item *itm,int key) {
     if (*tree==NULL) {
        *tree=new Node;
        (*tree)->key=key;    
        (*tree)->info=itm;
        (*tree)->left=NULL;
        (*tree)->right=NULL;
        }
     else
         if(key < (*tree)->key) 
                              input(&((*tree)->left), itm, key);
                              else
         if(key > (*tree)->key) 
                              input(&((*tree)->right), itm, key);
                              }
 
Item *appItem(Item *itm,int release, char *str) {
     if ((itm->next))
     appItem(itm->next,release,str);
     else 
     itm->next=CreateItem(release,str);
     }
     
//Ïîèñê óçëГ* ГЇГ® êëþ÷ó    
int findkey(Node *tree,int key,int release, char *str) {
    if(tree!=NULL) {
           if((tree)->key==key) {
                              appItem(tree->info,release,str); 
/*                    while(tree->info) {
                            if((tree->info->next)) {
                             tree->info=tree->info->next; }
                            else {    
                   (tree)->info->next=CreateItem(release,str);} }  
                   //(tree)->info=(tree)->info->next;*/
                   return 1;
                   } 
                
    if (tree->key!=key) {
     findkey(((tree)->left),key,release,str);
     findkey(((tree)->right),key,release,str);
     } }
     return 0;
} 
 
int findkeyThenDel(Node *tree,int key) {
    if(tree!=NULL) {
           if((tree)->key==key) {
                          //Node *tmp=new Node;
                          //Item *itm=new Item;
                          //itm=*&(tree->info);
                          //tmp->right=tree->right;
                          //tmp->left=tree->left;
                          delete *&(tree->info);
                           delete &*tree;
                          // free(itm);
//                          delete tmp;      
                   return 1;
                   } 
                
    if ((tree)->key!=key) {
     findkeyThenDel(((tree)->left),key);
     findkeyThenDel(((tree)->right),key);
     } }
     return 0;
}
 
 
Item *viewItem(Item *itm) {
     for(;;) {
                      cout<<"\t" << itm->release << "\t" << itm->string 
                      << endl;
                      itm=itm->next;
                      if(!(itm)) break;
                      } }                      
     
 
void treeView(Node*& tree) {
 
     if (tree != NULL) {
     cout<<tree->key ;
     viewItem(tree->info);
     // endl ;
     treeView(tree->left);
     treeView(tree->right);
         } 
         else return; }      
                       
void View(Node*& tree) {
     cout << "key\t" << "Release\t" << "String" << endl;   
     treeView(tree);
     }
 
 
 
 
void Insert(Node *&tree) 
{
    Item *itm=NULL;
    int key;
    int release;
    int aa;
    char string[80];
    cout << "\nVvedite key    : "; cin >> key;
    cout << "\nVvedite release: "; cin >> release;
    cout << "\nVvedite string : "; cin >> string;
    itm=CreateItem(release,string);
    if (findkey(tree,key,release,string)) return;
    input((&tree),itm,key); 
}
 
void Delete(Node *&tree) {
     int key;
     cout << "\nInser key for del : ";
     cin >> key; cout <<endl;
     if(findkeyThenDel(tree,key)) 
     cout << "node deleted" << endl;
     else
     cout << "No key in tree" << endl;
     }
     
int main()
{
    setlocale(LC_ALL, "Russian");
            
    Node *tree=NULL;
                
    for(;;) {
    int answer = 1;
    do {                            
        answer = Menu();
        func[answer](tree); 
    } while (answer);
}
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.05.2010, 17:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Обход дерева (C++):

Обход дерева - C++
Вот начал читать про деревья и способы их обхода (PreOrder, InOrder и PostOrder). С алгоритмами проблем нет, но видно, как бы это сказать...

обход дерева - C++
struct SAcson { int l,c; // строка, столбец float x; // заряд bool e; // возбуждающий или тормозящий }; struct SSinapc { ...

обход дерева - C++
Здравствуйте! У меня вопрос: Есть класс: class D { vector &lt;A*&gt; count; }; ...

Обход дерева) - C++
Прога работает) но сказали, что нужно сделать отдельную функцию обхода дерева) можете помочь) или пример)) #include &lt;iostream.h&gt; ...

Обход дерева Хаффмана - C++
Добрый вечер. Имеем кодовое дерево Хаффмана.(в изображении) До каждого узла данного дерева есть путь из 0 и 1 . Для узла 12 ,...

Обход произвольного дерева - C++
struct tree { char info; struct tree *left; struct tree *right; }; так, вопрос глупый -меня просто сомнения берут. вот...

2
SashaPinsk
39 / 37 / 2
Регистрация: 27.12.2009
Сообщений: 73
31.05.2010, 01:07 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void mydelete(int number, tree **root)
{
    int buffer;
    if(!*root)
    {
        printf("\nТакого элемента в дереве нет...");
        getch();
        return;
    }
    buffer=(*root)->number-number;
    if(buffer>0) mydelete(number, &(*root)->left);
    else if(buffer==0) 
         {
            tree *left, *right;
            left=(*root)->left;
            right=(*root)->right;
            free(*root);
            *root=right;
            while(*root) root=&(*root)->left;
            *root=left;
         }
         else mydelete(number, &(*root)->right);
}
1
frm
0 / 0 / 0
Регистрация: 23.05.2010
Сообщений: 18
31.05.2010, 09:55  [ТС] #3
Спасиб конечно, но я уже разобрался ))). Осталась проблема с балансировкой дерева.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.05.2010, 09:55
Привет! Вот еще темы с ответами:

Обход дерева в ширину - C++
имеется такой кусок программы. требуется обойти дерево в ширину. библиотека #include &lt;queue&gt; подключена void...

Обход бинарного дерева - C++
может есть у кого такой пример или похожий??или часть какая нибудь?

Обход дерева в ширину - C++
Кто нибудь может скинуть мне программу обхода дерева в ширину?

Обход n-арного дерева - C++
вопрос какой алгоритм использовать в плане КАК? знаю как хранить и как обходить, но алгоритм Лево Корень Право, а тут распечатывать...


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

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

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