二叉树的层次遍历（建树，遍历，释放）

这题的思路：读入--》判断是否为循环结束的条件（主动）--》判断是否
输入错误--》用队列向vector中输入合法数据--》按顺序输出

a)        编写readin函数，专门用来读取数据。函数返回类型为bool，输入不合法时返回false。依题意，如果输入只有()，表示input终止，跳出循环并返回true

b)        编写名为Node的结构体。结构体中包含input中括号左侧的结值、判断结点是否被赋值的bool类型的值，和类型为Node *的左右子结点。由于二叉树是递归定义的，其左右子结点类型都是“指向结类型的指针”，因此左右子结点的类型都是Node *

c)        建立全局变量failed，记录是否有从根到某个叶结的路径上有的结没有在输入中给出或值给出超过一次的情况

d)        建立函数addnode：按照移动序列走，目标不存在时调用newnode函数来创造新结点，判断结点是否已被赋值（如果已经被赋过值，将failed值改为true），并将结点值赋给对应的结点

e)        bfs找结点，使用队列：初始时只有一个根结点，然后每次取出一个结点，把它的左右子结点（如果存在）放进队列中，用vector保存结点的值

PS:failed 仅仅是作为continue的条件 真正退出的条件只能是readin读入到了结束
failed在外部函数中出现在了readin里的addnode函数里 作为重复赋值的判断
然后在bfs里有一个是否complete的判断 也与failed一样作为能否进入为vector赋值的条件

readin—》addnode—》bfs—》over

include<vector>

include<cstdio>

include<queue>

include<iostream>

include<cstring>

using namespace std;

const int maxn = 256 + 10;
char s[maxn];
bool failed;

struct Node{
int v; //结点值
bool have_value; //用来判断是否被赋值过
Node *left, *right; //递归定义左右结点
};
Node *root;

Node *newnode(){
return new Node(); //每建立一个结点用new运算符申请
}

void addnode(int v,char *s){
Node *u = root; //将根节点指向的地址赋给u进行储存
int n = strlen(s); //确定循环次数
for(int i = 0; i < n; n++){
if(s[i] == 'L'){
if(u->left==NULL){ //如果这个结点未被创建
u->left = newnode();//那么创建它
u = u->left; //并且将u指向它以进行下一次循环
}
}
else if(s[i] == 'R'){
if(u->right==NULL){ //同上
u->right=newnode();
u = u->left;
}
}
if(u->have_value) failed = true;//如果它已经被创建那么把标记值赋为ture 以在主函数中终止此次循环
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 readin(){ //这个函数是用来读入的
failed = false;
remove_tree(root);
root = newnode(); //创建根结点可能导致内存泄漏
for( ; ; ){
if(scanf("%s", s) != 1) return false;//读到了结束标志
if(strcmp(s,"()")) break;//比较字符串是否相等
//按照顺序比，第一个都是T 第二个都是h 第三个a<e 所以...就这样。比较方法就是挨个比较，利用ASCII码
//相等返回0 大于返回正整数小于返回负整数
int v;
sscanf(&s[1],"%d",&v); //不管了...
addnode(v,strchr(s,',')+1);//不管看不懂
}
return true ;
}

bool bfs(vector<int>&ans){
queue<Node*> q; //创建队列以存放结点
q.push(root); //将已经创建好的树的根节点放入队列
while(!q.empty()){ //当队列不为空（即未全部按顺序加入vector完）
Node *u = q.front(); //创建结构指针指向队列头
q.pop(); //出列
if(!u->have_value) return false;//如果该结点未被赋值过则树不完整返回false 在主函数中结束此次循环
if(u->left!=NULL) q.push(u->left); //若不为空则加入队列中
if(u->right!=NULL) q.push(u->right);//注意先左再右（题目要求）
}//有些树可能have_value是空的但是仍为一些结点的根节点
return true;
}

int main(){
while(1){
if(!readin()) break;

    vector<int>ans;
    if(!failed&&bfs(ans)){
        int len = ans.size();
        for(int i = 0; i < len; i++){
            printf("%d%c",ans[i],i == len-1?'\n':' ');
        }
    }
    else 
        printf("not complete");
}
return 0;

}

最后编辑于：2018.03.22 20:27:02