Trees on the level(UVA 122)
网址如下:
Trees on the level - UVA 122 - Virtual Judge (vjudge.net)
(第三方网站)
关于二叉树的构建以及bfs(宽度优先搜索)的
我抄了算法书的,算是便于学习
代码如下:
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
struct Node{
bool have_value;//是否被赋值过
int v;//节点值
Node * left, * right;
Node():have_value(false), left(NULL), right(NULL){}
} * root;
bool read_input(void);
Node * newnode(void){return new Node();}
void addnode(int v, char * s);
void remove_tree(Node * u);
bool bfs(vector<int> &ans);
const int maxn = 300;
char s[maxn];
bool failed;
int main(void)
{
while(read_input())
{
vector<int> ans;
if(failed){printf("not complete\n"); continue;}
if(!bfs(ans)){printf("not complete\n"); continue;}
int pos = 0;
for(auto it = ans.begin(); it != ans.end(); it++)
{
if(pos++) putchar(' ');
printf("%d", *it);
}
putchar('\n');
remove_tree(root);
}
}
bool read_input(void)
{
failed = false;
root = newnode();//创建根节点
while(true)
{
if(scanf("%s", s) != 1) return false;
if(!strcmp(s, "()")) break;
int v;
sscanf(&s[1], "%d", &v);
addnode(v, strchr(s, ',') + 1);
}
return true;
}
void addnode(int v, char * s)
{
int n = strlen(s);
Node * u = root;
for(int i = 0; i < n; i++)
if(s[i] == 'L')
{
if(u->left == NULL) u->left = newnode();
u = u->left;
}
else if(s[i] == 'R')
{
if(u->right == NULL) u->right = newnode();
u = u->right;
}
if(u->have_value) failed = true;
u->v = v;
u->have_value = true;
}
void remove_tree(Node * u)
{
if(u == NULL) return;
remove_tree(u->left); remove_tree(u->right);
delete u;
}
bool bfs(vector<int> &ans)
{
queue<Node *> q;
ans.clear();
q.push(root);
while(!q.empty())
{
Node * u = q.front(); q.pop();
if(!u->have_value) return false;
ans.push_back(u->v);
if(u->left != NULL) q.push(u->left);
if(u->right != NULL) q.push(u->right);
}
return true;
}
后面还有关于内存池的构建,还得看一下