#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "queue.h"
#include <string.h>
typedef char BTDatatype;

typedef struct BinaryTreeNode {
	BTDatatype data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;


BTNode* BuyNode(BTDatatype x)
{
	BTNode* temp = (BTNode*)malloc(sizeof(BTNode));
	if (temp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	temp->data = x;
	temp->left = temp->right = NULL;
	return temp;
}


//二叉树中的普通树一般不作为数据存储，因为太复杂还不如用之前简单的结构
//故二叉树的学习主要学习结构

//前序遍历（先根遍历）
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

//中序遍历（中根遍历）
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

//后序遍历（后根遍历）
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

//求树的节点数
//int count = 0;
//void TreeSize(BTNode* root)
//{
//	//方法一，遍历，利用多引用一个count变量来记录，或者全局变量,但是会累加，需要把count每次赋值0；
//	if (root == NULL)
//		return;
//	count++;
//	TreeSize(root->leftNode);
//	TreeSize(root->rightNode);
//	 
//}
 



//方法二，分治
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
	//后序法
}


//求树的叶子节点数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);

	//不能三目运算符，因为有两个条件,因为中间可能有单个空节点，那么就会访问空节点的左右节点
	//return root->leftNode == NULL && root->rightNode == NULL? 1:TreeLeafSize(root->leftNode) + TreeLeafSize(root->rightNode)
}

//求第k层的节点数，第一层的k是第二层的k-1，当k = 1时就是本层
int TreekSize(BTNode* root,int k)
{	
	assert(k >= 1);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreekSize(root->left, k - 1) + TreekSize(root->right, k - 1);

	
}

//求树的深度，（满二叉树是N = (2^h)-1，故满二叉树的高度为logN+1）,但普通二叉树树高度不确定
int TreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

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



//这是错误的写法，只是判断了没有右边单节点的树而已，正确的应该是层序遍历的方法
// 
// 如都是2度的节点，但是空了空，不连续就不是完全二叉树
////判断是否为完全二叉树，空树也是完全二叉树，只需要找到，左为空，右不为空即可
//int BinaryTreeComplete(BTNode* root)
//{
//    if (root == NULL)
//        return 1;
//    if (root->_left == NULL && root->_right != NULL)
//        return 0;
//
//    if (BinaryTreeComplete(root->_left) == 0)
//        return 0;
//    return BinaryTreeComplete(root->_right);
//
//    //这个合并也可
//    //return BinaryTreeComplete(root->_left) && BinaryTreeComplete(root->_right);
//



//判断完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	//利用层序遍历，遇到空之后看，其后面是否全是空
	//因为当遍历到第n层的时候，n-1层已经全部把子节点入列了，那么剩下的是否连续就可以判断了

	Queue s;
	QueueInit(&s);
	if (root)
		QueuePush(&s, root);
	while (!QueueEmpty(&s))
	{
		BTNode* temp = QueueFront(&s);
		QueuePop(&s);


		if (temp == NULL)
			break;
			
		//当temp出到是空的时候就可以退出了，然后在判断
		QueuePush(&s,temp->left);
		QueuePush(&s,temp->right);
	}
	while (!QueueEmpty(&s))
	{
		BTNode* temp = QueueFront(&s);
		QueuePop(&s);
		if (temp != NULL)
		{
			QueueDestroy(&s);//先销毁队列再返回，不然没出完队列就内存泄露了
			return 0;
		}
			
	}
	QueueDestroy(&s);
	return 1;


}



// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDatatype* a, int n, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		printf("NULL ");
		return NULL;
	}
	else
	{
		BTNode* root = BuyNode(a[(*pi)++]);
		printf("%d ", root->data);
		root->left = BinaryTreeCreate(a, n, pi);
		root->right = BinaryTreeCreate(a, n, pi);
		return root;
	}
	printf("\n");
}


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

	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}



//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue s;
	QueueInit(&s);//创建并初始化队列

	if (root)
		QueuePush(&s, root);
	while (!QueueEmpty(&s))
	{
		BTNode* temp = QueueFront(&s);//这里拿出来的是QNode的值，也就是BTNode*的节点 
		QueuePop(&s);

		printf("%d ", temp->data);
		if (temp->left)
		{
			QueuePush(&s, temp->left);
		}
		if (temp->right)
			QueuePush(&s, temp->right);
	}

	printf("\n");
	QueueDestroy(&s);
}


BTNode* BinaryTreeFind(BTNode* root, BTDatatype x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;


	//先找左边，左边存在直接返回，不存在再找右边
	BTNode* set = BinaryTreeFind(root->left, x);
	if (set)
		return set;

	return BinaryTreeFind(root->right, x);
}







int main()
{
	char* a = "123##4##67##8##";
	int i = 0;
	BTNode* root = BinaryTreeCreate(a, strlen(a), &i);
	printf("\n");

	printf("层序：");
	BinaryTreeLevelOrder(root);



	printf("前序：");
	PrevOrder(root);
	printf("\n");

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

	printf("后序：");
	PostOrder(root);


	printf("\n");
	for (int i = 49; i < 58; i++)
	{
		BTNode* ret = BinaryTreeFind(root,i);
		printf("%d 的地址是%p\n", i, ret);
	}


	printf("是否完全二叉树：");
	printf("%d\n", BinaryTreeComplete(root));
	return 0;
}