【数据结构】二叉查找树(3)

发布时间：2021-05-22 01:04 所属栏目：53 来源：网络整理

导读：树的遍历有三种：先序、中序和后序。每次遍历子树时，也要相应的按序遍历该子树。 1. 先序遍历：[首先访问根节点]? 先访问根节点，再遍历左子树，最后遍历右子树 2. 中序遍历：[中间访问根节点]? 先遍历左子树，再

树的遍历有三种：先序、中序和后序。每次遍历子树时，也要相应的按序遍历该子树。

1. 先序遍历：[首先访问根节点]? 先访问根节点，再遍历左子树，最后遍历右子树
2. 中序遍历：[中间访问根节点]? 先遍历左子树，再访问根节点，最后遍历右子树
3. 后序遍历：[最后访问根节点]? 先遍历左子树，再遍历右子树，最后访问根节点

如下所示：

/*
*              6             先序遍历： 6 2 1 4 3 8 10
*             / \                      
*            2   8           中序遍历： 1 2 3 4 6 8 10
*           / \   \       
*          1   4   10        后序遍历： 1 3 4 2 10 8 6
*             /                           
*            3                           
*/

从上得知，中序遍历二叉查找树时正好是排序好的数据。

/*先序遍历*/
void printPreorder(BinaryTree *pBinaryTree)
{
	if (NULL != pBinaryTree)
	{
		printf("%d\n",pBinaryTree->value);
		printPreorder(pBinaryTree->left_child);
		printPreorder(pBinaryTree->right_child);
	}
}

/*中序遍历*/
void printInorder(BinaryTree *pBinaryTree)
{
	if (NULL != pBinaryTree)
	{
		printInorder(pBinaryTree->left_child);
		printf("%d\n",pBinaryTree->value);
		printInorder(pBinaryTree->right_child);
	}
}

/*后序遍历*/
void printPostorder(BinaryTree *pBinaryTree)
{
	if (NULL != pBinaryTree)
	{
		printPostorder(pBinaryTree->left_child);
		printPostorder(pBinaryTree->right_child);
		printf("%d\n",pBinaryTree->value);
	}
}

参考资料：《数据结构与算法分析：C语言描述》(维斯)

（编辑：ASP站长网）