#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
char s[1<<10]; // 存放输入进去的字符串
bool failed=false; // 用开关表示输出树还是输出not complete
struct Node{ //结构体 树的节点
bool have_value; // 是否有值
int v; // 值为多少
Node *left, *right; // 每一个节点都可能会有一个左子树和一个 右子树
Node(): have_value(false),left(NULL),right(NULL) {} //构造函数 默认初始值
};
Node *root; //根节点
Node* newnode(){ return new Node(); } //！！为什么newnode()函数传回的值是
Node*？ Node*不是值吗？
void addnode(int v,char *s){
int n = strlen(s);
Node *u = root; //！！在此处新建的节点u，root将什么传给了u， 是地址还是值？
for(int i = 0 ; i<n ; i++){
if(s[i]=='L'){
if(u->left==NULL) u->left = newnode();
u = u->left;
}
if(s[i]=='R'){
if(u->right == NULL) u->right = newnode();
u = u->right;
}
}
if(u->have_value==true) failed=true;
u->v = v;
u->have_value = true;
}
void remove_tree(Node* u){
if(u==NULL) return;
if(u->left) remove_tree(u->left);
if(u->right) remove_tree(u->right);
delete u;
}
bool read_input(){
int v;
failed = false;
remove_tree(root);
root = newnode();
for(;;){
if( scanf("%s",s)!=1 ) return false;
if(!strcmp(s,"()")) break;
sscanf(&s[1],"%d",&v);
addnode(v,strchr(s,',')+1);
}
return true;
}
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;
}
int main(){
freopen("in3.txt","r",stdin);
vector<int>ans;
while(read_input()){
if(!bfs(ans)) failed = 1;
if(failed) printf("not complete\n");
else{
for(int i = 0 ; i<ans.size() ; i++){
if(i) printf(" ");
printf("%d",ans[i]);
}
printf("\n");
}
}
return 0;
}
两处有很多问题想问：
1. 在newnode()处，函数为什么传回的值是Node* ， 在我仅有的一点基 础内，只明白*Node应该是个值，而&Node才是地址。
2. 在addnode()下 Node*u = root是什么操作？ 是将根节点的什么东西
传给u？ 是地址吗？为什么可以这样做？
看你的问题描述，你可能需要补一补指针方面的知识
1、new用于开辟内存空间保存变量，它的返回类型是指向这个内存空间的指针，例如int* a = new int()就是开辟一块内存，保存int变量，返回值a是指向这个变量的指针；
2、Node* u = root;指针的赋值，指针是一类特殊变量，它保存的是指针所指向变量的地址，这个赋值就是把root保存的地址赋给了u，这样root和u保存相同地址，两者共同指向根节点；
这棵树不是一颗完全二叉树，用数组建立，浪费内存，用指针建树，其中sscanf()函数作用很大，eg: sscanf(&s,"%d %d",&a,&b);在已有的字符串s中读取两个整形变量a,b;建好树后，再用广搜层次遍历。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct Node{
bool used;
Node *left,*right;
int v;
Node():used(false),left(NULL),right(NULL){}
};
Node *root;
char s[200];
bool failed;
Node *newnode(){ return new Node();}
void addnode(int v,char *s)
{
Node *u=root;
int n=strlen(s);
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->used==true) failed=true;
u->v=v;
u->used=true;
}
bool read_input()
{
failed=false;
root=newnode();
while(true){
if(scanf("%s",s)!=1) return false;
if(!strcmp(s,"()")) break;
int v;
char str[200];
sscanf(s,"(%d,%s",&v,str);
addnode(v,str);
}
return true;
}
bool bfs(vector<int> &ans)
{
queue<Node*>q;
ans.clear();
q.push(root);
while(!q.empty()){
Node *u=q.front();q.pop();
if(u->used==NULL) 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;
}
void Delete(Node *t)
{
if(t==NULL) return;
Delete(t->left);
Delete(t->right);
delete t;
}
int main()
{
vector<int>ans;
while(read_input()){
if(bfs(ans)&&!failed){
for(int i=0;i<ans.size()-1;i++){
printf("%d ",ans[i]);
}
printf("%d\n",ans[ans.size()-1]);
}
else{
printf("not complete\n");
}
Delete(root);
}
}