JS层次遍历构建二叉树

本文采用层次遍历的方法构建一颗二叉树。

我们约定节点为空时，用null表示。如果我们要用层次遍历构建如上图所示的二叉树，则传入的数据为
['F', 'C', 'E', 'A', 'D', 'H', 'G', null, null, 'B', null, null, null, 'M', null]

步骤

层次遍历构建二叉树的主要思想是，使用一个队列(queue)保存本层所需要初始化的节点，然后依次出队，分别构建节点的左右子树，同时把左右子树，也就是下一层节点的数据，压入到另一个临时队列(tempQueue)中。当队列(queue)为空时，则说明本层次的节点已经构建完毕，此时需要把临时队列赋值给节点队列(queue=tempQueue)，然后再次重复上面步骤，构建队列(queue)中的节点，直至数据为空时结束。

第一次循环时，队列(queue)中只有一个节点F，第一次循环结束，临时队列(tempQueue)中为C E. 然后赋值queue=tempQueue。

第二次循环时，队列(queue)中含有C E两个节点。第二次循环结束，临时队列(tempQueue)中为A D H G, 然后赋值queue=tempQueue。
依次类推

下面我们来用代码实现，这里我们只使用了层次遍历的方法来遍历二叉树，如果需要使用其他方法来遍历二叉树，请点击查看这里

首先定义节点数据结构

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.bfs())

代码实现

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 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
    }
    return {
        build: build,
        bfs: bfs
    }