二叉樹

二叉樹的存盤結構

1、順序存盤：用陣列來存盤，只適用于完全二叉樹（堆），因為會存在空間浪費，現實中只有堆才會用陣列來存盤，二叉樹順序存盤在物理上是陣列，在邏輯上是一顆二叉樹，
2.鏈式存盤：用鏈表來表示一顆二叉樹，

二叉樹的遍歷

四種遍歷順序：
1、前序遍歷 先根遍歷 根 -> 左 -> 右
2、中序遍歷 中根遍歷 左 -> 根 -> 右
3、后序遍歷 后根遍歷 左 -> 右 -> 根
4、層序遍歷

普通二叉樹增刪查改沒有意義，如果是為了存盤資料，用線性表更簡單，二叉樹反而復雜，（極端情況下搜索二叉樹退化效率為O(N)）
哈夫曼樹：哈夫曼編碼 -> 檔案壓縮
搜索樹：AVL樹、紅黑樹(平衡樹)

排序二叉樹增刪查改才有意義

二叉樹的實作

1、表示

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

2、創建結點

BTNode* CreateTreeNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;

}

3、前、中、后序遍歷

遞回呼叫

void PrevOrder(BTNode* root)//前序
{
	if (root == NULL)
	{
		printf("NULL");
		return ;
	}
	printf("%c", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
void InOrder(BTNode* root)//中序
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	InOrder(root->left);
	printf("%c", root->data);
	InOrder(root->right);
}
void PostOrder(BTNode* root)//后序
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c", root->data);
}

4、求樹結點的個數

int TreeSize(BTNode* root)//樹結點的個數
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

分治演算法：分而治之
把大問題拆成小問題
思路：
1、空 ：回傳0；
2、非空 ：左子樹結點個數 + 右結點個數 + 1（自己）

5、求葉子結點個數

思路：
1、空 ：回傳0
2、葉子 ：回傳1
3、非空且不是葉子 ：回傳左子數葉子結點個數+右子樹結點個數

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);
}

7、求第K層葉子結點個數

思路：
求第K層個數，轉化為求K-1層個數
K-> K-1 -> K-2 ->… -> 2 -> 1 ->回傳個數

int TreeKLevelSize(BTNode* root, int k)//第K層葉子結點個數
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeKLevelSize(root->left, k - 1) + 
		   TreeKLevelSize(root->right, k - 1);

}

8、找結點

思路：
1、root == NULL return NULL
2、root 結點不是我們要找的，先去左樹找，如果左樹沒有，再到右樹找
3、左右都沒有，當前樹沒有，return NULL

BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	//我自己不是
	if (root->data == x)
		return root;
	//分別到左右子樹尋找
	BTNode* lret = TreeFind(root->left,x);
	if (lret)
		return lret;
	 BTNode* rret = TreeFind(root->right,x);
	if (rret)
		return rret;
	//左右都沒找到
	return NULL;
}

9、銷毀

void BinaryTreeDestoty(BTNode** proot)//后序銷毀
{
	//
	if (*proot == NULL)
		return;
	BinaryTreeDestoty(&(*proot)->left);
	BinaryTreeDestoty(&(*proot)->right);
	free(*proot);
	*proot = NULL;

}

二叉樹的前、中、后序就是深度優先遍歷

廣度優先遍歷

思路：
1、先把根入佇列
2、出隊頭的資料，把它的下一層入隊

特點：借助佇列先進先出的性質，
上一層出隊，下一層入隊

void TreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
	{
		QueuePush(&q, root->data);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c", front->data);
		if (front->left)
			QueuePush(&q, front->left->data);
		if (front->right)
			QueuePush(&q, front->right->data);
	}

	QueueDestroy(&q);
}

10、判斷是否為完全二叉樹

bool BinaryTreeCompelet(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root->data);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
			break;
		QueuePush(&q, front->left->data);
		QueuePush(&q, front->right->data);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
			return false;
	}
	QueueDestroy(&q);
	return true;
}

注：佇列的函式在另一篇博客：佇列