链式结构二叉树(递归暴力美学)

1. 链式结构二叉树

完成了顺序结构二叉树的代码实现，可以知道其底层结构是类似顺序表的结构；
因此，链式结构的二叉树类似于链表结构。

二叉树的结构一般由指数据域和左右指针域这三个域组成。

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data; //当前结点数据域
	struct BinaryTreeNode* left; //指向当前结点左孩⼦
	struct BinaryTreeNode* right; //指向当前结点右孩⼦
}BTNode;

1.1 二叉树创建

由于二叉树的代码实现过于复杂，因此这里采用手动创建一棵链式二叉树方便后续思路的代码实现。

单独封装一个函数可用来申请结点(和链表一样)；
手动创建多个结点，并让其形成一棵二叉树。

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	//malloc成功
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
//手动构造一颗二叉树
BTNode* CreaterTree()
{
	BTNode* newnodeA = BuyNode('A');
	BTNode* newnodeB = BuyNode('B');
	BTNode* newnodeC = BuyNode('C');
	BTNode* newnodeD = BuyNode('D');
	BTNode* newnodeE = BuyNode('E');
	BTNode* newnodeF = BuyNode('F');

	newnodeA->left = newnodeB;
	newnodeA->right = newnodeC;
	newnodeB->left = newnodeD;
	newnodeC->left = newnodeE;
	newnodeC->right = newnodeF;
	return newnodeA;
}

2. 前中后序遍历

既然是二叉树，那必然也离不开遍历。因此，我们有多种遍历方式。

2.1 遍历规则

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前
   访问顺序为：根结点、左子树、右子树（简称：根、左、右）
2. 中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）
   访问顺序为：左子树、根结点、右子树（简称：左、根、右）
3. 后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后
   访问顺序为：左子树、右子树、根结点（简称：左、右、根）

以前序遍历为例如下图所示：
遵循前序遍历的规则：
1 先是访问A结点，然后进入左子树；
2. 在左子树中访问B根结点，进入B结点的左子树；
3. 在左子树中访问D根结点，而D中没有左子树和右子树，返回访问B的右子树；
4. B的右子树不存在，返回访问A的右子树；
5. 在右子树中访问C根结点，进入C结点的左子树；
6. 在左子树中访问E根结点，而E中没有左子树和右子树，返回访问C的右子树；
7. 在右子树中访问F根结点，F中没有左子树和右子树，遍历结束。

因此，前序遍历出来的数据是： A B D NULL NULL NULL C E NULL NULL F NULL NULL （NULL表示空）。

2.2 代码实现

为了方便理解，建议看完此二篇。
函数栈帧的创建和销毁.

函数递归的理解 <-- 详见此文

//前序遍历 --- 根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(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);
}

3. 结点个数以及高度等

二叉树结点个数

错误示例1：

int BinaryTreeSize(BTNode* root)
{
	static int size = 0;
	if (root == NULL)
	{
		return 0;
	}
	++size;
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);
	return size;
}

我们开始的想法是通过调用该函数，在里面通过变量size计数，但每次递推调用函数的时候size又会重新置为0，因此我们又考虑用static修饰size延长其生命周期，使得每次递推的时候都能使size保存上一个函数调用的值，最后返回size的值得到该二叉树的结点个数。

但是，这明显存在一个错误，如果我们再次计算这个二叉树结点个数会出现什么情况？

我们打断点调试会发现size的值是从6开始的，这是为什么呢？
很明显，size被static修饰延长了生命周期，使得该变量不再是因为栈空间的结束而销毁。因此，该做法是不可取的。

错误示例2：

void BinaryTreeSize(BTNode* root, int* psize)
{
	if (root == NULL)
	{
		return 0;
	}
	++(*psize);
	BinaryTreeSize(root->left,psize);
	BinaryTreeSize(root->right,psize);
}

既然我们不能从函数内部计数，那么我们是否能在函数外部定义指针变量size(要使得形参的改变能影响实参)来计数呢？
虽然解决了生命周期被延长的做法，但下次调用函数依旧会出现问题，还是因为size没有从0开始(需要手动置为0)。

正确做法：

// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

深刻理解了递归和栈帧空间的创建销毁思想后，一棵二叉树是由根结点、左子树和右子树组成的，那么计算结点个数自然而然就是 1 + 左子树 + 右子树。

4. 层序遍历

建议看完此篇。
栈和队列 <-- 详见此文

层序遍历：从所在二叉树的根结点出发，先访问第⼀层的树根结点，然后从左到右访问第2
层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程。

实现层序遍历需要额外借助数据结构：队列

1. 将二叉树的根节点传给队列(队列可根据根节点找到左子树和右子树);
2. 取队头元素并打印，同时删除队头元素；
3. 若存在左孩子或右孩子，依次入队列；
4. 继续取队头元素并打印，删除队头元素同时将队头的左孩子和右孩子入队列(存在情况下);
5. 如此循环下去，直到队列为空完成了层序遍历。

// 层序遍历
void LevelOrder(BTNode* root)
{
	//借助数据结构--队列
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", top->data);
		//队头左右孩子入队列(不为空)
		if (top->left)
		{
			QueuePush(&q, top->left);
		}
		if (top->right)
		{
			QueuePush(&q, top->right);
		}
	}
	QueueDestroy(&q);
}

5. 判断是否完全二叉树

非完全二叉树：

完全二叉树：

// 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			break;
		}
		//把不为空的队头节点的左右孩子入队列
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	//队列不一定为空，继续取队头出队头
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}