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

1 完满二叉树

除了叶子结点之外的每一个结点都有两个孩子结点。

如下是完满二叉树

  

   

    

     

    
    

     
 1
     
    
   

    

     

    
    

     
 2 3
     
    
   

    

     

    
    

     
 4 5
     
    
   

    

     

    
    

     
 6 7
     
    
  
 

2 分析 

我们按层(queue)遍历数，如果发现左子树为空右子树不为空 或者 左子树不为空右子树为空 的情况下直接返回false

3 代码实现

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <queue>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct Tree 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int value;
     
    
   

    

     

    
    

     
 struct Tree* left;
     
    
   

    

     

    
    

     
 struct Tree* right;
     
    
   

    

     

    
    

     

       Tree(int value):value(value), left(NULL), right(NULL){}
     
    
   

    

     

    
    

     

      } Tree;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool isFullCompleteTree(Tree* node)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (NULL == node)
     
    
   

    

     

    
    

     
 return false;
     
    
   

    

     

    
    

     
 queue<Tree *> queue;
     
    
   

    

     

    
    

     
 queue.push(node);
     
    
   

    

     

    
    

     
 while (!queue.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       Tree* pNode = queue.front();
     
    
   

    

     

    
    

     
 if ((pNode->left == NULL && pNode->right !
     
    
  
 

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

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