二叉树的递归遍历

一个二叉树如何遍历呢？
我们对于一个二叉树有3种遍历方式：先序遍历、中序遍历、后序遍历。
先序遍历：先访问父节点，再依次访问左节点、右节点。
中序遍历：先访问左节点，再依次访问父节点、右节点。
后序遍历：先访问左节点，再依次访问右节点、父节点。

为了更好的理解二叉树的遍历，我们先看一个具体的二叉树。

对于先序遍历，从跟节点出发，对于2、3节点来说，1是其父节点，所以先访问1,再访问左节点2，同理，对于4,、5节点来说，2是父节点，所以再访问左节点4，访问顺序依次为：1 2 4 8 9 5 10 11 3 6 12 13 7，如上图所示。
用C语言递归代码表示为：
二叉树结构体为：

struct TreeNode
{
	int  data;     //数据域
	struct TreeNode *left;     
	struct TreeNode *right;
};

这是先序遍历代码：

  //先序遍历
    void preorderTravaersal(struct TreeNode *root)
    {
    	if (root)     //如果树非空
    	{
    		printf("%d  ", root->data);      //先访问根节点
    		preorderTravaersal(root->left);   //递归地遍历左子树
    		preorderTravaersal(root->right);   //递归地遍历右子树
    	}
    }

这是中序遍历代码：

  //先序遍历
    void preorderTravaersal(struct TreeNode *root)
    {
    	if (root)     //如果树非空
    	{
    		preorderTravaersal(root->left);   //递归地遍历左子树
    		printf("%d  ", root->data);      //先访问根节点
    		preorderTravaersal(root->right);   //递归地遍历右子树
    	}
    }

这是后序遍历代码：

  //先序遍历
    void preorderTravaersal(struct TreeNode *root)
    {
    	if (root)     //如果树非空
    	{
    		preorderTravaersal(root->left);   //递归地遍历左子树
    		preorderTravaersal(root->right);   //递归地遍历右子树
    		printf("%d  ", root->data);      //先访问根节点
    	}
    }

根据以上代码很容易理解，按照访问根节点的时机（对于每个节点来说就是访问父节点的时机），先访问根节点叫先序遍历，中间访问根节点叫中序遍历，最后访问根节点叫后序遍历。