#include "BinaryTree.h"
#include <malloc.h>
#include <stdio.h>
#include <assert.h>

BTNode* BuyBinaryTreeNode(BTDataType data)
{
	BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
	if (NULL == newNode)
	{
		assert(0);
		return NULL;
	}

	newNode->left = NULL;
	newNode->right = NULL;
	newNode->data = data;
	return newNode;
}

// 根据二叉树的概念来进行创建
// 创建根节点
// 创建根的左子树---递归
// 创建根的右子树---递归
BTNode* _CreateBinaryTree(BTDataType array[], int size, int* index, BTDataType invalid)
{
	BTNode* root = NULL;
	if (*index < size && array[*index] != invalid)
	{
		root = BuyBinaryTreeNode(array[*index]);

		++(*index);
		root->left = _CreateBinaryTree(array, size, index, invalid);

		++(*index);
		root->right = _CreateBinaryTree(array, size, index, invalid);
	}

	return root;
}

BTNode* CreateBinaryTree(BTDataType array[], int size, BTDataType invalid)
{
	int index = 0;
	return _CreateBinaryTree(array, size, &index, invalid);
}


void PreOrder(BTNode* root)
{
	// 空树
	if (NULL == root)
		return;

	// 根节点
	printf("%d ", root->data);

	// 递归遍历根的左子树
	PreOrder(root->left);

	// 递归遍历的右子树
	PreOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (NULL == root)
		return;

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (NULL == root)
		return;

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

#include "Queue.h"

void LevelOrder(BTNode* root)
{
	Queue q;
	if (NULL == root)
		return;

	QueueInit(&q);

	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);

		printf("%d ", cur->data);

		if (cur->left)
			QueuePush(&q, cur->left);

		if (cur->right)
			QueuePush(&q, cur->right);
	}

	QueueDestroy(&q);
}


// 获取节点总的个数
int GetSize(BTNode* root)
{
	if (NULL == root)
		return 0;

	return 1 + GetSize(root->left) + GetSize(root->right);
	//return NULL == root ? 0 : 1 + GetSize(root->left) + GetSize(root->right);
}


// 获取叶子节点的个数
int GetLeafNodeCount(BTNode* root)
{
	if (NULL == root)
		return 0;

	if (NULL == root->left && NULL == root->right)
		return 1;

	return GetLeafNodeCount(root->left) + GetLeafNodeCount(root->right);
}


// 获取第k层节点的个数
int GetKLevelNodeCount(BTNode* root, int k)
{
	if (NULL == root || k < 1)
		return 0;

	if (1 == k)
		return 1;

	return GetKLevelNodeCount(root->left, k - 1) +
		GetKLevelNodeCount(root->right, k - 1);
}

// 获取树的高度
int GetHeight(BTNode* root)
{
	if (NULL == root)
		return 0;

	int leftHegiht = GetHeight(root->left);
	int rightHegiht = GetHeight(root->right);
	return leftHegiht > rightHegiht ? leftHegiht + 1 : rightHegiht + 1;
}

// 检测data是否在二叉树中
BTNode* Find(BTNode* root, BTDataType data)
{
	BTNode* ret = NULL;
	if (NULL == root)
		return NULL;

	if (root->data == data)
		return root;

	if (ret = Find(root->left, data))
	{
		return ret;
	}

	return Find(root->right, data);
}

void Destroy(BTNode** root)
{
	assert(root);
	if (*root)
	{
		Destroy(&(*root)->left);
		Destroy(&(*root)->right);
		free(*root);
		*root = NULL;
	}
}


int IsCompleteBinaryTree(BTNode* root)
{
	Queue q;
	int flag = 0;    // 标记：第一个不饱和的节点是否找到
	// 空树也是完全二叉树
	if (NULL == root)
		return 1;

	// 按照层序遍历的方式将二叉树中的节点分两种规则来进行检测
	// 按照层序遍历方式找第一个不满和的节点
	QueueInit(&q);
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);

		if (flag)
		{
			// 不满和的节点应找到了，后序节点就不能有孩子
			if (cur->left || cur->right)
			{
				QueueDestroy(&q);
				return 0;
			}
		}
		else
		{
			// 找第一个不满和的节点
			// cur的左右孩子均存在
			if (cur->left && cur->right)
			{
				QueuePush(&q, cur->left);
				QueuePush(&q, cur->right);
			}
			else if (cur->right)
			{
				// cur只有右孩子，没有左孩子
				QueueDestroy(&q);
				return 0;
			}
			else if (cur->left)
			{
				// cur只有左没有右孩子
				flag = 1;
				QueuePush(&q, cur->left);
			}
			else
			{
				// cur没有孩子
				flag = 1;
			}
		}
	}

	QueueDestroy(&q);
	return flag;
}

void TestBinaryTree()
{
	int array[] = { 1,2,3,-1,-1,-1,4,5,-1, -1, 6 };

	int index = 0;
	BTNode* root = CreateBinaryTree(array, sizeof(array) / sizeof(array[0]), -1);

	printf("层序遍历:");
	LevelOrder(root);


	printf("前序遍历：");
	PreOrder(root);
	printf("\n");

	printf("中序遍历：");
	InOrder(root);
	printf("\n");

	printf("后序遍历：");
	PostOrder(root);
	printf("\n");

	printf("节点总数：%d\n", GetSize(root));
	printf("叶子节点总数：%d\n", GetLeafNodeCount(root));
	printf("第%d层节点总数：%d\n", 2, GetKLevelNodeCount(root, 2));
	printf("树的高度为：%d\n", GetHeight(root));
	if (Find(root, 15))
	{
		printf("15 is in binary tree\n");
	}
	else
	{
		printf("15 is not in binary tree\n");
	}


	if (IsCompleteBinaryTree(root))
	{
		printf("tree is complete tree\n");
	}
	else
	{
		printf("tree is not complete tree\n");

	}

	Destroy(&root);
}