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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.86
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
#1

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

11.12.2010, 16:04. Просмотров 2808. Ответов 12
Метки нет (Все метки)

я не могу понять как сделать не рекурсивный обход дерева.
понятно что надо добавлять элементы куда-то.в стек например.
но я не знаю как в смысле по какому правилу и т.п.
как обойти все элементы дерева добавляя их в стек без рекурсии?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2010, 16:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нерекурсивный обход дерева (C++):

НЕрекурсивный обход бинарного дерева - C++
уважаемые программисты! нужно написать алгоритм обхода бинарного дерева без использования рекурсии, а с помощью стека. Проверить на...

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

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

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

Обход дерева - C++
Всем доброе время суток. Не могу нормально обойти дерево и просмотреть введённое, по всей видимости, возможно я неправильно поставил...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
ЧакЭ одобряЭ
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
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
12.12.2010, 14:16 #4
вот это:
Цитата Сообщение от Artishok Посмотреть сообщение
elem->val=dr;
в 6 строке, что такое? dr вроде указатель на узел дерева, чего его присваивать значению узла... надо составить всю программу и откомпилировать, тогда яснее будет, а так вроде правильно.
я, кстати, рабочий вариант написал, чем он не понравился?
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
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
ЧакЭ одобряЭ
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
ЧакЭ одобряЭ
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
ЧакЭ одобряЭ
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...

Если есть возможность в отладчике посмотри как прога работает...
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
15.12.2010, 17:00  [ТС] #13
всё уже сделал и сдал
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.12.2010, 17:00
Привет! Вот еще темы с ответами:

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

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

Обход бинарного дерева - C++
Прошу Вас, помогите школьнику, незнающему деревья, завтра срочно надо сдать работу, я никак не могу реализовать... 1. В заданном...

Обход Бинарного дерева - C++
Задача: написать функцию, помощью которой можно получить n-тый элемент бинарного дерева по возрастанию. в узлах хранятся целые числа. ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.12.2010, 17:00
Ответ Создать тему
Опции темы

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