【题目要求】

设计算法判断一棵树是否为完全二叉树。

【提示】

根据完全二叉树的定义可知：

1）如果一个结点有右孩子而没有左孩子，那么这棵树一定不是完全二叉树。

2）如果一个结点有左孩子，而没有右孩子，那么按照层序遍历的结果，这个结点之后的所有结点都是叶子结点，这棵树才是完全二叉树。

3）如果一个结点是叶子结点，那么按照层序遍历的结果，这个结点之后的所有结点都必须是叶子结点这棵树才是完全二叉树。

【测试样例】

【输入】

AB#D##C##

【输出】

层序遍历：ABCD

判断是否是完全二叉树：不是

【题解代码】

//借助队列用层序遍历实现
#include<iostream>
#include<queue>
using namespace std;
const int QUEUESIZE = 100;


struct BiNode {
	char data;
	BiNode* lchild, * rchild;
};
class BiTree
{
private:
	BiNode* root;
public:
	BiTree() { root = creat(root); }
	~BiTree() {
		release(root);
	}
	BiNode* getRoot() { return root; }
	BiNode* creat(BiNode* bt); //构造函数调用
	void release(BiNode* bt);  //析构函数调用，释放树的存储空间 
	void leverOrder(BiNode* bt);//层序遍历函数调用
	bool isCompleteBiTree(BiNode* bt);//判断是否为完全二叉树
};

BiNode* BiTree::creat(BiNode* bt)
{
	char ch;
	cin >> ch;

	if (ch == '#')
		bt = NULL;
	else
	{
		bt = new BiNode;
		bt->data = ch;
		bt->lchild = creat(bt->lchild);
		bt->rchild = creat(bt->rchild);

	}
	return bt;
}

void BiTree::release(BiNode* bt)
{
	if (bt != NULL)
	{
		release(bt->lchild);
		release(bt->rchild);
		// cout<<"delete "<<bt->data<<endl;
		delete bt;
	}
}
void BiTree::leverOrder(BiNode* bt)
{
	BiNode* q;
	queue<BiNode*> Q;
	Q.push(root);
	if (root == NULL)
		return;
	while (!Q.empty())
	{
		q = Q.front();
		cout << q->data;
		Q.pop();
		if (q->lchild != NULL)
			Q.push(q->lchild);
		if (q->rchild != NULL)
			Q.push(q->rchild);
	}
}
bool BiTree::isCompleteBiTree(BiNode* bt)
{
	if (bt == NULL)
		return true;
	queue<BiNode*> Q;
	Q.push(bt);
	bool flag = false;
	while (!Q.empty())
	{
		BiNode* node = Q.front();
		Q.pop();
		if (node->lchild)  //如果左孩子存在
		{
			if (flag)     //但是前面有缺失的结点
				return false; //不是完全二叉树
			else          //前面是结点是满的
				Q.push(node->lchild); //把左孩子入队
		}
		else
		{
			flag = true;  //左孩子结点缺失，为了下一次判断需要将flag定为真
		}
		if (node->rchild) //右孩子结点存在
		{
			if (flag)     //前面有缺失的结点
				return false;//不是完全二叉树
			else
				Q.push(node->rchild);//否则，右孩子入队
		}
		else
			flag = true;//右孩子结点缺失，为了下一次判断需要将flag定为真
	}
	return true;
}
int main() {
	BiTree tree;
	cout << "层序遍历：";
	tree.leverOrder(tree.getRoot());
	cout << endl;
	cout << "判断是否是完全二叉树：";
	if (tree.isCompleteBiTree(tree.getRoot()))
		cout << "是" << endl;
	else
		cout << "不是" << endl;

	return 0;
}