返回信息流写了一个二叉树，然后分别使用广度遍历和深度遍历，为什么广度遍历比深度遍历用的时间长很多呢？
遍历的次数是相同的。
初学算法，请各位指教
```
class Node {
constructor (data, left, right) {
this.data = data
this.left = left
this.right = right
}
}
class BST {
constructor() {
this.root = null
this.ordered = []
this.times = 0
}
insert (data) {
var node = new Node(data, null, null)
if (this.root === null) {
this.root = node
} else {
var current = this.root
var parent
while(current !== null) {
parent = current
if (data < current.data) {
current = current.left
} else if (data > current.data){
current = current.right
} else {
return
}
}
data < parent.data ? (parent.left = node) : (parent.right = node)
}
}
inOrder(node) {
if (node !== null) {
this.times++
this.inOrder(node.left)
this.ordered.push(node.data)
this.inOrder(node.right)
}
}
// 广度优先遍历
bfs() {
var arr = []
arr.push(this.root)
while(arr.length) {
this.times++
var node = arr.shift()
this.ordered.push(node.data)
if (node.left) {
arr.push(node.left)
}
if (node.right) {
arr.push(node.right)
}
}
}
}
// test
var nums = new BST();
for (var j = 0; j < 100000; j++) {
nums.insert(Math.floor(Math.random()*100000))
}
console.time('bfs')
nums.bfs()
console.timeEnd('bfs')
console.log(nums.times)
nums.ordered.length = 0
nums.times = 0
console.time('inorder')
nums.inOrder(nums.root);
console.timeEnd('inorder')
console.log(nums.times)
```
这是一条镜像帖。来源：北邮人论坛 / java-script / #2946同步于 2017/9/26
该镜像源已超过 30 天没有更新，可能在源站已被删除。
JavaScript机器人发帖
为什么这样写的循环比递归花费时间长很多呢
vac872089248
2017/9/26镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
bfs 慢的主要原因是在 bfs 代码里使用了 arr.shift() 操作，可以尝试改为不用 unshift 操作的代码，这样运行速度就会显著的快
其次，在最后的代码速度计算中，只计算了一次的速度，这样就会导致前一次的运行会优化后一次的结果；可以把最后代码改为先测 inorder 后测 bfs，就会发现结果有点不同（虽然还是 inorder 快）
去掉 UNshift 并进行多次（比如 50 次）测量 bfs inorder 运行时间，就会发现两者差距不是很大，有时 bfs 还要稍快一点，但是大部分情况还是 inorder 快，我想这是因为 JavaScript 引擎 V8 对函数调用进行了优化，使得调用子函数速度比 bfs 除 this.times++;this.ordered.push(node.data) 额外的操作要快
先测inorder差的也挺多,下面是添加了了500000个节点
```
inorder: 34.885ms
499889
bfs: 138.871ms
499889
```
把shift换成了splice, 差得更多了
```
inorder: 35.602ms
499867
bfs: 237.638ms
499867
```
然后我又使用``arr[0]``取队首的元素，然后用slice去掉队首元素，bfs时间就无限了。。但是没有其他模拟队列的方法了。。。
【 在 UpBlast 的大作中提到: 】
: bfs 慢的主要原因是在 bfs 代码里使用了 arr.shift() 操作，可以尝试改为不用 unshift 操作的代码，这样运行速度就会显著的快
: 其次，在最后的代码速度计算中，只计算了一次的速度，这样就会导致前一次的运行会优化后一次的结果；可以把最后代码改为先测 inorder 后测 bfs，就会发现结果有点不同（虽然还是 inorder 快）
: 去掉 UNshift 并进行多次（比如 50 次）测量 bfs inorder 运行时间，就会发现两者差距不是很大，有时 bfs 还要稍快一点，但是大部分情况还是 inorder 快，我想这是因为 JavaScript 引擎 V8 对函数调用进行了优化，使得调用子函数速度比 bfs 除 this.times++;this.ordered.push(node.data) 额外的操作要快
使用队列出队入队方法一定要保证时间复杂度是 O(1)，当然你也可以以下的方式写
while (arr.length) {
var newArr = [];
for (var i = 0; i < arr.length; ++i) {
this.times++;
var node = arr[i];
this.ordered.push(node.data);
if (node.left) {
newArr.push(node.left);
}
if (node.right) {
newArr.push(node.right);
}
}
arr = newArr;
}
厉害！效果显著！不使用shift一直往后取数据，要比使用shift节省一半的时间
```
bfs() {
var arr = []
arr.push(this.root)
for (let i = 0; i < arr.length; i++) {
this.times++
let node = arr[i]
this.ordered.push(node.data)
if (node.left) {
arr.push(node.left)
}
if (node.right) {
arr.push(node.right)
}
}
}
```
为什么shift这么费时间啊？是因为指令复杂吗
没有学过计算机，只学过单片机。。
【 在 UpBlast 的大作中提到: 】
: 使用队列出队入队方法一定要保证时间复杂度是 O(1)，当然你也可以以下的方式写
: while (arr.length) {
: var newArr = [];
: ...................
嗯嗯，好的，非常感谢！
【 在 UpBlast 的大作中提到: 】
: 这个和 unshift 底层实现机制有关。你可以系统地学一下队列大概知道了