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

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

Войти
Регистрация
Восстановить пароль
 
нови4ок
0 / 0 / 0
Регистрация: 22.12.2012
Сообщений: 4
#1

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

09.04.2013, 18:37. Просмотров 689. Ответов 0
Метки нет (Все метки)

Не могу понять, почему при нерекурсивном обходе левый потомок на уровень выше смещается((
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;
 
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.04.2013, 18:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос нерекурсивный вариант процедуры обхода дерева в симметричном порядке (C++):

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

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

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

Процедура обхода для дерева - C++
постройте процедуру обхода для определения длины бинарного(или произвольного) дерева (т.е. длину максимальной ветви) PS если можно то...

Вывод обхода дерева в файл - C++
Есть бинарное дерево, не могу реализовать в нем вывод обхода дерева в файл из функции show(Node *&amp;der), вроде как-то можно забить данные из...

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.04.2013, 18:37
Привет! Вот еще темы с ответами:

Разобраться с рекурсивной функцией обхода бинарного дерева - C++
Люди, помогите разобраться с рекурсивной функцией обхода бинарного дерева. Бьюсь головой об стену, не могу понять как она работает. ...

Пронумеровать вершины бинарного дерева в соответствии с порядком концевого обхода - C++
Здравствуйте!!!! Помогите пожалуйста решить задачу. Построить бинарное дерево поиска для заданного множества целых чисел и занумеровать...

Сортировка точек в порядке обхода - C++
Дано n точек. В массиве a. Надо отсортировать точки в порядке обхода по или против часовой стрелки. Нужна помощь.

Напишите программу обхода двоичных деревьев во внутреннем порядке - C++
Помогите найти ошибку в коде. Задание: Напишите программу обхода двоичных деревьев во внутреннем порядке. #include&lt;iostream&gt; ...


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

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

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