初夏小谈：二叉树的三种遍历（1）

二叉树的遍历一般分为三种即为，前序遍历，中序遍历，后序遍历。

所谓前序遍历就是从二叉树的根节点出发，先访问根节点，在访问左孩子，然后访问右孩子。注意这是对于每一个结点都符合的条件。

中序遍历就是先访问左孩子，再访问根节点，最后访问右孩子。同样对每个节点都适用。

后序遍历则是先访问左孩子，在访问右孩子，最后访问根节点。每个节点都是如此。

知道了三种遍历方式后拿一个图来先看看各自的遍历顺序是怎么样的。

对于这样一棵简单的二叉树：

它的前序遍历顺序是先走A---》再走B---》接着走D，发现D没有左孩子后，在访问D的右孩子，发现也没有，就返回D，返回到B，接着走B的右孩子，从E出发，发现E左右孩子都没有，就返回B，返回到A，走A的右孩子C，访问C的左孩子发现没有就访问其右孩子F，再访问F的左右孩子发现没有就返回。

前序遍历顺序：A--->B--->D--->E--->C--->F

中序遍历：只是先走每个根节点的左孩子，再走根节点，最后访问右孩子。

中序遍历顺序：D--->B--->E--->A--->C--->F

后序遍历：则是先走根节点的左孩子，再走右孩子，最后访问根节点。

后序遍历顺序：D--->E--->B--->F--->C--->A

实现三种遍历的方式有两种分别是递归和循坏。这里先来说递归实现三种遍历。

前序遍历：

思想：就是先从根节点开始，先判断根节点是否存在，如果不存在就返回。如果存在就打印该节点，再访问它的左右孩子。
//1.前序遍历
void PreorderTraversal(Node* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreorderTraversal(root->left);
	PreorderTraversal(root->right);
}
中序遍历：

思想：也是从根节点开始先判断是否存在，不存在就返回，存在就访问它的左孩子，待访问完左孩子后，再打印这个根节点，最后访问右孩子。
//2.中序遍历
void InorderTraversal(Node* root)
{
	if (root == NULL)
	{
		return;
	}
	InorderTraversal(root->left);
	printf("%d ", root->data);
	InorderTraversal(root->right);
}
后序遍历：

思想：从根节点开始，先访问它的左孩子，直到她的左孩子完全返回，在遍历它的右孩子，待全部返回后，再打印根节点。
//3.后序遍历
void PostorderTraversal(Node* root)
{
	if (root == NULL)
	{
		return;
	}
	PostorderTraversal(root->left);
	PostorderTraversal(root->right);
	printf("%d ", root->data);
}

说完三种基本的遍历，可以从前序遍历和中序遍历或后序遍历和中序遍历推出一颗完整的二叉树，前序遍历和后序遍历是不可以推出完整的二叉树的因为无法区分出该树的左右子树。

以上面的前序遍历和中遍历来说

前序：A--->B--->D--->E--->C--->F

中序：D--->B--->E--->A--->C--->F

我们知道前序遍历先从根结点开始的，所以A就是根节点，中序我们知道先是访问左孩子再访问根节点的所以，便可以得出A的左子树有D，B，E，右子树上有C，F，紧接着我们从前序遍历结果得知B是A的左子树的根，在从中序遍历得知D为B的左孩子，E为B的右孩子。再看A的右子树，从前序看C为右子树的根，但无法判断F是C的左孩子还是右孩子，这时就从中序看如果F为左孩子则中序遍历时F一定在C的前面，显然F在C的后面，说明F是C的右孩子。

这种推导的方法总结一下就是：通过前序或后序遍历来确定根节点，在通过中序确定左右子树，再通过前序或后序确定根，在通过中序确定左右孩子。以此类推。