所谓二叉树遍历，就是按照一定的规则依次操作二叉树中的节点，每个节点只操作一次。访问结点的操作取决于具体的应用问题。 遍历是二叉树最重要的运算之一，也是二叉树其他运算的基础。
二叉树的遍历包括:前序/中序/后序的递归结构遍历:
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