二叉树的遍历 —— 先序、中序、后序

[gogoend]

了解

树状数据结构的遍历在我们日常工作中是十分常见的遍历方式，无奈每次对树状结构进行遍历，笔者总感觉不是那么得心应手。例如：

1. 如何对树由上到下进行层序的遍历？
2. 如何在树的遍历过程中对树的子节点进行额外操作？
3. 困扰笔者多年的先序、中序、后序遍历到底是什么意思？
4. 树的遍历除了递归，是否还有其它方式？

因此，找了一些时间，进行复习。这里先从二叉树的遍历看起。

这里的“序”，实际上指的是根节点的访问顺序。
先序，即根->左->右
中序，即左->根->右
后序，即左->右->根
无论根在何处，左节点一定在右节点之前访问。

挑战

94. 二叉树的中序遍历
617. 合并二叉树

[gogoend]

示例

这是一个二叉树的树状结构的数据，每个子节点中均包含key，若存在子节点则包含children。children中第0个元素是左节点，第1个元素是右节点。我们来将树中的每一个节点按照先序、中序、后序遍历的顺序来输出。

let aTree = {
    key: 'A',
    children: [
        {
            key: 'B',
            children: [
                {
                    key: 'D',
                    children: [
                        { key: 'G' },
                        { key: 'H' }
                    ]
                },
                null
            ]
        },
        {
            key: 'C',
            children: [
                {
                    key: 'E',
                    children: [
                        null,
                        { key: 'I' }
                    ]
                },
                { key: 'F' }
            ]
        },
    ]
}

首先，我们来编写先序遍历的代码。

function preOrderTraverse(biTree) {
    if (!biTree) return
    console.log(biTree.key)
    biTree.children && preOrderTraverse(biTree.children[0])
    biTree.children && preOrderTraverse(biTree.children[1])
}

执行代码，得到遍历结果：

执行过程：函数开始执行后，首先输出当前遍历的树的根节点，然后递归地分别对左孩子和右孩子也进行这个操作。