详解二叉树的递归遍历与非递归遍历

╰+哭是因爲堅強的太久メ 2021-11-10 10:20 401阅读 0赞

# 二叉树的遍历 #

所谓二叉树的遍历，是指按某条搜索路径访问树中的每个节点，使得每个节点均被访问一次，而且仅被访问一次。

遍历二叉树需要决定对根节点N、左子树L、右子树R的访问顺序（按照先遍历左子树在遍历右子树的原则），常见的遍历次序有先序（NLR）、中序（LNR）、后序（LRN）三种遍历算法，这也是最常见的二叉树遍历算法。

**其中的“序”实际上就是根节点的访问时机。**

## 1. 二叉树的数据结构 ##

> typedef struct BTNode\{
> 
> int data; //保存节点中的值
> 
> struct BTNode \*lchild; //左孩子指针
> 
> struct BTNode \*rchild; //右孩子指针
> 
> \}BTNode，\*BiTree；

这里我使用的比较适合基础学者的二叉树的存储结构，不同的存储结构，实现二叉树操作的算法也会不同，因此要根据实际应用场合（树的形态和需要进行的运算）来选择合适的存储结构。

不说废话了，哈哈肯定把你急死了！

## 2.二叉树的递归遍历 ##

### 1. 先序遍历 ###

先序遍历（PreOrder）的操作如下：

①首先若二叉树为空，则什么也不做；否则，

*  访问根节点；
 *  先序遍历左子树；
 *  先序遍历右子树。

对应的递归算法如下：

void PreOrder(BiTree T){
        if(T!=NULL){
            visit(T);        //访问跟结点
            PreOrder(T->lchild);    //访问左子树
            PreOrder(T->rchild);    //访问右子树
        }
    }

这里举一个例子做说明吧（后面都是使用这个例子），例子二叉树如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 1][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 2][]

这样一来先序遍历所得到的节点序列为1 2 4 6 3 5.

### 2. 中序遍历 ###

中序遍历（InOrder）的操作如下：

①首先若二叉树为空，则什么也不做；否则，

*  中序遍历左子树；
 *  访问根节点；
 *  中序遍历右子树。

对应的递归算法如下：

void InOrder(BiTree T){
        if(T!=NULL){
            InOrder(T->lchild);//递归遍历左子树
            visit(T);//访问根结点
            InOrder(T->lchild);//递归遍历右子树
            
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 3][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 4][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 5][]

这样一来中序遍历所得到的节点序列为2 6 4 1 3 5.

### 3. 后序遍历 ###

后序遍历（PostOrder）的操作如下：

①首先若二叉树为空，则什么也不做；否则，

*  后序遍历左子树；
 *  后序遍历右子树；
 *  访问根节点。

对应的递归算法如下：

void PostOrder(BiTree T){
        if(T!=NULL){
            PostOrder(T->lchild);//递归遍历左子树
            PostOrder(T->rchild);//递归遍历左子树
            visit(T);            //访问根结点
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 6][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 7][]

这样一来后序遍历所得到的节点序列为6 4 2 5 3 1.

这是二叉树结点的递归遍历，实现起来比较简单，很好地使用了递归的思想。

二叉树的非递归遍历在我的另一边文章当中

连接如下：[二叉树的非递归遍历][Link 1]

最后，送大家一句话：知识并不能为我们带来财富，但是能使我们有能力去创造财富。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190802172725198.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190802173505810.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 2]: /images/20211109/ebdbdaef1c124b19bb0b2839c408e04c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190802174626675.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190802175635203.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 5]: /images/20211109/06e281860008425eb25801b9b08d42a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20190802181140706.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 7]: /images/20211109/65346bcb934f4a25ac786bebcf8ff855.png
[Link 1]: https://blog.csdn.net/qq_37344125/article/details/98371082