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

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

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

обход бин дерева слева направо - C++

15.04.2013, 14:43. Просмотров 485. Ответов 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
#include <iostream> 
#include <math.h> 
#include <fstream> 
#include <stack> 
using namespace std; 
 
struct MyBiTree 
{
int Num;
int Data;
MyBiTree*left;
MyBiTree*right;
};
 
struct Result 
{
int Num;
int Data;
};
 
MyBiTree* ReadFromFile(); 
 
void CreateTree(MyBiTree**,int); 
 
Result* DFS (MyBiTree*); 
 
int ChoiceWay(MyBiTree*); 
 
int deep; 
int balance; 
int numb=1; 
int N=0; 
ifstream IN("1.txt"); 
 
void CreateTree(MyBiTree** root, int level) 
{
if((deep<level)&&(balance==0)) 
{
(*root)=NULL;
return;
}
 
if (deep<level) 
{
(*root)=new MyBiTree;
(*root)->Num=numb++; 
IN » (*root)->Data; 
(*root)->left=NULL; 
(*root)->right=NULL;
balance--; 
return;
}
 
(*root)=new MyBiTree;
(*root)->Num=numb++;
IN» (*root)->Data;
 
CreateTree(&(*root)->left,level+1);
CreateTree(&(*root)->right,level+1);
return;
 
}
 
MyBiTree* ReadFromFile()
{
MyBiTree *root; 
IN» N; 
deep=log10(N)/log10(2); 
balance=N-pow(2.0,deep)+1; 
 
CreateTree(&root,1); 
 
return root; 
 
}
 
int ChoiceWay(MyBiTree* root) 
{
if((root->left) && (root->left->Num>0)) 
return -1;
if((root->right) && (root->right->Num>0)) 
return 1;
return 0; 
}
 
Result* DFS(MyBiTree* root)
{
Result* result=new Result[N]; 
int i=0; 
stack <MyBiTree*> s; 
root->Num*=-1; 
s.push(root); 
while(!s.empty()) 
{
MyBiTree* p=s.top(); 
if(ChoiceWay(p)==-1) 
{
p->left->Num*=-1; 
s.push(p->left); 
}
else
if(ChoiceWay(p)==1) 
{
p->right->Num*=-1; 
s.push(p->right); 
}
else 
{
result[i].Num=-p->Num; 
result[i++].Data=p->Data; 
s.pop(); 
}
}
return result; 
}
 
int main()
{
 
MyBiTree* Root; 
 
Root=ReadFromFile(); 
 
Result* result=DFS(Root); 
 
 
for(int i=0;i<N;i++) 
cout « "Num:" « result[i].Num « " Data:" « result[i].Data « "\n";
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.04.2013, 14:43     обход бин дерева слева направо
Посмотрите здесь:

C++ поменять элементы каждого числа массива слева направо
Поменять элементы каждого числа массива слева направо C++
Постройка бин. дерева C++
C++ Сохранение и чтение бин. дерева
C++ Двумерный массив заполняется слева направо и сверху вниз
Выполнить циклический сдвиг двумерного массива по горизонтали слева направо C++
C++ Рекурсив. обход бин. дерева поиска
Слова читающиеся одинаково слева направо C++
Определение цифры слева направо C++
C++ Передвижение элементов двумерного массива слева направо
Данное четырехзначное число читается одинаково слева направо и справа налево C++
Каждое слово преобразовать так, чтобы оно читалось слева направо C++

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

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

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