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

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

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

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

30.05.2010, 17:59. Просмотров 1236. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.05.2010, 17:59     Обход дерева
Посмотрите здесь:

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

Ускорить обход дерева - C++
Во входном файле ancestor.in в первой строке содержится количество узлов дерева, во второй строке массив чисел i-ое из которых определяет...

Нерекурсивный обход дерева - C++
я не могу понять как сделать не рекурсивный обход дерева. понятно что надо добавлять элементы куда-то.в стек например. но я не знаю как...

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

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

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

Симметрический обход дерева - C++
Кто знает - симметрический обход дерева - это тоже самое что и сортировка? Получается так.

Обход дерева по образцу - C++
Помогите осуществить обход дерева по образцу.

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

Рекурсивный обход НЕбинарного дерева - C++
Имеется функция, которая рекурсивно обходит одну папку. void GetFileList(LPTSTR sPath, Object* fsParser) { WIN32_FIND_DATA...

Обход нагруженного дерева (бора) - C++
Здравствуйте,прошу помощи в объяснении как сделать обход такого дерева. В итоге должно вывести на екран: cat,car,it,is,all. В каждого узла...

Бинарное Дерево(обход дерева) - C++
добрый вечер всем!) в универе задали написать бинарное дерево со всеми видами обхода и т.п. я их написал.. но еще дали 1 вывод его надо...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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);
}
frm
0 / 0 / 0
Регистрация: 23.05.2010
Сообщений: 18
31.05.2010, 09:55  [ТС]     Обход дерева #3
Спасиб конечно, но я уже разобрался ))). Осталась проблема с балансировкой дерева.
Yandex
Объявления
31.05.2010, 09:55     Обход дерева
Ответ Создать тему
Опции темы

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