二叉树的前、中、后序遍历

所谓二叉树遍历是按某种特定规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树进行其它运算的基础。

二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(先根遍历)——访问根结点的操作发生在遍历其左右子树之前（根->左子树->右子树）。

2. 中序遍历(中根遍历)——访问根结点的操作发生在遍历其左右子树之中（左子树->根->右子树)。

3. 后序遍历(后根遍历)——访问根结点的操作发生在遍历其左右子树之后（左子树->右子树->根）。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

以下面这个图为例，对它进行前、中、后序遍历

先动手实现如上图所示的一个二叉树

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL) {
		perror("BTNode::mallc");
		return(-1);
	}
	newnode->_data = x;
	newnode->_left = newnode->_right = NULL;
	return newnode;
}
BTNode* CreatBinaryTree()
{
	BTNode* A = BuyNode(A);
	BTNode* B = BuyNode(B);
	BTNode* C = BuyNode(C);
	BTNode* D = BuyNode(D);
	BTNode* E = BuyNode(E);
	BTNode* F = BuyNode(F);

	A->_left = B;
	A->_right = C;
	B->_left = D;
	C->_left = E;
	C->_right = F;
	return A;
}

前序遍历

void PreOrder(BTNode* root)
{
	if (root == NULL) {
		return;
	}
	printf("%c ", root->_data);
	PreOrder(root->_left);
	PreOrder(root->_right);
}

递归调用过程如下图所示

中序遍历、后序遍历和前序遍历递归调用过程类似，就不画图了，下面分别给出了相应的代码。

中序遍历

void InOrder(BTNode* root)
{
	if (root == NULL) {
		return;
	}
	InOrder(root->_left);
	printf("%c ", root->_data);
	InOrder(root->_right);
}

后序遍历

void PostOrder(BTNode* root)
{
	if (root == NULL) {
		return;
	}
	PostOrder(root->_left);
	PostOrder(root->_right);
	printf("%c ", root->_data);
}

前序遍历结果：A B D C E F

中序遍历结果：D B A E C F

后序遍历结果：D B E F C A