前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历 (Traversal) 是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次 。访问结点所做的操作依赖于具体的应用问题。 遍历 是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有： 前序 / 中序 / 后序的递归结构遍历 ：
1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后 。
由于被访问的结点必是某子树的根，所以 N(Node ）、 L(Left subtree ）和 R(Right subtree ）又可解释为根、根的左子树和根的右子树 。 NLR 、 LNR 和 LRN 分别又称为先根遍历、中根遍历和后根遍历。
// 二叉树前序遍历 void PreOrder(BTNode* root); // 二叉树中序遍历 void InOrder(BTNode* root); // 二叉树后序遍历 void PostOrder(BTNode* root);
下面主要分析前序递归遍历，中序与后序图解类似，同学们可自己动手绘制。
前序遍历
前序遍历递归图解：
代码解析：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); return; } node->data = x; node->left = NULL; node->right = NULL; return node; } BTNode* CreatTree() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); BTNode* node7 = BuyNode(7); node1->left = node2; node1->right = node4; node2->left = node3; node2->right = NULL; node4->left = node5; node4->right = node6; return node1; } //前序排列 void PreOrder(BTNode* root) { if (root==NULL) { printf("NULL "); return; } printf("%d ",root->data); PreOrder(root->left); PreOrder(root->right); } int main() { BTNode* root = CreatTree(); PreOrder(root); printf("\n"); return 0; }
中序遍历
中序遍历递归图解：
代码解析：
void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }
后序遍历
后序遍历递归图解：
代码解析：
void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
