您的位置: 首页  >  文章  >  二叉树经典面试题4~判断一棵树是否是完全二叉树

二叉树经典面试题4~判断一棵树是否是完全二叉树

分类: 文章 • 2024-01-05 20:05:58

转载：点击打开链接

二叉树经典面试题4~判断一棵树是否是完全二叉树

 一.问题描述

  有一棵树判断该树是否是完全二叉树？

二.问题分析

1.完全二叉树的定义？

  判断一棵树是否是完全二叉树，首先要知道什仫是完全二叉树？完全二叉树就是除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

  1. 若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。  
  2.   
  3. 完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。  
  4.   
  5. 一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。  

   二叉树经典面试题4~判断一棵树是否是完全二叉树

 2.如何判断一棵树是完全二叉树？

    在了解了完全二叉树的概念之后，相信读者应该都会判定一颗树是否是完全二叉树了，根据完全二叉树的定义，我们知道完全二叉树的前h-1是满二叉树，而最后一层又是从左到右没有间隔的，如果对这棵树进行层序遍历会发生什仫情况呢？详细介绍见下。在这里我提到两种判断完全二叉树的方法：

    1).标记法

     二叉树经典面试题4~判断一棵树是否是完全二叉树

    设置标记flag=false,如上图所示，从根结点开始层序遍历入队列，如果队列不为空，一直循环。遇到第一个没有左孩子或者右孩子的结点，设置标记位flag=true,如果继续入队列再次遇到存在孩子的结点一定不是完全二叉树。

  1. //设置标志位的方法  
  2. bool IsCompleteBinaryTree1()  
  3. {  
  4.     bool flag=false;  
  5.     queue<Node *>q;  
  6.     q.push(_root);  
  7.     Node *cur=q.front();  
  8.     while (cur)  
  9.     {  
  10.         //有右孩子无左孩子  
  11.         if(cur->_left == NULL && cur->_right != NULL)  
  12.             return false;  
  13.         //标志位为true并且当前结点存在孩子  
  14.         if(flag == true && (cur->_left || cur->_right))  
  15.             return false;  
  16.         //如果当前结点少一个孩子  
  17.         if(cur->_left == NULL || cur->_right == NULL)  
  18.             flag=true;  
  19.         if(cur->_left)  
  20.             q.push(cur->_left);  
  21.         if(cur->_right)  
  22.             q.push(cur->_right);  
  23.         q.pop();  
  24.         if(!q.empty())  
  25.             cur=q.front();  
  26.         else  
  27.             cur=NULL;  
  28.     }  
  29.     return true;  
  30. }  

     2).剩余队列判空法

     突然发现使用上述标记法要考虑的情况很多，不太方便，于是又提出了另一种方法，就是剩余队列判空法

     这个方法同样的用到了队列这种辅助结构，那仫如何只通过队列这个结构来判断一棵树是否是完全二叉树呢？试想一下，如果我们把一棵树的所有结点，包括叶子结点的左右空孩子都通过层序遍历入队列会发生什仫情况？详细的分析见下图：

      二叉树经典面试题4~判断一棵树是否是完全二叉树

      二叉树经典面试题4~判断一棵树是否是完全二叉树

[cpp] view plain copy
print?
  1. //利用辅助队列的办法  
  2. bool IsCompleteBinaryTree2()  
  3. {  
  4.     queue<Node *>q;  
  5.     q.push(_root);  
  6.     Node *cur=q.front();  
  7.     //按照层序遍历的办法入队列直到遇到第一个NULL停止  
  8.     while (cur)  
  9.     {  
  10.         q.push(cur->_left);  
  11.         q.push(cur->_right);  
  12.         q.pop();  
  13.         cur=q.front();  
  14.     }  
  15.     //如果队列中全为NULL则是完全二叉树，否则不是  
  16.     while(!q.empty())  
  17.     {  
  18.         if(q.front())  
  19.             return false;  
  20.         q.pop();  
  21.     }  
  22.     return true;  
  23. }  

 三.完整的代码实现

