【数据结构】——二叉树功能

前言：我们前面已经了解了二叉树的一些概念，那么我们今天就来了解下二叉树的遍历实现和一些性质。

在这里插入图片描述

二叉树的遍历方式有三种：前序，中序，后序。

前序：先根节点，再左子树，最后右子树。
中序：先左子树，再根节点，最后右子树。
后序：先左子树，再右子树，最后根节点。

前序遍历：

void PrevOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

如果我们的根节点为空就返回空，不为空就递归左子树，如果左子树为空就返回递归访问右子树。

中序遍历：

void InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

先访问遍历左子树，再根节点，最后在访问右子树。

后序遍历：

void Tailorder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N");
		return;
	}
	Tailorder(root->left);
	Tailorder(root->right);
	printf("%d", root->data);
}

先遍历左子树，再遍历右子树，最后在根节点。

求二叉树节点个数：

int TreeSize(TreeNode* root)
{
	return root == NULL ? 0 :
		TreeSize(root->left) +
		TreeSize(root->right) + 1;
}

我们递归实现，左子树的节点个数加上右子树的节点个数再加上根节点的个数就是节点的总个数。

求叶子结点的个数：

int TreeLeafSize(TreeNode* root)
{
	// 空 返回0
	if (root == NULL)
		return 0;
	// 不是空，是叶子 返回1
	if (root->left == NULL
		&& root->right == NULL)
		return 1;

	// 不是空 也不是叶子  分治=左右子树叶子之和
	return TreeLeafSize(root->left) +
		TreeLeafSize(root->right);
}

求二叉树的高度：

int TreeHeight(TreeNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

因为我们的递归结合上三目操作符会使得非常的复杂，所以我们用一个数据来保存左右子树的高度，我们的二叉树的高度为左右子树较高的那个子树加上1，所以我们返回的是左右子树高度更高的再加上1就是二叉树的高度。

我们的代码还可以进行改进，我们C语言的fmax函数：该函数的作用是比较两个数得到较大的那一个数

int TreeHeight(TreeNode* root)
{
	if (root == NULL)
		return 0;

	return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}

二叉树查找值为x的节点：

// 二叉树查找值为x的结点
TreeNode* TreeFind(TreeNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	TreeNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;

	TreeNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

销毁二叉树：

void DestroyTree(TreeNode* root)
{
	if (root == NULL)
		return;

	DestroyTree(root->left);
	DestroyTree(root->right);
	free(root);
}

求二叉树第k层节点个数：

int TreeLevelK(TreeNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return TreeLevelK(root->left, k - 1)
		+ TreeLevelK(root->right, k - 1);
}