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

古城微笑少年丶 2022-04-24 05:40 73阅读 0赞

## 前言 ##

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

## 二叉树的遍历 ##

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

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

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

![640?wx\_fmt=png][640_wx_fmt_png]

二叉树

前序遍历

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

![640?wx\_fmt=gif][640_wx_fmt_gif]

前序遍历

前序遍历代码：

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。

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

中序遍历

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

中序遍历代码：

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

![640?wx\_fmt=gif][640_wx_fmt_gif 2]

后序遍历

后序遍历代码：

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

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

头结点入队：

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

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

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

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

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

![640?wx\_fmt=gif][640_wx_fmt_gif 3]

层次遍历

关键代码如下：

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

## 思考 ##

前面三种遍历方式都是直接printf输出，如果需要遍历返回一个数组呢？该如何实现？难点在哪？

具体实现可访问：

https://github.com/yanbinghu/data-structures-and-algorithms-in-c/blob/master/tree/traversal.c

或者**阅读原文**查看点击文章末尾的链接查看可运行代码。

关注公众号【编程珠玑】，获取更多Linux/C/C++/Python/Go/算法/工具等原创技术文章。后台免费获取经典电子书和视频资源

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

[Link 1]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284622&idx=1&sn=508b6434fe7a55e76866f330a8f45ea4&chksm=f2f99369c58e1a7f9d0b116e1efbcb171a5a5a32cbe6a6a95f15e749ca9cf889e6a2f0c268ab&scene=21#wechat_redirect
[640_wx_fmt_png]: /images/20220218/c1bf185a3444412e9bf37098c958a4d4.png
[640_wx_fmt_gif]: /images/20220218/bf6d7f07659c422798a2545d4e9f74fa.png
[640_wx_fmt_gif 1]: /images/20220218/e29ec7db8cc84485bf740decde1273ae.png
[640_wx_fmt_gif 2]: /images/20220218/758679b072324b168ad3d564810f5f29.png
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284579&idx=1&sn=cae147e7281c14f52776e57f08fff5a3&chksm=f2f9ac84c58e25927bbc59d8970456697d009b633d4b481b3335641cce2dc7eeaaca28b5c59a&scene=21#wechat_redirect
[640_wx_fmt_gif 3]: /images/20220218/aa96b3160e7543b2b9ba49fa23d6e7e7.png
[640_wx_fmt_jpeg]: /images/20220218/774ee9ab906b43b099500aeae8cf33af.png