【数据结构】树形结构--二叉树（二）

一.二叉树的实现

二叉树的介绍以及各种遍历在上篇文章有讲，可以先回顾一下再继续后面的学习 【数据结构】树形结构–二叉树。

1.求二叉树结点的个数

二叉树结点个数即：左子树结点个数加上右子树结点个数再加上根结点，这里就用到了分治思想和递归。

分治思想：
①分解：将一个大问题拆解成多个相似的子问题。
②解决：递归解决子问题，子问题足够小时，直接解决。
③合并：将子问题的解合并得到大问题的解。

因此当结点为空时直接返回0，然后递归计算左子树的结点，加上递归计算出的右子树的结点，再加上根结点的个数，即为二叉树的结点个数。
代码实现为：

//求二叉树结点个数
//分治思想
int BinaryTreeSize(BTNode* root)
{
	//采用三目表达式，结点为空直接返回，否则递归计算左右子树个数及根结点。
	return root == NULL ? 0 : BinaryTreeSize(root->leftchild) + BinaryTreeSize(root->rightchild) + 1;
}

2.求二叉树叶子结点的个数

求二叉树的叶子结点个数需要先判断是否为叶子结点，即没有左、右孩子的结点，满足条件则返回1，不满足返回0，然后递归计算左子树叶子结点个数和右子树叶子结点个数。
代码实现为：

//求二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->leftchild==NULL&&root->rightchild==NULL)
		return 1;

	return BinaryTreeLeafSize(root->leftchild) + BinaryTreeLeafSize(root->rightchild);
}

3.求二叉树第k层结点的个数

在求二叉树第k层结点个数时，形参除了传二叉树根结点，还需要传k的值，这样在函数中递归进入下一层时，再将k-1作为参数传递。
当k等于1且结点不为空时，当前层数即为第k层，返回1，同时使用分治思想计算左子树第k层结点个数和右子树结点个数，最后得到第k层结点个数。
代码实现为：

//求二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->leftchild, k-1) + BinaryTreeLevelKSize(root->rightchild, k-1);
}

4.求二叉树的深度（高度）

二叉树的深度是左、右子树中深度最大的那个，因此可以先递归计算出左子树的高度和右子树的高度，较大的高度再加上1（根结点），即为二叉树的高度。
代码实现为：

//求二叉树的深度（高度）
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftdepth = BinaryTreeDepth(root->leftchild);
	int rightdepth = BinaryTreeDepth(root->rightchild);
	return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
}

5.在二叉树中查找值为x的结点

可以借助前、中、后序遍历或层序遍历的方式依次遍历所有结点的值，若结点值为x，则返回该结点，若遍历完不存在值为x的结点，则返回空。
代码实现为：

//在二叉树中查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	BTNode* left = BinaryTreeFind(root->leftchild,x);
	if (left)
		return left;

	BTNode* right = BinaryTreeFind(root->rightchild,x);
	if (right)
		return right;

	return NULL;
}

6.判断二叉树是否为完全二叉树

判断二叉树是否为完全二叉树需要先了解完全二叉树的特点。
完全二叉树的定义是：除最后一层外，其余各层都是满的，并且最后一层的节点都集中在最左边。
因此可以借助队列层序遍历二叉树，循环将二叉树的结点入队列、出队列，当出队列的结点为空时停止循环，然后再循环出队列判断，若所有结点都出队列前遇到非空结点，则不是完全二叉树，否则是完全二叉树。
示意图：

代码实现为：

//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
		return true;
	QueuePush(&q,root);
	while (QueueSize(&q))
	{
		BTNode* tmp = QueueFront(&q);
		QueuePop(&q);
		if (tmp == NULL)
			break;

		QueuePush(&q,tmp->leftchild);
		QueuePush(&q, tmp->rightchild);
	}
	while (QueueSize(&q))
	{
		BTNode* tmp = QueueFront(&q);
		if (tmp != NULL)
			return false;
	}
	return true;
}

7.二叉树的销毁

二叉树的销毁需要根据左->右->根的顺序递归销毁每个结点，否则根结点在左、右孩子之前销毁的话就找不到左右结点了。
代码实现为：

//二叉树的销毁
void BinaryTreeDestory(BTNode** root)
{
	//根据 左->右->根 的顺序销毁二叉树
	if (*root == NULL)
		return;

	 BinaryTreeDestory(&(*root)->leftchild);
	 BinaryTreeDestory(&(*root)->rightchild);
	
	free(*root);
	*root = NULL;

}

二叉树的链式实现和各个操作就先讲到这里，感谢阅读！^ _ ^