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 }
用的树
有哪些收获:
1.注意审题,只有四种类型
2.函数模块化,使函数尽量简短易读
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 数据结构—链表 2020-05-29
- 图 2020-05-02
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 数据结构之顺序表的实现 2020-04-06
- 数据结构-线性表 2020-03-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash