定义

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

根据根节点访问的顺序，分为前序遍历、中序遍历、后序遍历

• 前序遍历: 先访问根节点，然后分别前序遍历左右子树
• 中序遍历: 先中序遍历左子树，访问根节点，在中序遍历右子树
• 后序遍历: 先中序遍历左子树，在中序遍历右子树，最后访问根节点
• 还有一种层次遍历：从根节点开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对节点逐个访问

如果我们要遍历上图中二叉树中，则
前序遍历: F C A D B E H G M
中序遍历: A C B D F H E M G
后序遍历: A B D C H M G E F
层次遍历: F C E A D H G B M

二叉树的构建

本文中重点关注二叉树的遍历，关于如何构建，点击这里。

节点的数据结构

function TreeNode(val){
    this.val = val;
    this.left = null;
    this.right = null;
}

用法

var nodeList = ['F', 'C', 'E', 'A', 'D', 'H', 'G', null, null, 'B', null, null, null, 'M', null]
var tree = Tree.build(nodeList);
console.log('前序遍历:', tree.preOrder())
console.log('中序遍历:',tree.inOrder())
console.log('后序遍历:',tree.postOrder())
console.log('层次遍历:',tree.bfs())
console.log('层次遍历(分层显示):',tree.bfs2())

代码实现

var Tree = (function(){
    var root = null;

    var build = function(valueList){
        if(!valueList || valueList.length === 0){
            return
        }
        root = new TreeNode(valueList.shift())
        var queue = [root]
        var tempQueue = []
        while(queue.length > 0){
            var node = queue.shift();
            if(valueList.length === 0){//构建结束
                break;
            }
            var leftVal = valueList.shift()
            if(leftVal!==null){//构建左子节点
                node.left = new TreeNode(leftVal) 
                tempQueue.push(node.left)
            }

            if(valueList.length === 0){//构建结束
                break;
            }
            var rightVal = valueList.shift()
            if(rightVal!==null){//构建又子节点
                node.right = new TreeNode(rightVal) 
                tempQueue.push(node.right)
            }
            if(queue.length === 0){//本次构建结束
                queue = tempQueue;
            }
        }
        return this;
    }

    var preOrder = function(){
        return _preOrder(root)
    }
    var inOrder = function(){
        return _inOrder(root)
    }
    var postOrder = function(){
        return _postOrder(root)
    }

    //层次遍历或者广度优先遍历
    var bfs = function(){
        if(!root){ return }
        var queue = [], result = []
        
        queue.push(root)
        while(queue.length > 0){
            var node = queue.shift()
            result.push(node.val)
            if(node.left){
                queue.push(node.left)
            }
            if(node.right){
                queue.push(node.right)
            }
        }
        return result
    }

    // 层次遍历2 把每一层的节点放到一个数组里，
    // 返回结构： [[leve1, leve1],[leve2,leve1],[leve3, leve3]]
    var bfs2 = function(){
        if(!root){ return }
        var queue = [], result = []
        queue.push(root)

        var levelArr = [];
        var tempQueue = []

        while(queue.length > 0){
            var node = queue.shift()

            levelArr.push(node.val)
            if(node.left){
                tempQueue.push(node.left)
            }
            if(node.right){
                tempQueue.push(node.right)
            }
            if(queue.length === 0){//说明本层遍历结束
                result.push(levelArr.concat())
                levelArr = []
                queue = tempQueue
                tempQueue = []
            }
        }
        return result
    }

    //private methods
    var _preOrder = function(node, result){
        result = result || []
        if(node){
            result.push(node.val)
            _preOrder(node.left, result)
            _preOrder(node.right, result)
        }
        return result
    }
    var _inOrder = function(node, result){
        result = result || []
        if(node){
            _inOrder(node.left, result)
            result.push(node.val)
            _inOrder(node.right, result)
        }
        return result
    }
    var _postOrder = function(node, result){
        result = result || []
        if(node){
            _postOrder(node.left, result)
            _postOrder(node.right, result)
            result.push(node.val)
        }
        return result
    }
    return {
        build: build,
        preOrder: preOrder,
        inOrder: inOrder,
        postOrder: postOrder,
        bfs: bfs,
        bfs2: bfs2
    }
})();