JavaScript 遞歸之深度優(yōu)先和廣度優(yōu)先

在前端工作當中，經(jīng)常會遇到樹組件、樹形表格、機構(gòu)樹等功能，這個時候就需要對后端返回的數(shù)據(jù)進行處理，在對樹形數(shù)據(jù)處理時，一般是需要用到遞歸來處理，而遞歸又分為了深度優(yōu)先和廣度優(yōu)先，這里給出了兩種遞歸方法的示例。

1 數(shù)據(jù)準備

這里是示例當中用到的數(shù)據(jù)

const tree = {id: 1,children: [{id: 2,children: [{id: 4,children: [{ id: 8 },{ id: 9 },]},{ id: 5 },]},{id: 3,children: [{ id: 6 },{ id: 7 },]},] };

2 深度優(yōu)先

顧名思義，深度優(yōu)先的意思就是以深度為主。我們可以把樹機構(gòu)的分支看作為一個個路徑，當進行深度優(yōu)先的遞歸時，程序會在一條路徑下，一直走下去，直到不能在走為止，然后換一個路徑繼續(xù)走到底，走的層級很深。

通過代碼打印的 1, 2, 4, 8, 9 可以看到是把第一個分支里面走到了底。

代碼示例：

function recursion(list){list.forEach(item => {console.log(item.id); // 打印idif(item.children){recursion(item.children);}}); } recursion([tree]); // 調(diào)用函數(shù)，會依次打印：1, 2, 4, 8, 9, 5, 3, 6, 7

3 廣度優(yōu)先

前面說深度優(yōu)先是一條道走到底，類似于遇見了岔道，一條岔道走到了底，直到無路可走，而廣度優(yōu)先則恰恰相反，廣度優(yōu)先是把每一個層級的所有選擇都走一遍，只有當?shù)谝粋€層級走完之后，才會走第二個層級。

以上面的圖為例，先走到1，然后1走完之后，遇見了2和3，廣度優(yōu)先時會先走一下2和3，走完之后，再處理4和5，順序為1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 > 9

代碼示例：

// 方法一： // 先遍歷當前節(jié)點，forEach當中找到當前項所有的子節(jié)點，放到同一個數(shù)組當中 // 也就是找到下一層級的全部節(jié)點 let tempArr = []; function recursion(list){tempArr = [];list.forEach(item => {console.log(item.id);if(item.children){tempArr = tempArr.concat(item.children);}});tempArr.length > 0 && recursion(tempArr); } recursion([tree]); // 調(diào)用函數(shù)，會依次打印：1, 2, 3, 4, 5, 6, 7, 8, 9// 方法二：使用隊列的思想，先進先出，依次將節(jié)點加入到數(shù)組當中，再從前面彈出 function queueRecursion(){while (tempArr.length){let item = tempArr.shift(); // 彈出第一個console.log(item.id);if(item.children){tempArr = tempArr.concat(item.children); // 添加節(jié)點}} } let tempArr = []; tempArr = [tree]; queueRecursion(); // 調(diào)用函數(shù)，會依次打印：1, 2, 3, 4, 5, 6, 7, 8, 9

總結(jié)

以上是生活随笔為你收集整理的JavaScript 递归之深度优先和广度优先的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。