二叉树的遍历算法有多种，典型的有先序遍历、中序遍历、后序遍历以及层序遍历。而且这些遍历的递归算法较为简单，代码很少，容易实现，本文就是汇总二叉树遍历的递归算法，非递归算法将在下一篇文章中进行总结。本文中用到的二叉树实例如下：
3
/ \
9 20
/ \
15 7
二叉树定义和辅助函数如下：
- struct node {
- int data;
- struct node* left;
- struct node* right;
- };
- void visit(int data)
- {
- printf("%d ", data);
- }
1、先序遍历
先序遍历：先访问二叉树的根结点，而后遍历左子树，最后遍历右子树。先序遍历二叉树实例结果为：3 9 20 15 7。递归算法代码如下：
- void preOrder(struct node* root)
- {
- if (root == NULL)
- return;
- visit(root->data);
- preOrder(root->left);
- preOrder(root->right);
- }
2、中序遍历
中序遍历：先遍历二叉树的左子树，然后访问根结点，最后遍历右子树。中序遍历二叉树实例结果：9 3 15 20 7。递归算法代码如下：
- void inOrder(struct node* root)
- {
- if (root == NULL)
- return;
- inOrder(root->left);
- visit(root->data);
- inOrder(root->right);
- }
3、后序遍历
后序遍历：先遍历二叉树的左子树，然后遍历二叉树右子树，最后访问根结点。后序遍历二叉树实例结果：9 15 7 20 3。递归算法代码如下：
- void postOrder(struct node* root)
- {
- if (root == NULL)
- return;
- postOrder(root->left);
- postOrder(root->right);
- visit(root->data);
- }
4、层序遍历
对于先序遍历、中序遍历以及后序遍历的递归算法，没有什么好说的，时间复杂度都为O（n）。而层序遍历的递归算法则稍微复杂一点，因为本身层序遍历用非递归算法是很容易实现的，不过使用递归算法代码更简洁，虽然递归算法的效率并不高。层序遍历二叉树实例结果：
3
9 20
15 7
递归代码如下：