树的三种遍历方式（先序、中序、后序）

树的遍历分很多种，经过前人总结，树的遍历其实一共就有三种方法，一种为先序遍历、一种为中序遍历、最后一种为后续遍历。他们不同的区别就是在遍历过程中查找树的根、左节点、右节点的顺序，同样由于遍历树惯用递归的方式，所以所谓的查找顺序不同就是在递归过程中打印节点数据时的代码位置不同而已，如果这句话你看的比较绕，那么在后面的代码中你将会恍然大悟。不过再看代码之前，你还是要记住下面的顺序。

【三种遍历方式的顺序】

先序遍历：先根、再左、后右

中序遍历：先左、再根、后右

后续遍历：先坐、再右、后根

一定要注意，由于是递归，所以每当遇到一个非叶子节点的时候，都要重新应用规则（相当于代码中递归入口）。如果你还是不理解，那么我们用下面的树结构来做一个小练习。

上图使用先序遍历的顺序如下（根、左、右）：

第一步：输出根 A

第二步：遇到非叶子节点，重新应用规则，输出根 B

第三步：继续上一次的规则，输出左节点 D

第四部：继续上一次的规则，输出右节点 E

第五步：A 的左侧节点都已经遍历到并输出完毕，继续 A 遍历的右侧节点，遇到非叶子节点 C，重新应用规则，输出根 C

第六步：继续以 C 为根节点的遍历，由于 C 没有左侧节点，所以直接输出右侧节点 F

最后：遍历出来的顺序就是 A B D E C F

使用中序遍历的顺序如下（左、根、右）：

第一步：找到 A 的左侧节点 B，发现其是非叶子节点，则重新应用规则向下找，B 的左节点是 D，并且没有子节点，所以遍历到底后最先输出 D

第二步：左节点找到了，按规则继续找这个左节点的根节点，输出 B

第三步：找到根节点 B 后继续找它的右节点 E，输出 E

第四步：A 的左侧节点都遍历完了，那么开始输出以 A 为根节点的根，输出 A

第五步：查找 A 的右子节点是 C ，但由于其是非叶子节点，所以重新应用规则，找 C 的左侧节点，由于 C 没有左子几点，输出根 C

第六步：输出根 C 完成后继续查找其右子节点，输出 F，右侧遍历完成

最后：遍历出来的顺序就是 D B E A C F

使用后续遍历的顺序如下（左、右、根）：

第一步：找到 A 的左侧节点 B，发现其是非叶子节点，则重新应用规则向下找，B 的左节点是 D，并且没有子节点，所以遍历到底后最先输出 D

第二步：继续找以 B 为跟节点的右子节点，输出 E

第三步：找根节点，输出 C

第四步：所有左侧节点遍历完成后，继续遍历 A 的右侧节点，找到 C，但 C 是非叶子节点，所以继续找其左节点，左节点不存在继续找右节点，输出 F

第五步：右侧节点全部遍历完毕，最后输出根节点 A

最后：遍历出来的顺序就是 D E B F C A

【代码实现】

上面我们使用逻辑思维过了一次遍历过程，下面我们就用代码实现一次，其实代码实现所谓的先序、中序、后序，只是输出语句在不同位置时则有不同的效果。代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tag_tirTNode
{
	//节点的数据
	char data;
	//左子节点指针
	struct tag_tirTNode* leftChild;
	//右子节点指针
	struct tag_tirTNode* rightChild;
}TirTNode;


void showTree(TirTNode* tree)
{
	if (tree == NULL)
	{
		return;
	}

	// 先序遍历
	printf("%c ", tree->data);

	if (tree->leftChild != NULL)
	{
		showTree(tree->leftChild);
	}

	// 中序遍历
	//printf("%c ", tree->data);

	if (tree->rightChild != NULL)
	{
		showTree(tree->rightChild);
	}

	// 后序遍历
	printf("%c ", tree->data);
}

int main()
{
	// 定义树的节点元素
	TirTNode treeA, treeB, treeC, treeD, treeE, treeF, treeG;

	// 初始化
	memset(&treeA, 0, sizeof(TirTNode));
	memset(&treeB, 0, sizeof(TirTNode));
	memset(&treeC, 0, sizeof(TirTNode));
	memset(&treeD, 0, sizeof(TirTNode));
	memset(&treeE, 0, sizeof(TirTNode));
	memset(&treeF, 0, sizeof(TirTNode));
	memset(&treeG, 0, sizeof(TirTNode));

	treeA.data = 'A';			// 节点值
	treeA.leftChild = &treeB;	// 左子节点
	treeA.rightChild = &treeC;	// 右子节点

	treeB.data = 'B';
	treeB.leftChild = &treeD;
	treeB.rightChild = &treeE;

	treeC.data = 'C';
	treeC.leftChild = NULL;
	treeC.rightChild = &treeF;

	// 让叶子节点的left和right都指向NULL
	treeD.data = 'D';
	treeD.leftChild = NULL;
	treeD.rightChild = NULL;

	treeE.data = 'E';
	treeE.leftChild = NULL;
	treeE.rightChild = NULL;

	treeF.data = 'F';
	treeF.leftChild = NULL;
	treeF.rightChild = NULL;

	showTree(&treeA);

	return 0;
}

从代码上我们可以看出来，所谓先序、中序、后序，在代码上只不过是输出语句 printf(“%c “, tree->data); 在进入递归代码的不同位置而起到的不同的输出作用。以上代码是先序遍历，如果你想改成中序遍历，就把进入递归前的 printf(“%c “, tree->data); 注释，然后将递归左子树下面的 printf(“%c “, tree->data); 解除注释就可以了。想改为后序遍历也是一样。