数据结构之判断一棵树是不是满二叉树

1 满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

2 分析

我们知道满二叉树是三角形的比如如下，最后一层任何一个节点的高度都是数的高度。

  

   

    

     

    
    

     
 1
     
    
   

    

     

    
    

     
 2 3
     
    
   

    

     

    
    

     

      4 5 6 7
     
    
  
 

但是如下二叉树就不是满二叉树

  

   

    

     

    
    

     
 1
     
    
   

    

     

    
    

     
 2 3
     
    
   

    

     

    
    

     

      4 5 
     
    
  
 

我们知道满二叉树节点总数是 (2^k) -1个，那么我们只需要求出高度就知道所有数的所有节点总数，然后我们再通过按层打印看下所有节点总数是不是满足满二叉树节点总数是 (2^k) -1的特点。

3 代码实现

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <queue>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct Tree 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int value;
     
    
   

    

     

    
    

     
 struct Tree* left;
     
    
   

    

     

    
    

     
 struct Tree* right
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/102773871