广度优先遍历（BFS）例题-蒲公英云

广度优先遍历（BFS）例题

二叉树的层次遍历 UVa122

题目：

转载：树的层次遍历，紫书P150UVa122

一、输入数据的处理：

此处两次用到的c语言字符串的灵活性——可以把任何指向字符的指针看成一个字符串，从该位置开始直到‘\0’结束的字符串。例如，若读到的字符串节点是“（11，LL）”,则‘&s[1]’代表的含义是字符串“11，LL）”。函数strchr（s,’,’）返回字符串中从左往右第一个‘，’字符的指针，因此strchr（s，’,’）所对应的字符串为“LL)”。这样实际调用的是addnode（11，”LL”）。

二、二叉树基本结构的定义：

struct Node{
bool have_value;
int v;
Node* left, *right;
Node():have_value(false),left(NULL),right(NULL){}
};

三、添加节点操作

四、层序遍历（BFS）、

70 3

五、递归释放二叉树（防止内存泄漏）

70 4

最后贴上完整程序源代码：

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
//树结点 
struct Node{
    int v ;
    Node* left,*right ;
    int have_value ;
    Node():have_value(false),left(NULL),right(NULL){} ;
} ;
Node* root ;//根节点
Node* newnode(){
    return new Node() ; //返回一个新结点 
} 
bool failed ;
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 freetree(Node* u){ //释放内存 
    if(u == NULL) return ;
    freetree(u->left);
    freetree(u->right);
    delete u;
}
char s[1005];
bool read_input(){
    failed = false ;
    freetree(root) ;
    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 ;
} 
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(int argc, char *argv[])
{
    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 != 0) cout << " " ;
                   cout << ans[i];
            }
            cout << endl ;
        }    
    }
    return 0;
}

上面的代码写的比我的好些，但还是习惯性贴上自己的代码：

#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;
struct node//构造树的节点，下面的构造函数是非常好的 
{
    bool value;
    int v;
    node *left;
    node *right;
    node():value(false),v(0),left(NULL),right(NULL){}
};
node *root=new node;//创建一个根节点，便于创建和遍历 
                    //一定要开辟空间 
int v;
string com_s;
/* 
void print(node *u)
{
    cout<<endl<<u->value;
    cout<<" "<<u->v;
    if(u->left)
        cout<<" "<<"left exit";
    if(u->right)
         cout<<" "<<"right exit";
}
*/
void extract(string &in_s)//提取命令 
{
    int i;
    v=0;
    com_s.clear();//清空是clear，不是empty()。大爷的，查这么长时间查不出 
    for(i=1;isdigit(in_s[i]);i++)//s[0]为（ 
        v=v*10+(in_s[i]-'0');
    //跳出循环时，读取的是,的位置
    i++; 
    for(i;in_s[i]!=')';i++)
        com_s.push_back(in_s[i]); 
}
void creat_node()
{
    node *u=root;
    for(int i=0;com_s[i];i++)
    {    
        if(com_s[i]=='L')
        {    
            if(u->left==NULL)
                u->left=new node;
            u=u->left; 
        }
        else if(com_s[i]=='R')//如果右子树的空间已经存在
        {
            if(u->right==NULL)
                u->right=new node;
            u=u->right; 
        } 
    }
    u->v=v;
    if(!u->value) 
        u->value=true;
} 
bool bfs(vector<int> &ans)
{
    ans.clear();
    queue<node*> q;
    q.push(root);
    while(!q.empty())
    {
        node* u=q.front();
        if(!u->value) return false;
        ans.push_back(u->v);   //print(u);
        q.pop();
        if(u->left) q.push(u->left);
        if(u->right) q.push(u->right);
    }
    return true;
} 
void remove_tree(node *u)
{
    if(u==NULL) return;
    remove_tree(u->left);
    remove_tree(u->right);
    delete u;
}
int main()
{
    string in_s;
    vector<int> ans;
    /*输入信息，建立树*/ 
    while(cin>>in_s) 
    {
        if(in_s=="()") break;
        extract(in_s);//从中提取命令放入v和com_s中
    //    cout<<v;
        //cout<<com_s;
        creat_node();//创建节点，生成树 
        //system("pause");
    }
    /*广度遍历树*/
    if(bfs(ans))
    {
        int n=ans.size();
        for(int i=0;i<n;i++) 
            cout<<ans[i]<<" ";
    }
    else
        cout<<-1;
    remove_tree(root);
    return 0;
}