按先序遍历建立链式存储结构的二叉树，设计算法判断输入的二叉树是否为满二叉树。

按先序遍历建立链式存储结构的二叉树，设计算法判断输入的二叉树是否为满二叉树。

按先序遍历建立链式存储结构的二叉树，设计算法判断输入的二叉树是否为满二叉树。

【输入形式】按先序遍历序列输入二叉树的结点信息（顶点名称均为单一小写字母，且不存在重复，#表示空）

【输出形式】若为满二叉树则输出1，否则输出0

【样例输入】abc##d##e#f##
此满二叉树为国内定义的满二叉树

#include
#include
#include
using namespace std;
#define MAXSIZE 100

typedef struct bitnode
{
	char data;
	struct bitnode* lchild, * rchild;
}bitnode, * bitree;

void create(bitree& t)//先序遍历创建二叉树
{
	char ch;
	cin >> ch;
	if (ch == '#')
		t = NULL;
	else
	{
		t = new bitnode;
		t->data = ch;
		create(t->lchild);
		create(t->rchild);
	}
}

void height(bitree& T,int &h)	//判断树的高度
{
	if (T)
	{
		h++;
		height(T->lchild,h);
	}
}

void node(bitree& T, int &sum)//先序遍历判断结点数目
{
	if (T)
	{
		sum++;
		node(T->lchild, sum);
		node(T->rchild, sum);
	}
}
int main()
{
	bitree T;
	
	int h = 0, sum = 0;
	create(T);
	height(T,h);
	node(T, sum);
	h = pow(2, h) - 1;
	if (h == sum)
		cout << 1 << endl;
	else
		cout << 0 << endl;
	return 0;
}