js对树的广度优先遍历和深度优先遍历
如下图一棵树：
广度优先遍历顺序：ABCDEFGHIJKLMN
深度优先遍历顺序：ABEFJLMNGCDHKI
广度优先遍历借助于队列，队列的特点是先进先出，后进后出。步骤如下：
1.将A放入队列，将A弹出队列；
2.将A的子节点BCD顺序放入队列（此时B在队头）,将B弹出队列，判断B是否有子节点，若有则将B的子节点放入队列，若没有将队列头部元素继续弹出队列（上图B有EFG三个子节点，所以将EFG顺序放入，然后将C弹出队列），继续判断弹出节点是否有子元素，重复此步骤直到队列为空。
深度优先遍历借助于栈，栈的特点是先进后出，后进先出。步骤如下：
1.将A放入栈，将A出栈；
2.将A的子节点BCD倒序入栈（此时B在栈的顶端），将B出栈，判断B是否有子节点，若有则将B的子节点入栈，若没有将队列头部元素继续出栈（上图B有EFG三个子节点，所以将EFG倒序入栈，此时E在栈的顶端，所有将E出栈），继续判断出栈节点是否有子元素，重复此步骤直到栈为空。
代码如下：
class Stack {
constructor(data = []) {
this.data = Array.from(data)
}
push (v) {
return this.data.push(v)
}
pop () {
return this.data.pop()
}
}
class Queue {
constructor(data = []) {
this.data = Array.from(data)
}
push (v) {
return this.data.push(v)
}
pop () {
return this.data.shift()
}
}
class Tree {
constructor (data = []) {
this.data = Array.from(data)
this.queue = new Queue()
this.stack = new Stack()
}
// 广度优先
printBFS () {
this.bfs(this.data)
}
bfs (data) {
data.forEach(item => {
this.queue.push(item)
})
this.bfsFn()
}
bfsFn () {
if (this.queue.data.length === 0) return
const popV = this.queue.pop()
console.log(popV.value)
if (popV.children) {
this.bfs(popV.children)
} else {
this.bfsFn()
}
}
// 深度优先
printDFS () {
this.dfs(this.data)
}
dfs (data) {
// 倒序将子节点压入栈中
for (let i = data.length - 1;i >= 0;i--) {
this.stack.push(data[i])
}
this.dfsFn()
}
dfsFn () {
if (this.stack.data.length === 0) return
const popV = this.stack.pop()
console.log(popV.value)
if (popV.children) {
this.dfs(popV.children)
} else {
this.dfsFn()
}
}
}
const tree = new Tree([{
value: 'A',
children: [{
value: 'B',
children: [{
value: 'E'
}, {
value: 'F',
children: [{
value: 'J',
children: [{
value: 'L'
}, {
value: 'M'
}, {
value: 'N'
}]
}]
}, {
value: 'G'
}]
}, {
value: 'C'
}, {
value: 'D',
children: [{
value: 'H',
children: [{
value: 'K'
}]
}, {
value: 'I'
}]
}]
}])
console.log('广度优先遍历：')
tree.printBFS()
console.log('深度优先遍历：')
tree.printDFS()
如有错误，欢迎大家指正