数据结构之树（二叉树的遍历）

这是我参与更文挑战的第26天，活动详情查看：更文挑战

树的遍历

遍历一颗树就是指访问树的每个节点并对它们进行某种操作的过程。
遍历方式又分为：

• 中序遍历，是一种以上行顺序访问BST所有节点的遍历方式，也就是从最小到最大的顺序访问所有节点。
• 先序遍历，是以优先于后代节点的顺序访问每个节点。
• 后序遍历，是先访问节点的后代节点，再访问节点本身。

中序遍历的实现

中序遍历的一种应用就是对树进行排序操作。

function BinarySearchTree () {
    // 初始化根节点为null
    let root = null
    // 声明节点Node类，用于创建多个独立的节点
    let Node = function (key) {
        this.key = key
        this.left = null
        this.right = null
    }
    
    /** 
        inOrderTraverse方法接收一个回调函数作为参数，回调函数用来定义我们对遍历到的每个节点进行的操作（也叫访问者模式）。
        而在BST中最常用的算法就是递归，所有此处需要一个私有的辅助函数，来接收一个节点和对应的回调函数作为参数
    **/
    this.inOrderTraverse = function (callback) {
        inOrderTraverseNode(root, callback)
    }
    /**
        遍历的前提是该节点存在，节点存在才会一直遍历递归下去，当节点不存在时停止递归。那么此时节点是否存在就是递归是否继续执行的判断条件
        节点存在的话，先访问当前节点的左侧子节点，然后对 当前节点 进行callback中的一系列操作，之后再访问当前节点的右侧子节点
    **/
    let inOrderTraverseNode = function (node, callback) {
        if(node) {
            inOrderTraverseNode(node.left, callback)
            callback(node.key)
            inOrderTraverseNode(node.left, callback)
        }
    }
}
复制代码

上述代码中，我们简单的实现了中序遍历，那么我们来一起运行一下。
首先我们先定义一个对节点进行操作的回调函数

function printNode (value) {
    // 在控制台上输出当前节点
    console.log(value)
}
复制代码

根据上一篇文章中树的实现，我们首先创建一颗树：

let tree = new BinarySearchTree();
// 插入节点
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
复制代码

根据上述执行代码，我们生成了如下所示的一颗二叉搜索树：
BST的规则：比父节点小的子节点放在左侧，比父节点大的子节点放在右侧。

接下来，我们调用中序遍历方法，依次输出树的每个节点。从根节点开始遍历
tree.inOrderTraverseNode(printNode)
从中序遍历的定义我们就可以知道，最终的输出结果应该是这样的：
3 5 7 8 9 10 11 12 13 14 15 18 20 25

中序遍历规则：先访问左侧子树，再访问根节点，最后访问右侧子树。而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。

未完待续。。。