数据结构——二叉树的遍历

一、“树”是一种重要的数据结构，本文浅谈二叉树的遍历问题，采用C语言描述。 1）定义：有且仅有一个根结点，除根节点外，每个结点只有一个父结点，最多含有两个子节点，子节点有左右之分。 2）存储结构二叉树的存储结构可以采用顺序存储，也可以采用链式存储，其中链式存储更加灵活。在链式存储结构中，与线性链表类似，二叉树的每个结点采用结构体表示，结构体包含三个域：数据域、左指针、右指针。

struct BiTreeNode{
 int c;
 struct BiTreeNode *left;
 struct BiTreeNode *right;
};

二、二叉树的遍历 “遍历”是二叉树各种操作的基础。二叉树是一种非线性结构，其遍历不像线性链表那样容易，无法通过简单的循环实现。二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。二叉树遍历通常借用“栈”这种数据结构实现，有两种方式：递归方式及非递归方式。在递归方式中，栈是由操作系统维护的，用户不必关心栈的细节操作，用户只需关心“访问顺序”即可。因而，采用递归方式实现二叉树的遍历比较容易理解，算法简单，容易实现。递归方式实现二叉树遍历的C语言代码如下：

//先序遍历--递归
int traverseBiTreePreOrder(BiTreeNode \*ptree,int (\*visit)(int))
{
	if(ptree)
	{
		if(visit(ptree->c))
			if(traverseBiTreePreOrder(ptree->left,visit))
				if(traverseBiTreePreOrder(ptree->right,visit))
					return 1;  //正常返回
		return 0;   //错误返回
	}else return 1;   //正常返回
}
//中序遍历--递归
int traverseBiTreeInOrder(BiTreeNode \*ptree,int (\*visit)(int))
{
	if(ptree)
	{
		if(traverseBiTreeInOrder(ptree->left,visit))
			if(visit(ptree->c))
				if(traverseBiTreeInOrder(ptree->right,visit))
					return 1;
		return 0;
	}else return 1;
}
//后序遍历--递归
int traverseBiTreePostOrder(BiTreeNode \*ptree,int (\*visit)(int))
{
	if(ptree)
	{
		if(traverseBiTreePostOrder(ptree->left,visit))
			if(traverseBiTreePostOrder(ptree->right,visit))
				if(visit(ptree->c))
					return 1;
		return 0;
	}else return 1;
}

二叉树的遍历有三种方式，如下：（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。 tree 例1：如上图所示的二叉树，若按前序遍历，则其输出序列为。若按中序遍历，则其输出序列为。若按后序遍历，则其输出序列为。前序：根A，A的左子树B，B的左子树没有，看右子树，为D，所以A-B-D。再来看A的右子树，根C，左子树E，E的左子树F，E的右子树G，G的左子树为H，没有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH 中序：先访问根的左子树,B没有左子树，其有右子树D，D无左子树，下面访问树的根A，连起来是BDA。再访问根的右子树，C的左子树的左子树是F，F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左子树结束，找到根C，无右子树，结束。连起来是FEHGC, 中序结果连起来是BDAFEHGC 后序：B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA