完全二叉树：若一棵二叉树具有具有n个节点，它的每个节点都与高度为k的满二叉树编号为0~n-1结点一一对应，则称这可二叉树为完全二叉树。

方法一：一维数组存储

根据完全二叉树的定义和性质，利用一位数组作为完全二叉树的存储，如下图

由图，节点的编号与数组元素的下标是一一对应的，可根据二叉树的性质，可方便找出下标为i的的双亲结点a[i/2]及左右孩子结点a[i*2],a[i*2+1].这样判断一棵树是否为二叉树，应该对此二叉树从上到下，从左到右依次编号，然后把编好的号依次存入一位数组中，在与相应深度的满二叉树的编号进行对比，即可判断此二叉树是否为完全二叉树。


但是该方法虽然实现容易，但占用空间太大，并且效率低，所以可通过层次遍历来判断是否为完全二叉树。

方法二：层次遍历（利用队列）

完全二叉树是指最后一层左边是满的，右边可能慢也不能不满，然后其余层都是满的，根据这个特性，利用层遍历。如果我们当前遍历到了NULL结点，如果后续还有非NULL结点，说明是非完全二叉树。

bool_CheckCompleteTree(Node*root){queue<Node*>q;if(root==NULL)//空树是完全二叉树returntrue;q.push(root);boolflag=false;while(!q.empty()){Node*front=q.front();if(front!=NULL){if(flag)returnfalse;q.push(front->_left);q.push(front->_right);}elseflag=true;q.pop();}returntrue;}


完整代码及测试用例

#include<iostream>#include<queue>usingnamespacestd;template<classT>structBinaryTreeNode{T_data;BinaryTreeNode*_left;BinaryTreeNode*_right;BinaryTreeNode(constT&d):_data(d),_left(NULL),_right(NULL){}};template<classT>classBinaryTree{typedefBinaryTreeNode<T>Node;public:BinaryTree():_root(NULL){}BinaryTree(constT*a,size_tsize,constT&invalid){size_tindex=0;_root=_CreateNode(a,size,index,invalid);}voidCheckCompleteTree(){boolret;ret=_CheckCompleteTree(_root);cout<<"IsacomplateBinaryTree?:"<<ret<<endl;}protected:bool_CheckCompleteTree(Node*root){queue<Node*>q;if(root==NULL)//空树是完全二叉树returntrue;q.push(root);boolflag=false;while(!q.empty()){Node*front=q.front();if(front!=NULL){if(flag)returnfalse;q.push(front->_left);q.push(front->_right);}elseflag=true;q.pop();}returntrue;}Node*_CreateNode(constT*a,size_tsize,size_t&index,constT&invalid){Node*root=NULL;while((index<size)&&(a[index]!=invalid)){root=newNode(a[index]);root->_left=_CreateNode(a,size,++index,invalid);root->_right=_CreateNode(a,size,++index,invalid);}returnroot;}protected:Node*_root;};intmain(){inta[10]={1,2,3,'#','#',4,'#','#',5,6,};BinaryTree<int>b1(a,10,'#');b1.CheckCompleteTree();inta2[9]={1,2,'#',3,'#',4,'#','#',5};BinaryTree<int>b2(a2,9,'#');b2.CheckCompleteTree();system("pause");return0;}