обход бинарного дерева с помощью метода поиска в глубину слева направо
проверьте плиз
| 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;
} |
|
(
