题意:给你一些字符串,代表某个值被插入树中的位置。让你输出层序遍历。

题解:动态建树。

   由于输入复杂,将输入封装成read_input。注意输入函数返回的情况

   再将申请新节点封装成newnode().

   最后层序输出直接用bfs实现。

坑:我把ans.clear放到主程序的if里面,导致某特定情况无法初始化,wa了一页//以后debug真的别XJB改细节了上下语句顺序,一些无关紧要的处理,改之前想一想

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include<stdio.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = ;
char s[maxn];
int failed;
struct node {
int v;
bool have_v;
node* leftson, *rightson;
node() :have_v(false), leftson(NULL), rightson(NULL) {}
}*root;
node* newnode() { return new node(); }
void addnode(int v, char *s) {
int n = strlen(s);
node * now = root; for (int i = ; i < n - ; i++) {
if (s[i] == 'L') { if (now->leftson == NULL) now->leftson = newnode();
now = now->leftson;
}
else {
if (now->rightson == NULL) now->rightson = newnode();
now = now->rightson;
} }
if (now->have_v) { failed = ; }
now->v = v;
now->have_v = ;
}
bool read_input() {
failed = false; root = newnode();
while () {
while (scanf("%s", &s) != )return false;
if (s[] == ')')break;
int v;
sscanf(&s[], "%d", &v);
addnode(v, strchr(s, ',') + );
}
return true;
}
list<int>ans;
void bfs() {
ans.clear();
queue<node> Q;
node now;
//int vis[maxn];
Q.push(*root);
while (!Q.empty()) {
now = Q.front(); if (!now.have_v) { failed = ; break; }
Q.pop();
if (now.leftson != NULL)Q.push(*now.leftson);
if (now.rightson != NULL)Q.push(*now.rightson);
ans.push_back(now.v);
} }
int main() {
while (read_input()) {
bfs();
if (failed)cout << "not complete" ;
else
{
cout << ans.front(); ans.pop_front();
for (auto t : ans)cout << ' ' << t;
}
cout << endl;
} system("pause");
}

最新文章

  1. Zabbix监控
  2. Photon服务器进阶&amp;一个新游戏的出产(三)
  3. closest应用(向上查找最近的资料)
  4. maven project 更新总是jre-1.5
  5. JS按回车键实现登录的方法
  6. Pig Latin
  7. MIMO-OFDM通信系统学习笔记(一)
  8. 03day2
  9. T4 文本模板编写准则
  10. SharePoint 2010 修改默认列表样式
  11. 【v2.x OGE课程 14】 控制使用
  12. Android.mk中的经常使用语法
  13. FreeMarker 实例
  14. .meta和模型贴图丢失
  15. Linux入门命令解释(1)
  16. PDB调试python代码常用命令
  17. 领域驱动设计学习之路—DDD的原则与实践
  18. 使用ML.NET实现白葡萄酒品质预测
  19. IO创建Socket通信中慎用BufferReader中的readLine()
  20. 20175320 2018-2019-2 《Java程序设计》第5周学习总结

热门文章

  1. 02-centOS6.7安装
  2. Linux环境SVN命令行使用经验总结(转)
  3. Git Step by Step – (5) Git分支(branch)
  4. 编译poco-1.7.8
  5. Elasticsearch 5.x 关于term query和match query的认识
  6. javascript的初步认识
  7. 在taro中跳转页面的时候执行两遍componentDidMount周期的原因和解决方法
  8. 在RDLC报表中对纸张的设置
  9. Web程序员应该知道的Javascript prototype原理
  10. Esper学习之十:EPL语法(六)