JavaScript實作樹的深度優先遍歷和廣度優先遍歷~
一、來棵樹
1、tree.js
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: []
},
{
val: 'e',
children: []
},
{
val: 'f',
children: []
}
]
},
{
val: 'c',
children: [
{
val: 'g',
children: []
},
{
val: 'h',
children: []
},
{
val: 'i',
children: []
}
]
}
]
}
module.exports = {
tree
}
2、給它畫出來~
二、深度優先遍歷
1、畫圖
2、代碼實作
const { tree } = require('./tree_data')
const dfs = root => {
if(!root) return;
console.log(root.val);
root.children.forEach(child => {
dfs(child)
})
}
dfs(tree)
// a b d e f c g h i
三、樹的廣度優先遍歷
1、畫圖
###### 2、編碼實作
const { tree } = require('./tree_data')
const bfs = root => {
if(!root) return;
const queue = [root];
while(queue.length) {
const top = queue.shift();
console.log(top.val);
top.children.forEach(child => {
queue.push(child)
})
}
}
bfs(tree)
// a b c d e f g h i
寫完啦~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/290894.html
標籤：其他