判斷是否是完全二叉樹和是否為滿二叉樹

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;
	}
}