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

Нерекурсивный обход дерева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.86
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
11.12.2010, 16:04     Нерекурсивный обход дерева #1
я не могу понять как сделать не рекурсивный обход дерева.
понятно что надо добавлять элементы куда-то.в стек например.
но я не знаю как в смысле по какому правилу и т.п.
как обойти все элементы дерева добавляя их в стек без рекурсии?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2010, 16:04     Нерекурсивный обход дерева
Посмотрите здесь:

C++ Обход произвольного дерева
НЕрекурсивный обход бинарного дерева C++
Обход дерева C++
Обход дерева) C++
Обход дерева C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
12.12.2010, 09:47     Нерекурсивный обход дерева #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
struct node {
    int val;
    node *left,*right;
    node(int v, node *l,node *r):val(v),left(l),right(r) {}
};
void foo(node *t)
{
    std::stack<node*> s;
    s.push(NULL);
    node *tt = t;
    do {
        if (tt != NULL) {
            s.push(tt);
            std::cout << tt->val << '\n';
            tt = tt->left;
        } else {
            if (s.top() == NULL) break;
            tt = s.top();
            s.pop();
            tt = tt->right;
        }
    } while (true);
}
чего-то типа того.
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
12.12.2010, 13:23  [ТС]     Нерекурсивный обход дерева #3
то есть если я правильно понял то
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
do
    {
        if (dr != NULL) 
            {
                 stack *elem=new stack;
                 elem->val=dr;
                 if (st==0)
                    {
                    st=elem;
                    st->next=0;
                    }
                     else
                   {
                      elem->next=st;//áûâøГ*Гї ãîëîâГ* Г±ГІГ*Г*ГҐГІ âòîðûì ýëåìåГ*òîì
                      st=elem;
                    }
                    cout << dr->val <<" ";
                    dr = dr->left;
            }  
            else 
            {               
                 if (st == NULL) break;//åñëè Г±ГІГҐГЄ ГЇГіГ±ГІ
                 dr = st;
                 stack *temp;
                 temp=st;
                 st=st->next;
                 delete temp;
                 dr = dr->right;
            }
    }while(true);
так?
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
12.12.2010, 14:16     Нерекурсивный обход дерева #4
вот это:
Цитата Сообщение от Artishok Посмотреть сообщение
elem->val=dr;
в 6 строке, что такое? dr вроде указатель на узел дерева, чего его присваивать значению узла... надо составить всю программу и откомпилировать, тогда яснее будет, а так вроде правильно.
я, кстати, рабочий вариант написал, чем он не понравился?
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
12.12.2010, 14:32  [ТС]     Нерекурсивный обход дерева #5
Цитата Сообщение от Aye Aye Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct node {
    int val;
    node *left,*right;
    node(int v, node *l,node *r):val(v),left(l),right(r) {}
};
void foo(node *t)
{
    std::stack<node*> s;
    s.push(NULL);
    node *tt = t;
    do {
        if (tt != NULL) {
            s.push(tt);
            std::cout << tt->val << '\n';
            tt = tt->left;
        } else {
            if (s.top() == NULL) break;
            tt = s.top();
            s.pop();
            tt = tt->right;
        }
    } while (true);
}
чего-то типа того.
как изменить для правого обхода
я изменил tt->left на tt->right а tt->left но это ничего не изменило
и кстати я правильно перебил из stl в свои функции?
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
12.12.2010, 15:59     Нерекурсивный обход дерева #6
кажется перебил правильно, но стек на односвязном списке обычно организовывается немножко удобнее, нужно определить класс:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MySteck{
    struct list_node*{
        list_node *next;
        int value;
        list_node(list_node *l, int v);
    };
    list_node *head;
    int sz; // количество узлов в списке
public:
    void push(int x);
    void pop();
    void top();
    bool empty();
    int size();
};
просто так намного понятнее и можно хорошо протестировать стек отдельно от непосредственного использования.
Цитата Сообщение от Artishok Посмотреть сообщение
я изменил tt->left на tt->right а tt->left но это ничего не изменило
не может быть, чтобы это ничего не изменило, смотри внимательнее. Может где-нибудь опечатался, или забыл поменять... ну если написано tt = tt->right; как обход может в другую сторону пойти!? нрипиши там везде вывод содержимого узлов на экран, чтобы было видно точно куда идет обход. Может твоя процедура заполнения дерева заполняет его не в том порядке, в каком ты думаешь. Сначала распечатай дерево обычно процедурой:
C++
1
2
3
4
5
6
7
8
9
void print(node *t,int n)
{
    if (t != NULL) {
        print(t->right,n+1);
        for (int i = 0; i < n) std::cout << "  ";
        std::cout << t->val << '\n';
        print(t->left,n+1);
    }
}
и убедись, что дерево именно такое, каким ты его себе представляешь.
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
12.12.2010, 21:00  [ТС]     Нерекурсивный обход дерева #7
вывожу через рекурсию.
C++
1
2
3
4
5
6
7
8
void print_tree(uzel *root)//âûâåñòè äåðåâî
{
 if (root == 0) 
    return;
   print_tree(root->right);
   cout<<root->key<<" ";
   print_tree(root->left);
}
АлександрШ
 Аватар для АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
