首页 > > 程序设计 > C/C++ >

2018.12.4数据结构上机考试

2018-12-04 07:15:38来源：博客园阅读 ()

  1 #include<iostream>
  2 #include<string>
  3 #include<stack>
  4 #include<queue>
  5 using namespace std;
  6 
  7 class FTree {
  8 public:
  9     FTree();
 10     void getNodeNum();
 11     //递归先序构造二叉树形式的树/森林
 12     FTree(string str, int& index);
 13     //2）树和森林的先根遍历的递归和迭代算法；
 14     void preOrderbyRecursive();
 15     void preOrderbyIteration();
 16     //3）树和森林的后根遍历的递归和迭代算法；
 17     void afterOrderbyRecursive();
 18     void afterOrderbyIteration();
 19     //4）树和森林的层次遍历算法。
 20     void levelOrder();
 21     void getReltion(char node1,char node2);
 22     void getReltion();
 23     FTree* getNode(char node);
 24     ~FTree();
 25     bool isFatherOf(char node);
 26     bool isBrotherOf(char node);
 27     bool isGrandFatherOf(char node);
 28     bool isOtherTree(char node1,char node2);
 29     bool isSameTree(char node);
 30     bool haveLittleSon(char node);
 31 protected:
 32     char data;
 33     FTree* left_son;
 34     FTree* right_brother;
 35     int node_num;
 36 };
 37 
 38 int main() {
 39 
 40     //string ss = "124##57###3#6##"; int index = 0;
 41     //string ss = "RAB#C#D##EF##GH#IJ#####"; 
 42     string ss;
 43     cin >> ss;
 44     int index = 0;
 45     FTree t(ss, index);
 46     t.getNodeNum();
 47     cout << "从字符串 " << ss << " 构造树t " << endl;
 48     //t.getReltion('R','C');
 49     while (1) {
 50         t.getReltion();
 51     }
 52 
 53 }
 54 
 55 
 56 
 57 FTree::FTree()
 58 {
 59     data = NULL;
 60     left_son = 0;
 61     right_brother = 0;
 62 }
 63 void FTree::getNodeNum()
 64 {
 65     cout << "树的节点个数为" << node_num << endl;
 66 }
 67 FTree::FTree(string str, int& index)
 68 {
 69     if (str[index] == NULL) {
 70         cout << "输入的字符串错误！";
 71     }
 72     node_num = 0;
 73     if (index <= str.size() - 1 && str[index] != '#') {
 74         data = str[index];
 75         index++;
 76         node_num++;
 77         if (index <= str.size() - 1) {
 78             if (str[index] == '#') {
 79                 left_son = 0;
 80                 index++;
 81             }
 82             else {
 83                 left_son = new FTree(str, index);
 84                 node_num += left_son->node_num;
 85             }
 86         }
 87         if (index <= str.size() - 1) {
 88             if (str[index] == '#') {
 89                 right_brother = 0;
 90                 index++;
 91             }
 92             else {
 93                 right_brother = new FTree(str, index);
 94                 node_num += right_brother->node_num;
 95             }
 96         }
 97     }
 98     else {
 99         data = NULL;
100         index++;
101         left_son = 0;
102         right_brother = 0;
103     }
104 }
105 
106 void FTree::preOrderbyRecursive()
107 {
108     if (data == NULL) {
109         return;
110     }
111     cout << data;
112     if (left_son != 0) {
113         left_son->preOrderbyRecursive();
114     }
115     if (right_brother != 0) {
116         right_brother->preOrderbyRecursive();
117     }
118 }
119 
120 void FTree::preOrderbyIteration()
121 {
122     stack<FTree*> sta;
123     if (data == NULL) { return; }
124     cout << data;
125     if (left_son != 0) { sta.push(left_son); }
126     if (right_brother != 0) { sta.push(right_brother); }
127     while (!sta.empty()) {
128         FTree* f = sta.top(); sta.pop();
129         cout << f->data;
130         if (right_brother != 0) { sta.push(right_brother); }
131         if (left_son != 0) { sta.push(left_son); }
132     }
133 }
134 
135 void FTree::afterOrderbyRecursive()
136 {
137     if (data == NULL) {
138         return;
139     }
140 
141     if (left_son != 0) {
142         left_son->afterOrderbyRecursive();
143     }
144     cout << data;
145     if (right_brother != 0) {
146         right_brother->afterOrderbyRecursive();
147     }
148 
149 }
150 
151 void FTree::afterOrderbyIteration()
152 {
153     stack<FTree*> sta;
154     if (data == NULL) { return; }
155     if (right_brother != 0) { sta.push(right_brother); }
156     sta.push(this);
157     if (left_son != 0) { sta.push(left_son); }
158     while (!sta.empty()) {
159         FTree* f = sta.top(); sta.pop();
160         if (right_brother != 0) { sta.push(right_brother); }
161         cout << f->data;
162         if (left_son != 0) { sta.push(left_son); }
163     }
164 }
165 
166 void FTree::levelOrder()
167 {
168     queue<FTree*> que;
169     que.push(this);
170     while (!que.empty()) {
171         FTree* f = que.front();    que.pop();
172         while (f != 0) {
173             cout << f->data;
174             if (f->left_son != 0) {
175                 que.push(f->left_son);
176             }
177             f = f->right_brother;
178         }
179 
180     }
181 }
182 
183 void FTree::getReltion(char node1, char node2)
184 {
185     FTree* no1 = getNode(node1);
186     FTree* no2 = getNode(node2);
187     if (no1->isFatherOf(node2) == 1) {
188         return;
189     }
190     if (no2->isFatherOf(node1) == 1) {
191         return;
192     }
193     if (no1->isGrandFatherOf(node2) == 1) {
194         return;
195     }
196     if (no2->isGrandFatherOf(node1) == 1) {
197         return;
198     }
199 
200     if (no1->isBrotherOf(node2) == 1) {
201         return;
202     }
203     if (no2->isBrotherOf(node1) == 1) {
204         return;
205     }
206     if (this->isOtherTree(node1,node2) == 1) {
207         return;
208     }
209     if (no1->isSameTree(node2) == 1) {
210         return;
211     }
212     if (no2->isSameTree(node1) == 1) {
213         return;
214     }
215     cout << "其他关系" << endl;
216 }
217 
218 void FTree::getReltion()
219 {
220     char node1, node2;
221     cout << "\nplease input node1,node2\n";
222     cin >> node1;
223     cin>>node2;
224     getReltion(node1, node2);
225 }
226 
227 FTree * FTree::getNode(char node)
228 {
229     if (data == node) {
230         return this;
231     }
232     FTree* find = 0;
233     FTree* current = left_son;
234     while (current != 0) {
235         find = current->getNode(node);
236         if (find != nullptr) {
237             return find;
238         }
239         current = current->right_brother;
240     }
241     return 0;
242     return find;
243 }
244 
245 FTree::~FTree()
246 {
247     if (left_son != 0) {
248         //cout << left_son->data;
249         delete left_son;
250     }
251     if (right_brother != 0) {
252         //cout << right_brother->data;
253         delete right_brother;
254     }
255 
256 }
257 
258 bool FTree::isFatherOf(char node)
259 {
260     
261     FTree* current = left_son;
262     while (current != 0) {
263         if (current->data == node) {
264             cout << data << "与" << node << "是父子关系,";
265             cout << data << "是" << node << "的父亲"<<endl;
266             return 1;
267         }
268         else {
269             current = current->right_brother;
270         }
271     }
272     return false;
273 }
274 
275 bool FTree::isBrotherOf(char node)
276 {
277     FTree* current = right_brother;
278     while (current != 0) {
279         if (current->data == node) {
280             cout << data << "与" << node << "是兄弟关系\n";
281             cout << data << "是" << node << "的兄长";
282             return 1;
283         }
284         else {
285             current = current->right_brother;
286         }
287     }
288     return false;
289 }
290 
291 bool FTree::isGrandFatherOf(char node)
292 {
293     FTree* current = left_son;
294     while (current != 0) {
295         if (current->left_son != 0) {
296             FTree* currentson = current->left_son;
297             while (currentson != 0) {
298                 if (currentson->data == node) {
299                     cout << data << "与" << node << "是祖孙关系\n";
300                     cout << data << "是" << node << "的祖父";
301                     return 1;
302                 }
303                 currentson = currentson->right_brother;
304             }
305         }
306         current = current->right_brother;
307     }
308     return false;
309 }
310 
311 bool FTree::isOtherTree(char node1, char node2)
312 {
313     int flag = 0;
314     FTree* current = left_son;
315     while (current != 0) {
316         if (current->haveLittleSon(node1) ){
317             flag++;
318         }
319         else {
320             if (current->haveLittleSon(node2)) {
321                 flag++;
322             }
323         }
324         current = current->right_brother;
325     }
326     if (flag == 2) {
327         cout << "其他关系，"<< node1 << "与" << node2<<"不在同一分支上,"   <<endl;
328         return 1;
329     }
330     return false;
331 }
332 
333 bool FTree::isSameTree(char node)
334 {
335 
336     FTree* current = left_son;
337     while (current != 0) {
338         if (current->left_son != 0) {
339             if (current->haveLittleSon(node)) {
340                 cout << "其他关系，在同一分支上," << data << "是" << node << "祖父以上长辈"<<endl;
341                 return 1;
342             }
343         }
344         current = current->right_brother;
345     }
346     return false;
347 }
348 
349 bool FTree::haveLittleSon(char node)
350 {
351     if (data == node) {
352         return 1;
353     }
354     bool flag=0;
355     FTree* current = left_son;
356     while (current != 0) {
357         if (current->data == node) {
358             return 1;
359         }
360         flag = current->haveLittleSon(node);
361         current = current->right_brother;
362     }
363     return flag;
364 }