[cpp] view plain copy
print?
  1. template<class T>  
  2. struct BinaryTreeNode  
  3. {  
  4.     T _data;  
  5.     BinaryTreeNode<T> *_left;  
  6.     BinaryTreeNode<T> *_right;  
  7.     BinaryTreeNode(const T& data)  
  8.         :_data(data)  
  9.         ,_left(NULL)  
  10.         ,_right(NULL)  
  11.     {}  
  12. };  
  13. template<class T>  
  14. class BinaryTree  
  15. {  
  16.     typedef BinaryTreeNode<T> Node;  
  17. public:  
  18.     BinaryTree()  
  19.         :_root(NULL)  
  20.     {}  
  21.     BinaryTree(const T*a,size_t size,const T& invalid)  
  22.     {  
  23.         size_t index=0;  
  24.         _root=_CreatTree(a,size,index,invalid);  
  25.     }  
  26.     //设置标志位的方法  
  27.     bool IsCompleteBinaryTree1()  
  28.     {  
  29.         bool flag=false;  
  30.         queue<Node *>q;  
  31.         q.push(_root);  
  32.         Node *cur=q.front();  
  33.         while (cur)  
  34.         {  
  35.             //有右孩子无左孩子  
  36.             if(cur->_left == NULL && cur->_right != NULL)  
  37.                 return false;  
  38.             //标志位为true并且当前结点存在孩子  
  39.             if(flag == true && (cur->_left || cur->_right))  
  40.                 return false;  
  41.             //如果当前结点少一个孩子  
  42.             if(cur->_left == NULL || cur->_right == NULL)  
  43.                 flag=true;  
  44.             if(cur->_left)  
  45.                 q.push(cur->_left);  
  46.             if(cur->_right)  
  47.                 q.push(cur->_right);  
  48.             q.pop();  
  49.             if(!q.empty())  
  50.                 cur=q.front();  
  51.             else  
  52.                 cur=NULL;  
  53.         }  
  54.         return true;  
  55.     }  
  56.     //利用辅助队列的办法  
  57.     bool IsCompleteBinaryTree2()  
  58.     {  
  59.         queue<Node *>q;  
  60.         q.push(_root);  
  61.         Node *cur=q.front();  
  62.         //按照层序遍历的办法入队列直到遇到第一个NULL停止  
  63.         while (cur)  
  64.         {  
  65.             q.push(cur->_left);  
  66.             q.push(cur->_right);  
  67.             q.pop();  
  68.             cur=q.front();  
  69.         }  
  70.         //如果队列中全为NULL则是完全二叉树，否则不是  
  71.         while(!q.empty())  
  72.         {  
  73.             if(q.front())  
  74.                 return false;  
  75.             q.pop();  
  76.         }  
  77.         return true;  
  78.     }  
  79. protected:  
  80.     Node* _CreatTree(const T*a,size_t size,size_t& index,const T& invalid)  
  81.     {  
  82.         assert(a);  
  83.         Node *root=NULL;  
  84.         if(index < size && a[index] != invalid)  
  85.         {  
  86.             root=new Node(a[index]);  
  87.             root->_left=_CreatTree(a,size,++index,invalid);  
  88.             root->_right=_CreatTree(a,size,++index,invalid);  
  89.         }  
  90.         return root;  
  91.     }  
  92. protected:  
  93.     Node *_root;  
  94. };  
  95. void testIsCompleteTree()  
  96. {  
  97.     //int array[]={0,1,3,'#','#','#',2,4,'#','#',5};    //false  
  98.     //int array[]={0,1,3,'#','#',4,'#','#',2,5,'#','#','#'}; //true  
  99.     //int array[]={0,1,3,'#','#',4,'#','#',2};  //true  
  100.     int array[]={0,1,3,'#','#','#',2};  
  101.     size_t size=sizeof(array)/sizeof(array[0]);  
  102.     BinaryTree<int> bt(array,size,'#');  
  103.     bool ret=bt.IsCompleteBinaryTree2();  
  104.     if(ret == true)  
  105.         cout<<"是完全二叉树"<<endl;  
  106.     else  
  107.         cout<<"不是完全二叉树"<<endl;  
  108. }  

相关推荐