树的遍历

tip

中序遍历：先遍历左子节点，再遍历当前节点，最后遍历右子节点。 前序遍历：先遍历当前节点，再遍历左子节点，最后遍历右子节点。 后序遍历：先遍历左子节点，再遍历右子节点，最后遍历当前节点。

caution

注意：只需要记住中序、前序、后序是相对于中间的节点而言的就好记了。

中序遍历

// 中序遍历
this.inOrderTraverse = function (callback) {
    inOrderTraverseNode(root,callback);
}
// inOrderTraverse方法接收一个回调函数参数，这个回调函数用来定义对遍历到的每个节点进行的操作
// inOrderTraverseNode 辅助函数
function inOrderTraverseNode(node, callback){
    if (node !== null) {
        inOrderTraverseNode(node.left, callback); // 先左
        callback(node); // 当前节点中间顺序遍历-----中序
        inOrderTraverseNode(node.right, callback);// 后右
    }
}

中序遍历的访问路径图：

前序遍历

this.preOrderTraverse = function(callback){
    preOrderTraverseNode(root, callback);
};
function preOrderTraverseNode(node, callback){
    if (node !== null) {
        callback(node);
        preOrderTraverseNode(node.left, callback);
        preOrderTraverseNode(node.right, callback);
    }
}

前序遍历的访问路径图：

后序遍历

this.postOrderTraverse = function(callback){
  postOrderTraverseNode(root, callback);
};

function postOrderTraverseNode(node, callback) {
    if (node !== null) {
        postOrderTraverseNode(node.left, callback);
        postOrderTraverseNode(node.right, callback);
        callback(node);
    }
}

后序遍历的访问路径图：