【数据结构】——二叉树功能-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】——二叉树功能。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

【数据结构】——二叉树功能,数据结构,数据结构,开发语言

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

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

前序遍历：

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