12.12.2010, 21:30     Нерекурсивный обход дерева #8
Сильно не вникал о чем вы, увидел что требуется обход, вот держи может поможет. тут все обходы и правильно работают.
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
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
 
 
using namespace std;
 
 
 
//описание стэка
 
template<class telem> class stack
{
    telem *x;
    int top;
    int n;
public:
    stack(int size);
   ~stack(){delete x;}
   void push(telem y);
   telem pop();
   int emptry()
   {
       if (top==0) return 1;
       else return 0;
   }
};
 
template<class telem> stack<telem>::stack(int size)
{
    x = new telem [size];
    if(!x)
    {
    cout << "невозможно создать стек \n"; exit (1);
    }
    n = size;
    top =0;
}
 
template<class telem>void stack<telem>::push(telem y)
{
    if (top==n)
      {
          cout<<"стэк заполнен \n";return;
      }
    x[top]=y;
    top++;
}
 
template<class telem>telem stack<telem>::pop()
{
    if(top==0)
    {
    cout<< "Стек пуст\n";
    return 0;
    }
    top--;
    return x[top];
}
 
//postroenie dereva
 
template<class DataT> class tree
{
    DataT info;
    tree*llink;
    tree *rlink;
public:
    tree *root;
    tree(){root=NULL;};
    void in(tree<DataT> *&t);
    void btree1(tree<DataT> *t);
    void btree2(tree<DataT> *t);
    void btree3(tree<DataT> *t);
    void btree4(tree<DataT> *t);
    void btree5(tree<DataT> *t);
    void btree6(tree<DataT> *t);
 
};
 
template<class DataT>void tree<DataT>::in(tree<DataT> *&t)
{
    DataT c;
    cin>>c;
    if(c!='.')
    {
        t=new tree<DataT>;
        t->info=c;
        in(t->llink);
        in(t->rlink);
    }else{
        t=NULL;
    }
 
}
 
 
//рекурсивная реализация обхода в обратном порядке
template<class DataT>void tree<DataT>::btree1(tree<DataT> *t)
{
    if(t!=NULL)
    {
    btree1(t->llink);
    cout<<t->info;
    btree1(t->rlink);
    }
}
 
//рекурсивная реализация обхода в прямом порядке
template<class DataT>void tree<DataT>::btree2(tree<DataT> *t)
{
    if(t!=NULL)
    {
        cout<<t->info;
    btree2(t->llink);
        btree2(t->rlink);
    }
}
 
//рекурсивная реалзация обхода в концевом порядке
template<class DataT>void tree<DataT>::btree3(tree<DataT> *t)
{
    if(t!=NULL)
    {
        btree3(t->llink);
        btree3(t->rlink);
    cout<<t->info; 
   }
}
 
//Нерекурсивный обход в обратном порядке
template<class DataT>void tree<DataT>::btree4(tree<DataT> *t)
{
    stack <tree<DataT>*> x(100);
    tree<DataT> *p;
    p=t;
m: while(p!=NULL)
    {
    x.push(p);
    p=p->llink;
    }
    if(!x.emptry())
    {
    p=x.pop();
    cout<<p->info;
    p=p->rlink;
    goto m;
    }
}
 
