动画：二叉树遍历的多种姿势

前言

在《什么是二叉树》中，我们介绍了二叉树的创建（插入），查找和删除，本文将介绍二叉树的遍历。而二叉树遍历有多种形式，他们也可以应用在不同的场景中，常见的深度优先遍历方式有前序遍历，中序遍历，后序遍历，而不常用广度优先遍历方式有层次遍历。本文将会对以上遍历方式都进行介绍。

二叉树的遍历

常见遍历顺序有以下几种：

• 前序遍历，先检查节点值，然后递归遍历左子树和右子树
• 中序遍历，先遍历左子树，然后检查当前节点值，最后遍历右子树
• 后序遍历，先递归遍历左右子树，然后检查当前节点值
• 层次遍历，如名字所言，从第一层开始，一层一层往下遍历

以下图为例，我们一一介绍四种遍历方式。

二叉树

前序遍历

• 输出当前节点值10，然后输出左子树，最后输出右子树；
• 对于其左子树来说，同样以这样的顺序，则先输出5，然后输出左子树4，最后输出右子树8；
• 对于其右子树，同样以这样的顺序，则先输出19，然后输出左子树13，最后输出右子树24；
• 最终得到前序遍历输出为：10,5,4,8,19,13,24。

前序遍历

前序遍历代码：

void preOrder(TreeNode *tree)
{
    if(NULL == tree)
        return;
    printf("%d ",tree->value);
    preOrder(tree->left);
    preOrder(tree->right);
}

中序遍历：

• 先输出左子树，然后输出当前节点10，最后输出右子树；
• 对于其左子树来说，同样以这样的顺序，则先输出左子树4，然后输出节点值5，最后输出右子树8；
• 对于其右子树，同样以这样的顺序，则先,输出左子树13，然后输出节点值19，最后输出右子树24；
• 最终得到中序遍历输出为：4,5,8,10,13,19,24。

中序遍历

我们发现二叉查找树的中序遍历输出就是排序后的结果。还记得吗，二叉查找树也叫二叉搜索树或者二叉排序树。

中序遍历代码：

void inOrder(TreeNode *tree)
{
    if(NULL == tree)
        return; 
    inOrder(tree->left);
    printf("%d ",tree->value);
    inOrder(tree->right);
}

后序遍历

• 先输出左子树，然后输出右子树，最后输出节点值10
• 对于其左子树来说，同样以这样的顺序，则先输出左子树4，然后输出右子树8，最后输出节点值5；
• 对于其右子树，同样以这样的顺序，则先,输出左子树13，然后输出右子树24，最后输出节点值19
• 最终得到后序遍历输出为：4,8,5,13,24,19,10

后序遍历 后序遍历代码：

void postOrder(TreeNode *tree)
{
    if(NULL == tree)
        return;
    postOrder(tree->left);
    postOrder(tree->right);
    printf("%d ",tree->value);
}

层次遍历

• 遍历第一层，输出10
• 遍历第二层，输出5,19
• 遍历第三层，输出4,8,13,24

虽然看起来过程很简单，但是代码实现却不能像前面三种深度优先遍历方式那样直接使用递归，它更好的方式是借助一个具有先入先出特点的队列（队列可参考《如何自己实现一个队列》）。以三个节点为例，我们先将根节点入队，然后分别入队左右孩子节点，最后输出队列内容，那么它的顺序就是层次遍历的顺序了。

头结点入队：

输出,队头元素10，并将它的左右孩子5,19入队：

输出队头元素5，并将它的左右孩子4,8入队：

输出队头元素19，并将它的左右孩子13,24入队：

由于队列中的元素都没有孩子节点，因此都直接出队，输出4,8,13,24

最终得到的输出顺序为：10,5,19,4,8,13,24.

层次遍历

关键代码如下：

void PrintNodeByLevel(TreeNode* root) 
{
    if(NULL == root)
         return;
    /*初始化队列*/
    QueueInfo queue;
    init_queue(&queue);
    TreeNode *node = NULL;

    /*头节点入队*/
    queue_insert(&queue,root);
    do 
    {
        queue_delete(&queue,&node);
        if (node) 
        {
            printf("%d ",node->value);
            if (node->left)
                queue_insert(&queue,node->left);
            if (node->right)
                queue_insert(&queue,node->right);
        }
    } while (!queue_is_empty(&queue));
}

完整可运行代码

完整代码较长，请访问：https://github.com/yanbinghu/data-structures-and-algorithms-in-c/blob/master/tree/traversal.c 运行结果：

insert 10 to tree
insert 5 to tree
insert 19 to tree
insert 4 to tree
insert 8 to tree
insert 13 to tree
insert 24 to tree

层次遍历：10 5 19 4 8 13 24 
前序遍历：10 5 4 8 19 13 24 
后序遍历：4 8 5 13 24 19 10 
中序遍历：4 5 8 10 13 19 24