数据结构之SWUSTOJ972: 统计利用先序遍历创建的二叉树的宽度

题目：

思路：

通过上述图解，我们首先需要先序遍历创建好二叉树，然后我们需要求出这个二叉树的层数k， 然后通过递归到最后一层的时候来计算宽度大小

代码：

#include
using namespace std;
typedef struct BinaryTree
{
	char data;
	struct BinaryTree* leftchild;
	struct BinaryTree* rightchild;
}BT;//创建二叉树的结构体
void BinaryTreePreCreate(BT*& root)
{
	char a;
	cin >> a;
	if (a == '#')
		root = NULL;
	else
	{
		root = (BT*)malloc(sizeof(BT));
		root->data = a;
		BinaryTreePreCreate(root->leftchild);
		BinaryTreePreCreate(root->rightchild);
	}
}//通过先序变量初始化二叉树
int BinaryTreeDepth(BT* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = BinaryTreeDepth(root->leftchild);
	int rightDepth = BinaryTreeDepth(root->rightchild);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}//通过递归分治的思想求二叉树的高度/深度
int Count = 0;//用全局变量记录一下宽度
void BinaryTreeWidth(BT* root, int k)
{
	if (k == 1 && root!=NULL)//如果当k等于1时说明k走到了最后一层，并且最后一层不为空时Count++
	{
		Count++;
		return;
	}
	if (root == NULL)//当root为空时直接返回
	{
		return;
	}
	else
	{
		BinaryTreeWidth(root->leftchild, k - 1);
		BinaryTreeWidth(root->rightchild, k - 1);//不断向下递归
	}
}
int main()
{
	BT* tree;
	BinaryTreePreCreate(tree);
	int k = 0;
	k = BinaryTreeDepth(tree);
	BinaryTreeWidth(tree, k);
	printf("%d", Count);
	return 0;
}