-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtreeSameStruct.cpp
More file actions
224 lines (198 loc) · 4.03 KB
/
Copy pathtreeSameStruct.cpp
File metadata and controls
224 lines (198 loc) · 4.03 KB
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
//data structure exercise
#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
using namespace std ;
typedef struct TreeNode TreeNode , *Tree ;
struct TreeNode {
char data ;
Tree lt ;
Tree rt ;
} ;
struct InputStru{
char c ;
char left ;
char right ;
} ;
Tree insertTree( struct InputStru* pInput , int inde )
{
Tree T =(Tree) malloc( sizeof(*T) ) ;
T->data = pInput[inde].c ;
T->lt = T->rt = NULL ;
if( pInput[inde].left >=0 )
T->lt = insertTree( pInput, pInput[inde].left ) ;
if( pInput[inde].right >=0 )
T->rt = insertTree(pInput, pInput[inde].right ) ;
return T ;
}
Tree readTree( string filn )
{
ifstream ifs( filn.c_str() ) ;
Tree R = NULL;
char c ;
char left , right ;
int n ;
int i = 0 ;
//cin >> n ;
ifs >> n ;
if( n == 0 )
return NULL ;
int* pIndex = new int[n] ;
for( i = 0 ; i < n ; i ++ )
pIndex[i] = -1 ;
struct InputStru* pInput = new struct InputStru [n] ;
i = 0 ;
while( i < n ) {
//cin >> c >> left >> right ;
ifs >> c >> left >> right ;
pInput[i].c = c ;
pInput[i].left = left - '0' ;
pInput[i].right = right - '0' ;
if( pInput[i].left >= 0 )
pIndex[ pInput[i].left ] = pInput[i].left ;
if( pInput[i].right >= 0 )
pIndex[ pInput[i].right] = pInput[i].right ;
i++ ;
}
ifs.close() ;
int head ;
for( i = 0 ; i < n ; i ++ ) {
if( pIndex[i] == -1 ) {
head = i ;
break ;
}
}
cout << head << endl ;
R = insertTree( pInput , head ) ;
return R ;
}
Tree readTree( istream InStream )
{
Tree R = NULL;
char c ;
char left , right ;
int n ;
int i = 0 ;
//cin >> n ;
InStream >> n ;
if( n == 0 )
return NULL ;
int* pIndex = new int[n] ;
for( i = 0 ; i < n ; i ++ )
pIndex[i] = -1 ;
struct InputStru* pInput = new struct InputStru [n] ;
i = 0 ;
while( i < n ) {
//cin >> c >> left >> right ;
InStream >> c >> left >> right ;
pInput[i].c = c ;
pInput[i].left = left - '0' ;
pInput[i].right = right - '0' ;
if( pInput[i].left >= 0 )
pIndex[ pInput[i].left ] = pInput[i].left ;
if( pInput[i].right >= 0 )
pIndex[ pInput[i].right] = pInput[i].right ;
i++ ;
}
int head ;
for( i = 0 ; i < n ; i ++ ) {
if( pIndex[i] == -1 ) {
head = i ;
break ;
}
}
cout << head << endl ;
R = insertTree( pInput , head ) ;
return R ;
}
bool compareTree( Tree T1 , Tree T2 )
{
if( T1==NULL && T2==NULL )
return true ;
if( T1 == NULL && T2 !=NULL )
return false ;
if( T1 != NULL && T2 == NULL )
return false ;
if( T1->data != T2->data )
return false ;
bool b1, b2 , b3 , b4;
Tree T11= T1->lt ;
Tree T21 = T2->lt ;
Tree T12 = T1->rt ;
Tree T22 = T2->rt ;
b1 = compareTree( T11 , T21 ) ;
b2 = compareTree( T12 , T22 ) ;
b3 = compareTree( T11, T22 ) ;
b4 = compareTree( T12 , T21 ) ;
return (b1&&b2) || (b3&&b4) ;
}
int main()
{
string filn1 = "d:\\tree1Input.txt" ;
string filn2 = "d:\\tree2Input.txt" ;
ifstream ifs( filn1.c_str() ) ;
Tree R1 = readTree( ifs /*cin*/ ) ;
ifs.close() ;
Tree R2 = readTree(filn2) ;
bool b = compareTree( R1 , R2 ) ;
if( b )
cout<<"Yes"<<endl ;
else
cout<<"No"<<endl ;
return 0 ;
}
/*
03-树1 树的同构（25 分）
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。
例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
现给定两棵树，请你判断它们是否是同构的。
输入格式:
输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N?1编号）；
随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，
则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。
输出格式:
如果两棵树是同构的，输出“Yes”，否则输出“No”。
输入样例1（对应图1）： 见Fig1Fig2.png
8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -
输出样例1:
Yes
输入样例2（对应图2）：见Fig1Fig2.png
8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4
输出样例2:
No
*/