广度优先遍历（BFS）例题

谁践踏了优雅 2022-05-05 09:37 172阅读 0赞

二叉树的层次遍历     UVa122

## 题目： ##

![70][]

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

一、输入数据的处理：

> ![70 1][]

此处两次用到的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)\{\}  
> \};

三、添加节点操作

> ![70 2][]

四、层序遍历（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;
    }

[70]: /images/20220505/8f2931ed055e4cb8bd4e7093d29fcc66.png
[P150UVa122]: https://blog.csdn.net/NCUscienceZ/article/details/78008320
[70 1]: /images/20220505/de194930c9534ff794b357fd28a969ce.png
[70 2]: /images/20220505/49d96d4b02414aa3afe277706a765c8e.png
[70 3]: /images/20220505/0daf592ebe4740aabc8f547247fe0607.png
[70 4]: /images/20220505/9daa2fcb2fd9499587741c2961334da0.png