判断一颗二叉树是否是完全二叉树

4.判断一颗二叉树是否是完全二叉树
思路: 完全二叉树定义：完全二叉树：只有最下面的一层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
我们根据二叉树性质， 在下一层结点满的情况下，结点数是上一层结点数二倍  -->
利用两个队列， 队列1保存上层结点， 队列2保存下层结点(由队列1中结点得到)
我们先将 根节点入队列 1， 利用一个变量来保存 队列1 中 结点个数， 并依次将队列1 顶端 的 左右孩子入队列2， 直到队列1为空（每次pop一次），
利用第二个变量 保存此时 队列2中结点个数（也可以调用 queue 的 size（ ） 方法， 不过为了使程序简明， 我们利用一个新变量来做这件事）
在 队列1中结点的孩子 入 队列二 的时候， 我们添加一个 if 条件来判断， 队列1中的每个节点的 孩子， 是否是 只有右孩子没有左孩子， 如果是， 则不满足完全二叉树规则， 我们返回 false
当 队列1 中元素为空， 即原队列1 中的结点孩子都入队列二 后我们判断， 我们的两个变量是否是二倍关系，  依次进行， 
直到数量关系不满足（即 队列二中的结点数量 并不是 队列1 中的结点数量二倍）， 此时， 因为我们已经在队列2结点入队列时， 检测过完全二叉树的 ：“最下面一层的结点都集中在该层最左边的若干位置的二叉树” 这个条件,
因此我们只需要关注，  队列二中的结点， 是不是最后一层结点， 即它们有没有孩子， 如果有， 则返回false， 否则， 返回true.

我们还需增加一个标志位来判断这种情况:  -->  如图：

增加标志位防止如图的二叉树使我们程序产生bug.

.h:

#ifndef BINARY_TREE_H_
#define BINARY_TREE_H_


template<class T>
struct BinaryTreeNode
{
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
	T _date;

	BinaryTreeNode( const T& x )
		:_date( x )
		,_left( NULL )
		,_right( NULL )
	{}
};


template<class T>
class BinaryTree
{
	typedef BinaryTreeNode<T> Node;

public:
	BinaryTree( )
		:_root( NULL )
	{}

	BinaryTree( T* a, size_t n, const T& invalid = T( ) )
	{
		size_t index = 0;

		_root = CreateTree( a, n, invalid, index );
	}

	Node* GetRoot( )
	{
		return _root;
	}

	~BinaryTree( )
	{
		_Destroy( _root );
	}

protected:
	Node* _root;

	Node* CreateTree( T* a, size_t n, const T& invalid, size_t& index )//因为递归会创建多个index变量，为使index值正确，此处用引用  而第一处用引用是处于节省空间考虑
	{
		Node* root = NULL;						//采用前序遍历创建二叉树

		if ( (index < n) && (a[index] != invalid) )//先序前序后序是以根为前中后.  通过数组写树时，  按顺序写  比如前序 根左右  就先写大框架，留出缝隙， 在当子问题处理， 往中间加数据(即把根 左 右都当作一个新根  子问题)
		{
			root = new Node( a[index] );			//注意圆括号与方括号的区别  圆括号构建一个用delete  而方括号构建多个 用delete[]

			root->_left = CreateTree( a, n, invalid, ++index );//构建完左子树再执行下面构建右子树
			root->_right = CreateTree( a, n, invalid, ++index );
		}

		return root;							//1.返回值  2.引用  3.二级指针(指针的地址！)
	}

	void _Destroy( Node* root )
	{
		if ( NULL == root )
		{
			return;
		}

		_Destroy( root->_left );
		_Destroy( root->_right );

		delete root;
	}
};


#endif

.cpp:

#include <iostream>
#include <queue>
#include <windows.h>
using namespace std;
#include "BinaryTree.h"


template <typename T>
bool IsCompleteBinaryTree( BinaryTreeNode<T>* root )
{
	if ( NULL == root )							//空树为完全二叉树
		return true;

	queue<BinaryTreeNode<T>*> q1;
	queue<BinaryTreeNode<T>*> q2;

	bool flag = true;

	size_t size1 = 0;

	q1.push( root );

	while ( 1 )
	{
		size1 = q1.size( );

		while ( 0 != q1.size( ) )				//队列1中还有节点
		{
			BinaryTreeNode<T>* tmp;
			tmp = q1.front( );

			if ( NULL == tmp->_left && NULL != tmp->_right )//左孩子为空,右孩子不为空,直接返回false
				return false;

			if ( NULL != tmp->_left )
			{
				if ( false == flag )
					return false;

				q2.push( tmp->_left );
			}

			if ( NULL != tmp->_right )
			{
				if ( false == flag )
					return false;

				q2.push( tmp->_right );
			}

			if ( NULL == tmp->_left && NULL == tmp->_right )//可能有这种情况,某一结点的两个孩子都为空,但下一个节点有孩子。这种情况下这棵树已经不是完全二叉树，而这步操作可以检测这种情况
				flag = false;

			q1.pop( );
		}

		size_t size2 = q2.size( );

		if ( size2 != 2 * size1 )
		{
			while ( 0 != q2.size( ) )
			{
				BinaryTreeNode<T>* node = q2.front( );

				if ( NULL != node->_left || NULL != node->_right )
					return false;

				q2.pop( );
			}

			return true;
		}

		while ( 0 != q2.size( ) )
		{
			q1.push( q2.front( ) );

			q2.pop( );
		}
	}
}


bool IsCompleteTree( BinaryTreeNode<int>* root )
{
	if ( NULL == root )
		return true;

	queue<BinaryTreeNode<int>*> q;
	q.push( root );

	bool exits = true;

	while ( !q.empty( ) )
	{
		BinaryTreeNode<int>* front = q.front( );

		q.pop( );

		if ( NULL != front->_left )
		{
			if ( false == exits )
				return false;

			q.push( front->_left );
		}
		else
			exits = false;
		
		if ( NULL != front->_right )
		{
			if ( false == exits )
				return false;

			q.push( front->_right );
		}
		else
			exits = false;
	}

	return true;
}


void Test1( )
{
	//int array [10] = {1, 2, 3, '#', '#', 4, '#' , '#', 5, 6};
	//int array[15] = {1,2,'#',3,'#','#',4,5,'#',6,'#',7,'#','#',8};
	int array[11] = { 3, 4, '#', '#', 5, 6, '#', '#', 7, '#', '#' };
	BinaryTree<int> t( array, sizeof(array)/sizeof(array[0]), '#' );

	BinaryTreeNode<int>* root = t.GetRoot( );

	cout << IsCompleteBinaryTree( root ) << endl;
}


void Test2( )
{
	//int array [10] = {1, 2, 3, '#', '#', 4, '#' , '#', 5, 6};
	//int array[15] = {1,2,'#',3,'#','#',4,5,'#',6,'#',7,'#','#',8};
	int array[11] = { 3, 4, '#', '#', 5, 6, '#', '#', 7, '#', '#' };
	BinaryTree<int> t( array, sizeof(array)/sizeof(array[0]), '#' );

	BinaryTreeNode<int>* root = t.GetRoot( );

	cout << IsCompleteBinaryTree( root ) << endl;
}


int main( )
{
	//Test1( );
	Test2( );

	system( "pause" );
	return 0;
}

方法一较麻烦，列举各种情况

方法二 简单便捷