[C++知识库]二叉树层次遍历的相关应用(伪代码)

1.层次遍历

void LevelOrder(BTree *t){
    Queue Q;
    initQueue(Q);
    EnQueue(Q,t);
    while(!Empty(Q)){
        TNode*p=DeQueue(Q);
        if(p->lchird) EnQueue(Q,p->lchird);
        if(p->rchird) EnQueue(Q,p->rchird);
    }
}

求二叉树的高度(非递归)

int Height(BTree *t){
    Queue Q;    
    initQueue(Q);    
    EnQueue(Q,t); 
    int high=0;   
    while(!Empty(Q)){ 
       int n=Q.length;    
       for(int i=0;i<n;i++){
          TNode*p=DeQueue(Q);   
          if(p->lchird) EnQueue(Q,p->lchird);          
          if(p->rchird) EnQueue(Q,p->rchird);  
        } 
       high++; 
     }
     return high;
 }

求二叉树的宽度

int Width(BTree *t){
    Queue Q;    
    initQueue(Q);    
    EnQueue(Q,t); 
    int max=0;   
    while(!Empty(Q)){ 
       int n=Q.length; 
       if(max<n) max=n;  
       for(int i=0;i<n;i++){
          TNode*p=DeQueue(Q);   
          if(p->lchird) EnQueue(Q,p->lchird);          
          if(p->rchird) EnQueue(Q,p->rchird);  
        } 
     }
     return max;
 }

打印二叉树的右视图

void RightTree(BTree *t){
    Queue Q;    
    initQueue(Q);    
    EnQueue(Q,t);  
    while(!Empty(Q)){ 
       int n=Q.length; 
       for(int i=0;i<n;i++){
          TNode*p=DeQueue(Q);   
          if(p->lchird) EnQueue(Q,p->lchird);          
          if(p->rchird) EnQueue(Q,p->rchird);  
          if(i==n-1) printf("%d",p->data);
        } 
     }
 }

打印二叉树的左视图

void LeftTree(BTree *t){
    Queue Q;    
    initQueue(Q);    
    EnQueue(Q,t);  
    while(!Empty(Q)){ 
       int n=Q.length; 
       for(int i=0;i<n;i++){
          TNode*p=DeQueue(Q);   
          if(p->lchird) EnQueue(Q,p->lchird);          
          if(p->rchird) EnQueue(Q,p->rchird);  
          if(i==0) printf("%d",p->data);
        } 
     }
 }

求二叉树的指定层次的叶子结点个数

int Height(BTree *t,int k){
    Queue Q;    
    initQueue(Q);    
    EnQueue(Q,t); 
    int level=0,count=0;   
    while(!Empty(Q)){ 
       int n=Q.length;  
       level++;  
       for(int i=0;i<n;i++){
          TNode*p=DeQueue(Q);  
          if(!p->lchird&&!p->rchird&&level==k)
              count++;
          if(p->lchird) EnQueue(Q,p->lchird);          
          if(p->rchird) EnQueue(Q,p->rchird);  
        }   
     }
     return count;
 }

求最底层叶子结点权值之和

int Weight(BTree *t){
    Queue Q;    
    initQueue(Q);    
    EnQueue(Q,t); 
    int sum;   
    while(!Empty(Q)){ 
       int n=Q.length;  
       sum=0;  
       for(int i=0;i<n;i++){
          TNode*p=DeQueue(Q);  
          if(!p->lchird&&!p->rchird)
              sum+=p->data;
          if(p->lchird) EnQueue(Q,p->lchird);          
          if(p->rchird) EnQueue(Q,p->rchird);  
        }   
     }
     return sum;
 }

打印每层叶子结点权值之和

void LevelWeight(BTree *t){
    Queue Q;    
    initQueue(Q);    
    EnQueue(Q,t); 
    int sum,level=0;   
    while(!Empty(Q)){ 
       int n=Q.length;  
       sum=0; level++; 
       for(int i=0;i<n;i++){
          TNode*p=DeQueue(Q);  
          if(!p->lchird&&!p->rchird)
              sum+=p->data;
          printf("%d层的叶子结点权值之和%d\n",level,sum);
          if(p->lchird) EnQueue(Q,p->lchird);          
          if(p->rchird) EnQueue(Q,p->rchird);  
        }   
     }
 }