【紫书】Trees on the level UVA - 122 动态建树及bfs
2024-09-02 04:02:59
题意:给你一些字符串,代表某个值被插入树中的位置。让你输出层序遍历。
题解:动态建树。
由于输入复杂,将输入封装成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");
}
最新文章
- Zabbix监控
- Photon服务器进阶&;一个新游戏的出产(三)
- closest应用(向上查找最近的资料)
- maven project 更新总是jre-1.5
- JS按回车键实现登录的方法
- Pig Latin
- MIMO-OFDM通信系统学习笔记(一)
- 03day2
- T4 文本模板编写准则
- SharePoint 2010 修改默认列表样式
- 【v2.x OGE课程 14】 控制使用
- Android.mk中的经常使用语法
- FreeMarker 实例
- .meta和模型贴图丢失
- Linux入门命令解释(1)
- PDB调试python代码常用命令
- 领域驱动设计学习之路—DDD的原则与实践
- 使用ML.NET实现白葡萄酒品质预测
- IO创建Socket通信中慎用BufferReader中的readLine()
- 20175320 2018-2019-2 《Java程序设计》第5周学习总结
热门文章
- 02-centOS6.7安装
- Linux环境SVN命令行使用经验总结(转)
- Git Step by Step – (5) Git分支(branch)
- 编译poco-1.7.8
- Elasticsearch 5.x 关于term query和match query的认识
- javascript的初步认识
- 在taro中跳转页面的时候执行两遍componentDidMount周期的原因和解决方法
- 在RDLC报表中对纸张的设置
- Web程序员应该知道的Javascript prototype原理
- Esper学习之十:EPL语法(六)