#include<stdio.h>  // perror, printf
#include<stdlib.h> // malloc
typedef char BTDataType;
// 定義二叉樹的節(jié)點(diǎn)
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
// 動(dòng)態(tài)申請一個(gè)新節(jié)點(diǎn)
BTNode* BuyNode(BTDataType x)
{
	// 
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}
// 二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)
BTNode* CreatBinaryTree()
{
	// 創(chuàng)建多個(gè)節(jié)點(diǎn)
	BTNode* node_A = BuyNode('A');
	BTNode* node_B = BuyNode('B');
	BTNode* node_C = BuyNode('C');
	BTNode* node_D = BuyNode('D');
	BTNode* node_E = BuyNode('E');
	BTNode* node_F = BuyNode('F');
	// 用鏈來指示節(jié)點(diǎn)間的邏輯關(guān)系
	node_A->left = node_B;
	node_A->right = node_C;
	node_B->left = node_D;
	node_C->left = node_E;
	node_C->right = node_F;
	return node_A;
}

// 二叉樹前序遍歷
void PreOrder(BTNode* root)
{
	if (root) // 先判斷樹是否為空
	{
		// 根 --> 左子樹 --> 右子樹
		printf("%c ", root->data);
		PreOrder(root->left);
		PreOrder(root->right);
	}
}
int main()
{
	// 創(chuàng)建一顆鏈?zhǔn)蕉鏄?
	BTNode* root = CreatBinaryTree();
	// 前序遍歷
	PreOrder(root); // A B D C E F
    return 0;
}

// 二叉樹中序遍歷
void InOrder(BTNode* root)
{
	if (root) // 先判斷樹是否為空
	{
		// 左子樹 --> 根 --> 右子樹
		InOrder(root->left);
		printf("%c ", root->data);
		InOrder(root->right);
	}
}

// 二叉樹后序遍歷
void PostOrder(BTNode* root)
{
	if (root) // 先判斷樹是否為空
	{
		// 左子樹 --> 右子樹 --> 根
		PostOrder(root->left);
		PostOrder(root->right);
		printf("%c ", root->data);
	}
}

// 二叉樹的層序遍歷
void LevelOrder(BTNode* root)
{
	LinkQueue q; // 鏈?zhǔn)疥?duì)列
	QueueInit(&q); // 初始化隊(duì)列
	// 樹的根節(jié)點(diǎn)root不為空，把根節(jié)點(diǎn)入隊(duì)
	if (root)
	{
		QueuePush(&q, root);
	}
    // 當(dāng)隊(duì)列不為空時(shí)，不斷的出隊(duì)，以及入隊(duì)根節(jié)點(diǎn)root的左右子樹
	while (!QueueEmpty(&q))
	{
		// 當(dāng)前樹的根節(jié)點(diǎn)出隊(duì)
		BTNode* front = QueueFront(&q); // 獲取隊(duì)頭元素 
		printf("%c ", front->data);     // 打印節(jié)點(diǎn)值
		QueuePop(&q);                   // 出隊(duì)
		// 如果當(dāng)前樹根的左右孩子不為空，則分別入隊(duì)
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestroy(&q); // 銷毀隊(duì)列
}

// 二叉樹節(jié)點(diǎn)個(gè)數(shù)
/* 方法一：
1、遞歸遍歷 -- 用全局變量/靜態(tài)局部變量來記錄節(jié)點(diǎn)個(gè)數(shù)
2、遞歸遍歷 -- 函數(shù)外定義一個(gè)局部變量記錄節(jié)點(diǎn)個(gè)數(shù)，傳址給函數(shù)
*/
// 方法二：分而治之的思路
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL) // 1. 先判斷當(dāng)前訪問的節(jié)點(diǎn)是否為空
	{
		return 0;
	}
	// 2. 當(dāng)前節(jié)點(diǎn)不為空，節(jié)點(diǎn)個(gè)數(shù)累+1，則繼續(xù)訪問其左右子樹
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

// 二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
/* 方法一：
1、遞歸遍歷 -- 用全局變量/靜態(tài)局部變量來記錄節(jié)點(diǎn)個(gè)數(shù)
2、遞歸遍歷 -- 函數(shù)外定義一個(gè)局部變量記錄節(jié)點(diǎn)個(gè)數(shù)，傳址給函數(shù)
*/
// 方法二：分而治之的思路
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL) // 1. 先判斷當(dāng)前訪問的節(jié)點(diǎn)是否為空
	{
		return 0;
	}
	// 2. 當(dāng)前節(jié)點(diǎn)不為空，它的左右孩子都為空，說明該節(jié)點(diǎn)是葉子節(jié)點(diǎn)
    if (root->left == NULL && root->right == NULL) 
	{
		return 1;
	}
	// 3. 當(dāng)前節(jié)點(diǎn)不為空，左右孩子不都為空，則繼續(xù)往下遍歷
	return BinaryTreeLeafSize(root->left) 
		+ BinaryTreeLeafSize(root->right);
}