//нерекурсивный обход в прямом порядке
template<class DataT>void tree<DataT>::btree5(tree<DataT> *t)
{
    stack <tree<DataT>*> s(100);
    tree<DataT> *p;
    p=t;
    s.push(p);
    while(!s.emptry())
    {
    p=s.pop();
    cout<<p->info;
    if(p->rlink!=NULL)
        s.push(p->rlink);
    if(p->llink!=NULL)
        s.push(p->llink);
    }
}
 
//нерекурсивный прямой обход
template<class DataT>void tree<DataT>::btree6(tree<DataT> *t)
{
    struct obxod{char info; obxod *link; void btree6(tree<DataT> *t);};
    stack <tree<DataT>*> s(100);
    tree *p;
    
    p=t;
    obxod *first=NULL;
    obxod *q;
    s.push(p);
    while(!s.emptry())
    {
    p=s.pop();
    q=new obxod;
    q->info=p->info;
    q->link = first;
    first = q;
 
    if(p->llink!=NULL)
        s.push(p->llink);
    if(p->rlink!=NULL)
        s.push(p->rlink);
    }
//вывод
 
    q=first;
    while(q!=NULL)
    {
    cout<<q->info;
    q=q->link;
    }
}
 
int comand=0;
 
//Тело основной рабочей программы
int main()
{
    cout<<"Вводите дерево";
    cout<<endl;
    tree<char> t;
    cout<<endl;
    t.in(t.root);
 
cout<<"Рекурсивный обратный обход:\n";
t.btree1(t.root);
   cout<<endl;
cout<<"Рекурсивынй прямой обход:\n";
t.btree2(t.root);
   cout<<endl;
cout<<"Рекурсивный концевой обход:\n";
t.btree3(t.root);
   cout<<endl;
cout<<"Нерекурсивный обратный обход:\n";
t.btree4(t.root);
   cout<<endl;
cout<<"Нерекурсивный прямой обход:\n";
t.btree5(t.root);
   cout<<endl;
cout<<"Нерекурсивный концевой обход:\n";
t.btree6(t.root);
   cout<<endl;
       
}
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
12.12.2010, 21:50  [ТС]     Нерекурсивный обход дерева #9
что это за метод emptry?
АлександрШ
 Аватар для АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
12.12.2010, 22:05     Нерекурсивный обход дерева #10
в общем он используется для того, что проверить стек на пустоту.
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
12.12.2010, 22:56  [ТС]     Нерекурсивный обход дерева #11
но почему его назвали emptry?
по-моему все-таки empty называется для стека по крайней мере

Добавлено через 43 минуты
вот перебивал обход в прямом порядке
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
struct stack
{
  uzel *val;
  struct stack *next;//äîáГ*ГўГЁГ« Гў Г*Г*Г·Г*ëî èçâëåê Гў Г*Г*Г·Г*ëî
};
 
void push(stack *s,uzel *el)
{
    stack *elem=new stack;
    elem->next=s;
    elem->val=el;
    s=elem; 
}
 
uzel* pop(stack *s)
{
    stack *temp=s;
    s=s->next;
    stack *simp=temp;
    delete temp;
    return simp->val;
}
 
void print_tree_2(uzel *root)
{
    
    uzel *dr=root;
    stack *ss;
    push(ss,dr);
    while (ss!=0)
    {
        dr=pop(ss);
        cout<<dr->key;
        if (dr->right!=0)
         push(ss,dr->right);
        if (dr->left!=0)
         push(ss,dr->left);
    }
}
но ничего не выводит
АлександрШ
 Аватар для АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
15.12.2010, 16:38     Нерекурсивный обход дерева #12
а что вводишь? точнее как вводишь дерево? уверен что правильно?
Попробуй мою прогу скомпилируй и введи например ABC..D...

Если есть возможность в отладчике посмотри как прога работает...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.12.2010, 17:00     Нерекурсивный обход дерева
Еще ссылки по теме:

обход дерева C++
C++ Обход дерева Хаффмана
C++ обход дерева

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

Или воспользуйтесь поиском по форуму:
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
15.12.2010, 17:00  [ТС]     Нерекурсивный обход дерева #13
всё уже сделал и сдал
Yandex
Объявления
15.12.2010, 17:00     Нерекурсивный обход дерева
Ответ Создать тему
Опции темы

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