二叉树的层次遍历（完整版）

亦凉 2023-07-18 16:24 469阅读 0赞

## 二叉树的层次遍历 ##

二叉树的层次遍历也被称为宽度优先遍历（BFS)。可以用递归实现也可以用队列等数据结构实现，下面介绍以[uva的trees on the level][uva_trees on the level] 为例介绍BFS的完整代码（参考算法竞赛入门经典）。输入二叉树的每一个节点的信息，输入利用”左右“来给出结点所在位置，建树完毕后，按照层次顺序遍历打印这棵树，打印权值信息。

#include<stdio.h>
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    const int maxn = 266;
    char s[maxn];
    bool failed;
    struct Node{
        //结构体的声明，节点的值和指针，have_value判断是否有值
      bool have_value;
      int v;have_value
      Node* left, *right;
      Node():have_value(false),left(NULL),right(NULL){
        }//构造函数
    };
     
    Node* root;
    Node* newnode() {
         return new Node(); }
    
    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 read_input(){
        //读取输入数据 
    	failed = false;
    	remove_tree(root); 
    	root=newnode();
    	for(;;){
        
    		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){
        //使用队列进行层次遍历，利用引用进行参数传递，其实是一种指针的形式，如果在函数内我们改变了a,b的值，当函数结束后，原来的值也将被改变。在C语言中，要想在自定义函数中通过形参来改变实参的值，必须给形参传递实参的地址
    	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(){
        
      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) printf(" ");
            printf("%d", ans[i]);
          }
          printf("\n");
        }
      }
      return 0;
    }

[uva_trees on the level]: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=838&page=show_problem&problem=58