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

нерекурсивный вариант процедуры обхода дерева в симметричном порядке - C++

Восстановить пароль Регистрация
 
нови4ок
0 / 0 / 0
Регистрация: 22.12.2012
Сообщений: 4
09.04.2013, 18:37     нерекурсивный вариант процедуры обхода дерева в симметричном порядке #1
Не могу понять, почему при нерекурсивном обходе левый потомок на уровень выше смещается((
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
#include <iostream>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
const char TAB[6]="     ";
const char ERROR_INCORRECT_INT[125]="Введено некорректное числовое значение, пожалуйста повторите ввод.";
char input_inf[100];
using namespace std;
void menu()
{
    cout<<"_______________________________________________________________________________"<<endl;
    cout<<"|                               Меню:                                         |"<<endl;                                                              
    cout<<"|  (1)Построение ИСД                                                          |"<<endl;
    cout<<"|  (2)Вывод в прямом порядке                                                  |"<<endl;
    cout<<"|  (3)Вывод в симметричном порядке                                            |"<<endl;
    cout<<"|  (4)Вывод в обратно-симметричном порядке                                    |"<<endl;
    cout<<"|  (5)Вывод НЕРЕКУРСИВНЫМ способом в симметричном порядке                     |"<<endl;
    cout<<"|  Выберите действие и введите цифру или введите 'q' для выхода               |"<<endl;
    cout<<"|_____________________________________________________________________________|"<<endl;
};
struct Apex
{
    int information;
    struct Apex* Left;
    struct Apex* Right;
};
struct Apex* Root;
 
bool check_int(char *str)
{   int i=0;
while (str[i]!='\0')
{
    char symbol=str[i];
    if (!isdigit(symbol)){return false;};
    i++;
};
return true;
}
void dislpay_direct(Apex* current,int level)
{
    if (current!=NULL)
    {
 
        for(int i=1;i<=level;i++)
 
            cout<<TAB;
        cout<<current->information<<endl;
 
        level++;
        dislpay_direct(current->Left,level);
        dislpay_direct(current->Right,level);
    }
 
}
void display_symmetric(Apex* current,int level)
{
    if (current!=NULL)
    {
                level++;
        display_symmetric(current->Left,level);
                for(int i=1;i<level;i++)
            cout<<TAB;
        cout<<current->information<<endl;
        display_symmetric(current->Right,level);
 
    };
};
void display_symmetric_nonrecursive()
{
 
    struct StackItem
    {
        int level;
        struct Apex* LastApex;
        struct StackItem* Next;
    };
    struct StackItem* StackPoint=NULL;
    struct StackItem* temp;
    struct Apex* current;
    current=Root;
    bool stop = false;
    int level=-1;
    while (!(stop)) 
    {                
        while  (current!=NULL)
        {
            level++;
            temp=new(StackItem);
            temp->LastApex=current;
            temp->level=level;
            temp->Next=StackPoint;
            StackPoint=temp;
            current = current->Left;
        }
        if  (StackPoint==NULL) stop= true;
        else
        {
            current=StackPoint->LastApex;
            if (StackPoint->LastApex==Root) level = 0;
            else level = 1;
            for(int i=1;i<=StackPoint->level;i++)
            cout<<TAB;
            cout<<current->information<<endl;
            temp=StackPoint;
            StackPoint=StackPoint->Next;
            delete(temp);
            current = current->Right;
        }
    }
 
}
void display_reverse_symmetric(Apex* current,int level)
{
    if (current!=NULL)
    {
                level++;
        display_reverse_symmetric(current->Right,level);
                for(int i=1;i<level;i++)
            cout<<TAB;
        cout<<current->information<<endl;
        display_reverse_symmetric(current->Left,level);
 
    };
}
void build_tree(Apex* &current, int aN)
{
    int N_left,N_right;
    Apex* temp;
    if (aN==0)
    {
        current=NULL;
    }
    else
    {
        N_left=aN/2;
        N_right=aN-N_left-1;
        temp=new(Apex);
        build_tree(temp->Left,N_left);
        build_tree(temp->Right,N_right);
        temp->information=rand()%100;
        current=temp;
    }
}
int add()
{
    char input_inf[100];
    bool is_correct_int_value=false;
    while (!is_correct_int_value)
    {
        cout<<"введите количество вершин:"<<endl;
        cin>>input_inf;
        if (check_int(input_inf))
            is_correct_int_value=true;
        else cout<<ERROR_INCORRECT_INT<<endl;
    }
    build_tree(Root,atoi(input_inf));
    return atoi(input_inf);
}
int main()
{
    setlocale(LC_CTYPE, "");
    char input_key[254];
    char key;
    Root=NULL;
    srand((unsigned)time(NULL));
                                                                                                                                                                                                                                                    for(;;)
    {
        menu();
        cin>>input_key;
        if (strlen(input_key)>1) {cout<<"Данное действие не предустмотрено"<<endl; }
        else {
            key=input_key[0];
            switch (key)
            {
            case '1': {add(); break;};
            case '2': {dislpay_direct(Root,0); break;};
            case '3': {display_symmetric(Root,0); break;};
            case '4': {display_reverse_symmetric(Root,0);break;};
            case '5': {display_symmetric_nonrecursive();break;}
            case 'q': {return 0;break;};
            default: {cout<<"Данное действие не предустмотрено"<<endl;}
            };
        }
    }
 
    return 0;
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.04.2013, 18:37     нерекурсивный вариант процедуры обхода дерева в симметричном порядке
Посмотрите здесь:

НЕрекурсивный обход бинарного дерева C++
C++ Сортировка точек в порядке обхода
Процедура обхода для дерева C++
Процедура обхода для дерева C++
Разработать алгоритм и написать программу прошивания дерева при симметричном порядке обхода его C++
C++ Напишите программу обхода двоичных деревьев во внутреннем порядке
C++ Найти площадь многоугольника, заданного перечислением координат вершин в порядке обхода его границы
C++ Разобраться с рекурсивной функцией обхода бинарного дерева

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

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

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