层次遍历及其应用

非递归层次遍历：

利用队列先进先出特性，分层次存储入队后输出。（下面代码是常见的一个）

void levelorder(Node* root){
    queue q; //指针队列 
    Node* p=root; //p依次遍历树
    q.push(p);
    while(!q.empty()){
        Node* p=q.front();
        q.pop();
        cout<data;
        if(p->left!=NULL){
            q.push(p->left);
        }
        if(p->right!=NULL){
            q.push(p->right);
        }
    }
}

应用1：求二叉树的高度和宽度

上述代码基础上让队列的元素数目q.size为每层的结点个数，MAX(q.size)即为二叉树的宽度；

用size控制一层的结束，height++计算二叉树的高度。

注：利用此代码也可输出第i层的结点。

void levelorder1(Node* root){
    queueq;
    Node* p=root;
    q.push(root);
    int m=0;//宽度 
    int height=0; //高度  
    while(!q.empty()){
        height++;
        for(int i=0;i){
            if(q.size()>m) m=q.size();
            Node* p=q.front();
            q.pop();
            cout<data;
            if(p->left!=NULL){
                q.push(p->left);
            }
            if(p->right!=NULL){
                q.push(p->right);
            }
        }
    }
    cout<<"二叉树的宽度是"<endl; 
    cout<<"二叉树的高度是"<endl;   
} 

应用2：判断二叉树是否是完全二叉树

(王道代码)

思想：将所有节点都进入队列中，包括空结点，此过程边出边进，出遇到空结点后，只进行出队操作，若其后面有非空结点，则此树非完全二叉树！ 

bool Iscomplete(Node* root){
    queue q;
    q.push(root);//将根节点入队 
    while(!q.empty()){
        Node* p=q.front();
        q.pop();//结点依次出队
        if(p){
            q.push(p->left);
            q.push(p->right);//将p的左右孩子入队，不管空还是不空 
        } 
        else{//p为空时(层次遍历遇到的第一个空结点) 
        //队列中p后面若还有非空结点，则此树是非完全二叉树。 
            while(!q.empty()){
                Node* p=q.front();
                q.pop();
                if(p){
                    return 0;
                }
            }
        }
    }
    return 1;
} 

注：另一博主相似思路：https://www.cnblogs.com/WTSRUVF/p/11029636.html