判断是否是完全二叉树和是否为满二叉树

struct Node
{
	char data;
	Node *lchild,*rchild;
	Node(char _data)
	{
		data = _data;
	}
};
           

是否为完全二叉树：

bool isCompleteBinaryTree(Node *root)
{
	if(root == NULL)
	{
		return true;
	}
	queue<Node*>q;
	q.push(root);
	Node *p;
	//先用层次遍历二叉树,子树为NULL也进队列 
	while((p = q.front()) != NULL)//如果是完全二叉树，退出此循环后，后面的结点应该都是NULL
	{//因为本循环会在层次遍历到第一个NULL结点退出 
		q.push(p->lchild);
		q.push(p->rchild);
		q.pop();
	}
	//如果不是完全二叉树，则队列里还有非NULL结点 
	while(q.empty() == false)	//检查是否有非空结点 
	{
		p = q.front();
		if(p != NULL)		//有 
		{
			return false;
		}
		q.pop();
	}
	return true;
} 
           

是否为满二叉树：

bool isFullBinaryTree(Node *root)
{
	if(root->lchild != NULL && root->rchild != NULL)
	{
		return isFullBinaryTree(root->lchild) && isFullBinaryTree(root->rchild); 
	}
	if(root->lchild == NULL && root->rchild != NULL)
	{
		return false;
	}
	else if(root->rchild && root->lchild != NULL)
	{
		return false;
	}
	else 
	{
		return true;
	}
}