Carl的博客空间

我们知道，树是一种 非线性 的数据结构，但计算机只能以线性的方式运行程序。要想让计算机能够处理树这种数据结构，就需要采用特殊的方式来解决，而这种特殊的方式就是我们本文准备讲解的遍历，废话不多说，开搞！

概述

树的种类繁多，但是最常用的还是 二叉树，因此本文是围绕二叉树来展开讲解的

二叉树的遍历是指从 根结点 出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次

遍历的方式

二叉树的遍历方式有很多，列举如下

深度优先遍历
- 前序遍历：根-左-右
- 中序遍历：左-根-右
- 后序遍历：左-右-根
广度优先遍历
- 层序遍历：按照树的层次一层一层地从左到右遍历

示例讲解

概念其实都非常简单，但是要想真正掌握还是必须要从实践出发，因此本节就会以给出示例的方式带你去领略每一种方式的魅力

构造二叉树

在js里，二叉树可以用一个对象来表示，示例如下

const tree = {
    name: 'root',
    left: {
        name: 'left-child',
        left:{
            name:'left-child-left'
        },
        right: {
            name: 'left-child-right'
        }
    },
    right: {
        name: 'right-child',
        left: {
            name: 'right-child-left'
        },
        right: {
            name: 'right-child-right'
        }
    }
}

前序遍历

这种方式主要是遵循 根-左-右 的顺序进行遍历，示例代码如下

function preOrderTraverse(node) {
    if(!node) {
        return
    }
    console.log(node.name)
    preOrderTraverse(node.left)
    preOrderTraverse(node.right)
}

中序遍历

这种方式主要是遵循 左-根-右 的顺序进行遍历，示例代码如下

function middleOrderTraverse(node) {
    if(!node) {
        return
    }
    middleOrderTraverse(node.left)
    console.log(node.name)
    middleOrderTraverse(node.right)
}

后序遍历

这种方式主要是遵循 左-右-根 的顺序进行遍历，示例代码如下

function afterOrderTraverse(node) {
    if(!node) {
        return
    }
    afterOrderTraverse(node.left)
    afterOrderTraverse(node.right)
    console.log(node.name)
}

可以看到，三种遍历方式都可以使用递归来实现

结语

二叉树的遍历其实没有想象中那么复杂，虽然它是一个非线性结构，但最终都会被线性地处理

如果我们采用递归的方式实现，那么不管是从代码实现，还是从理解上都非常简单，因此我们至少要掌握递归方式的遍历

至于非递归的方式我还没开始研究，等我研究好了再来出一篇博客，哈哈，好啦，over！

概述