[数据结构与算法]关于二叉树的常问问题

节点定义

typedef char ElemType;

typedef struct BtNode
{
	ElemType data;
	struct BtNode* leftchild;
	struct BtNode* rightchild;
}BtNode,*BinaryTree;

如何判断二叉树是满二叉树

描述：对于满二叉树来说，它的每一层节点的个数都是2的幂次方个，那么我们就可以利用这个特点，使用两个队列，在每一次入队完之后，判断一次队中的个数是否达到了当前的2的幂次方个，如果达到了，则继续入队判断下一层；若没有达到，则程序退出，不是满二叉树。（为了确定到哪一层，我们可以定义一个常量s,赋初始值为1，在每一次入队完成之后，都使它加加自身，同样可以达到2的幂次方增长）

bool FuntwoTree(BtNode* ptr)
{
	if (ptr == NULL)return false;
	int s = 1;
	queue<BtNode*>qu1;
	queue<BtNode*>qu2;
	qu1.push(ptr);
	bool tag = true;
	while (!qu1.empty() || !qu2.empty())
	{
		if (s != qu1.size())
		{
			tag = false;
			break;
		}
		while (!qu1.empty())
		{
			ptr = qu1.front(); qu1.pop();
			if (ptr->leftchild != NULL)qu2.push(ptr->leftchild);
			if (ptr->rightchild != NULL)qu2.push(ptr->rightchild);
		}
		s += s;
		if (s != qu2.size())
		{
			tag = false;
			break;
		}
		while (!qu2.empty())
		{
			ptr = qu2.front(); qu2.pop();
			if (ptr->leftchild != NULL)qu1.push(ptr->leftchild);
			if (ptr->rightchild != NULL)qu1.push(ptr->rightchild);
		}
		s += s;
	}
	return tag;
}

如何判断二叉树是完全二叉树

? 描述：完全二叉树指的是除最后一层之外，其它层都是满的，并且最后一层的缺省节点是从左到右依次缺省的。那么在判断时，我们可以将每一层的节点依次入队列，直到入完为止。因为入队时，我们是从左到右依次入的，那么对于完全二叉树来说，当一个节点为空时，它后边的节点就全为空了，此时我们检查它后边的节点，如果发现有一个不为空，那么此树就不是完全二叉树。

代码实现：

bool Is_ComBintaryTree(BtNode* ptr)
{
	bool tag = true;
	if (ptr == NULL)return tag;
	queue<BtNode*>qu;
	qu.push(ptr);
	while (!qu.empty())
	{
		ptr = qu.front(); qu.pop();
		if (ptr == NULL)break;
		qu.push(ptr->leftchild);
		qu.push(ptr->rightchild);
	}
	while (!qu.empty())
	{
		if (qu.front())
		{
			tag = false;
			return false;
		}
		qu.pop();
	} 
	return tag;
}