// 二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL) // 1. 先判斷當(dāng)前訪問的節(jié)點(diǎn)是否為空
	{
		return 0;
	}
	if (k == 1) // 2. 當(dāng)前節(jié)點(diǎn)不為空，而k已經(jīng)減到1了，說明遍歷到了第k層，說明該節(jié)點(diǎn)是第k層的
	{
		return 1;
	}
	// 3. 還沒有遍歷到第k層，我們就繼續(xù)往下遍歷
	return BinaryTreeLevelKSize(root->left, k - 1)
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

// 二叉樹的深度(高度)
int BinaryTreeDepth(BTNode* root)
{
    // 1. 先判斷當(dāng)前樹的根節(jié)點(diǎn)是否為空
	if (root == NULL)
	{
		return 0;
	}
	// 2. 當(dāng)前樹的根節(jié)點(diǎn)不為空，分別計(jì)算其左右子樹的深度
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);
	// 3. 比較當(dāng)前樹左右子樹的深度，最大的那個(gè)+1 就是當(dāng)前樹的深度
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

// 二叉樹查找值為x的節(jié)點(diǎn)，若有則返回該節(jié)點(diǎn)的地址，若沒有則返回NULL
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL) // 1. 先判斷當(dāng)前訪問的節(jié)點(diǎn)是否為空
	{
		return NULL;
	}
	if (root->data == x) // 2. 判斷要找的x值節(jié)點(diǎn)是不是當(dāng)前節(jié)點(diǎn)
	{
		return root;
	}
	// 3. 不是當(dāng)前節(jié)點(diǎn)，則繼續(xù)去該節(jié)點(diǎn)的左子樹中找
	BTNode* ret = BinaryTreeFind(root->left, x);
	if (ret != NULL)
	{
		return ret; // 找到了返回地址
	}
	// 3. 還沒找到，再繼續(xù)去該節(jié)點(diǎn)的右子樹中找
	ret = BinaryTreeFind(root->right, x);
	if (ret != NULL)
	{
		return ret; // 找到了返回地址
	}
	// 4. 當(dāng)前節(jié)點(diǎn)及其左右子樹中都沒找到，返回NULL
	return NULL;
}

// 通過前序遍歷的字符串?dāng)?shù)組arr "ABD##E#H##CF##G##" 構(gòu)建二叉樹
BTNode* BinaryTreeCreate(BTDataType* arr, int size, int* pi);

// 二叉樹銷毀
// 一級(jí)指針(頭節(jié)點(diǎn)指針)，形參是實(shí)參的一份拷貝，函數(shù)內(nèi)改變形參的值，無法改變外部實(shí)參的值
// 所以我們需要在函數(shù)外置頭節(jié)點(diǎn)指針為NULL
void BinaryTreeDestroy(BTNode* root)
{
	// 不建議使用前中序遍歷銷毀，如果節(jié)點(diǎn)先被銷毀，就變成隨機(jī)值了，不知道它的左右子樹位置了
	// 所以我們采用后序遍歷銷毀
	if (root)
	{
		BinaryTreeDestroy(root->left);
		BinaryTreeDestroy(root->right);
		free(root);
	}
}
int main()
{
	// 創(chuàng)建一顆鏈?zhǔn)蕉鏄?
	BTNode* root = CreatBinaryTree();
	// 銷毀二叉樹
    BinaryTreeDestroy(root);
	// 頭節(jié)點(diǎn)指針置NULL
    root = NULL;
	return 0;
}

// 判斷二叉樹是否是完全二叉樹（利用層序遍歷的思想來判斷）
bool BinaryTreeComplete(BTNode* root)
{
	LinkQueue q; // 鏈?zhǔn)疥?duì)列
	QueueInit(&q); // 初始化隊(duì)列
	// 樹的根節(jié)點(diǎn)root不為空，把根節(jié)點(diǎn)入隊(duì)
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		// 當(dāng)前樹的根節(jié)點(diǎn)出隊(duì)
		BTNode* front = QueueFront(&q); // 獲取隊(duì)頭元素
		QueuePop(&q);                   // 出隊(duì)
		// @@@ 出隊(duì)的節(jié)點(diǎn)中，出到第一個(gè)空節(jié)點(diǎn)時(shí)，跳出循環(huán) @@@
		if (front == NULL)
		{
			break;
		}
		// 不管當(dāng)前樹根的左右孩子是否為空，都分別入隊(duì)
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	// @@@ 出隊(duì)的節(jié)點(diǎn)中，出到第一個(gè)空節(jié)點(diǎn)時(shí)，跳出上面循環(huán) @@@
	// 在這里繼續(xù)出隊(duì)：
	// 1、如果隊(duì)列中全是空節(jié)點(diǎn)，則是完全二叉樹
	// 2、如果隊(duì)列中有非空節(jié)點(diǎn)，則是非完全二叉樹
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q); // 獲取隊(duì)頭元素
		QueuePop(&q);                   // 出隊(duì)
		// @@@ 出隊(duì)的節(jié)點(diǎn)中，如果出現(xiàn)非空節(jié)點(diǎn)，說明是非完全二叉樹 @@@
		if (front)
		{
			QueueDestroy(&q); // 銷毀隊(duì)列
			return false;
		}
	}
	QueueDestroy(&q); // 銷毀隊(duì)列
	// @@@ 出隊(duì)的節(jié)點(diǎn)中，如果沒有出現(xiàn)非空節(jié)點(diǎn)，說明是完全二叉樹 @@@
	return true;
}