本文采用层次遍历的方法构建一颗二叉树。
我们约定节点为空时,用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
}