数据结构：二叉树的前序、中序和后序遍历

前言
在学习二叉树的基本操作之前，我们需要先手动快速构建一个二叉树。以下图的二叉树为例。（二叉树真正的构建方法并不是这样）

//手动创建一个二叉树

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc failn");
		exit(-1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

BTNode* CreatBinaryTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');
	BTNode* nodeG = BuyNode('G');

	nodeA->left = nodeB;
	nodeA->right = nodeD;
	nodeB->left = nodeC;
	nodeD->left = nodeE;
	nodeD->right = nodeF;

	return nodeA;
}

前序遍历：访问根节点的操作发生在遍历其左右子树之前。

由上述逻辑可知，如果前序遍历该二叉树，则顺序为：A B C NULL NULL NULL D E NULL NULL F NULL NULL

中序遍历：访问根节点的操作发生在遍历其左右子树中间

中序遍历该二叉树的顺序：NULL C NULL B NULL A NULL E NULL D NULL F NULL

后序遍历：访问根节点的操作发生在遍历其左右子树之后。

后序遍历该二叉树的顺序：NULL NULL C NULL B NULL NULL E NULL F NULL D A

根据以下的部分逻辑，可以知道，这种遍历的思想采用了递归的结构，现在开始代码的实现吧

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

递归图解

中序和后序遍历原理都是如此。

 //中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
 }
 //后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	InOrder(root->left);
	InOrder(root->right);
	printf("%c ", root->data);
}