快捷導航

JavaScript樹形結(jié)構(gòu)數(shù)組處理之遞歸問題

更新時間：2023年06月07日 10:32:50 作者：小熊代碼加

這篇文章主要介紹了JavaScript樹形結(jié)構(gòu)數(shù)組處理之遞歸問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

JS樹形結(jié)構(gòu)數(shù)組處理之遞歸

經(jīng)典示例

var data = [
?{
? ? ?name: "所有物品",
? ? ?children: [
? ? ? ? ?{
? ? ? ? ? ? ?name: "水果",
? ? ? ? ? ? ?children: [{name: "蘋果", children: [{name: '青蘋果'}, {name: '紅蘋果'}]}]
? ? ? ? ?},
? ? ? ? ?{
? ? ? ? ? ? ?name: '主食',
? ? ? ? ? ? ?children: [
? ? ? ? ? ? ? ? ?{name: "米飯", children: [{name: '北方米飯'}, {name: '南方米飯'}]}
? ? ? ? ? ? ?]
? ? ? ? ?},
? ? ? ? ?{
? ? ? ? ? ? ?name: '生活用品',
? ? ? ? ? ? ?children: [
? ? ? ? ? ? ? ? ?{name: "電腦類", children: [{name: '聯(lián)想電腦'}, {name: '蘋果電腦'}]},
? ? ? ? ? ? ? ? ?{name: "工具類", children: [{name: "鋤頭"}, {name: "錘子"}]},
? ? ? ? ? ? ? ? ?{name: "生活用品", children: [{name: "洗發(fā)水"}, {name: "沐浴露"}]}
? ? ? ? ? ? ?]
? ? ? ? ?}
? ]
}]
//遞歸遍歷實現(xiàn)
var recursiveFunction = function(){
? ? var str = ''
? ? const getStr = function(list){
? ? ? ? list.forEach(function(row){
? ? ? ? ? ? if(row.children){
? ? ? ? ? ? ? ? getStr(row.children)
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? str += row.name + ";"
? ? ? ? ? ? }
? ? ? ? })
? ? }
? ? getStr(data)
? ? console.log(str)
}
recursiveFunction()
//輸出：青蘋果;紅蘋果;北方米飯;南方米飯;聯(lián)想電腦;蘋果電腦;鋤頭;錘子;洗發(fā)水;沐浴露;

簡單理解：

let arr = [
?? ?{ name: '小明同學', children: [ { name: '小明同學', children: [ { name: '小明同學' } ] } ] }
]
function fn (arr, newArr = []) {
?? ?arr.forEach(item => {
?? ??? ?typeof item === 'object' && item.name && newArr.push(item.name) ?// 先判斷當前項是否是對象。 當前項是否存在你想要的數(shù)據(jù)。都符合，把數(shù)據(jù)push到新數(shù)組里
?? ??? ?item.children && item.children instanceof Array && fn(item.children, newArr) // 當前項是否還有子節(jié)點，子節(jié)是否是數(shù)組, 如果是繼續(xù)調(diào)用自己。再循環(huán)遍歷一次.
?? ?})
?? ?return newArr
}
fn(arr) // ['小明同學','小明同學','小明同學']
function fn1 (arr, newArr = []) {
?? ?function recursion (arr) {
?? ??? ?arr.forEach(item => {?
?? ??? ??? ?newArr.push(item.name)
?? ??? ??? ?item.children && recursion(item.children)
?? ??? ?})
?? ?}
?? ?recursion(arr)
?? ?return newArr
}
fn1(arr) // ['小明同學','小明同學','小明同學']

遞歸解決多級數(shù)組

1.我們考慮利用遞歸就必須等有一個判斷條件中斷遞歸不然容易出現(xiàn)死循環(huán)

2.我們在進如函數(shù)遞歸是要注意第二次調(diào)用自身是函數(shù)的參數(shù)要是數(shù)據(jù)的子數(shù)據(jù)

實現(xiàn)邏輯

//js遍歷對象
function TraversalObject(obj)
{
? ? for (var a in obj) {
? ? ? ? if (typeof (obj[a]) == "object") {
? ? ? ? ? ? TraversalObject(obj[a]); //遞歸遍歷
? ? ? ? }
? ? ? ? else {
? ? ? ? ? ? alert(a + "=" + obj[a]);//值就顯示
? ? ? ? }
? ? }
}
//遍歷對象中所有Ur的值
function TraversalObject(obj)
{
? ? for (var a in obj) {
? ? ? ? if(a=="Url") ? ?alert(obj[a]);/ /顯示URL的值
? ? ? ? if (typeof (obj[a]) == "object") {
? ? ? ? ? ? TraversalObject(obj[a]); //遞歸遍歷
? ? ? ? }
? ? }
}

這種遍歷方法在對象不規(guī)則但需要獲取相同屬性時起到非常好的作用。

復雜遞歸

遞歸屬性遍歷

一般來說，在JavaScript中考慮復合類型的深層復制的時候，往往就是指對于Date、Object與Array這三個復合類型的處理。

我們能想到的最常用的方法就是先創(chuàng)建一個空的新對象，然后遞歸遍歷舊對象，直到發(fā)現(xiàn)基礎(chǔ)類型的子節(jié)點才賦予到新對象對應的位置。

不過這種方法會存在一個問題，就是JavaScript中存在著神奇的原型機制，并且這個原型會在遍歷的時候出現(xiàn)，然后原型不應該被賦予給新對象。

那么在遍歷的過程中，我們應該考慮使用hasOenProperty方法來過濾掉那些繼承自原型鏈上的屬性：

function clone(obj) {
var copy;
? ? // Handle the 3 simple types, and null or undefined
if (null == obj || "object" != typeof obj) return obj;
? ? // Handle Date
if (obj instanceof Date) {
? ? ? ? copy = new Date();
? ? ? ? copy.setTime(obj.getTime());
return copy;
? ? }
? ? // Handle Array
if (obj instanceof Array) {
? ? ? ? copy = [];
for (var i = 0, len = obj.length; i < len; i++) {
? ? ? ? ? ? copy[i] = clone(obj[i]);
? ? ? ? }
return copy;
? ? }
? ? // Handle Object
if (obj instanceof Object) {
? ? ? ? copy = {};
for (var attr in obj) {
if (obj.hasOwnProperty(attr)) copy[attr] = clone(obj[attr]);
? ? ? ? }
return copy;
? ? }
throw new Error("Unable to copy obj! Its type isn't supported.");
}

調(diào)用如下：

// This would be cloneable:
var tree = {
? ? "left" ?: { "left" : null, "right" : null, "data" : 3 },
? ? "right" : null,
? ? "data" ?: 8
};
// This would kind-of work, but you would get 2 copies of the?
// inner node instead of 2 references to the same copy
var directedAcylicGraph = {
? ? "left" ?: { "left" : null, "right" : null, "data" : 3 },
? ? "data" ?: 8
};
directedAcyclicGraph["right"] = directedAcyclicGraph["left"];
// Cloning this would cause a stack overflow due to infinite recursion:
var cylicGraph = {
? ? "left" ?: { "left" : null, "right" : null, "data" : 3 },
? ? "data" ?: 8
};
cylicGraph["right"] = cylicGraph;

不限層級

//后臺返回來的數(shù)據(jù)形式
?const data = {
? ? "code":"0",
? ? "data":[
? ? ? ? {
? ? ? ? ? ? "data":{
? ? ? ? ? ? ? ? "name":"xx集團香港分公司",
? ? ? ? ? ? ? ? isLeaf:false,
? ? ? ? ? ? ? ? "id":1,
? ? ? ? ? ? ? ? "child":{ ? ??
? ? ? ? ? ? ? ? ? ? "name":"xx集團香港分公司第一分部",
? ? ? ? ? ? ? ? ? ? ?isLeaf:false,
? ? ? ? ? ? ? ? ? ? "id":2,
? ? ? ? ? ? ? ? ? ? "child":{
? ? ? ? ? ? ? ? ? ? ? ? "name":"xx集團香港分公司第二分部",
? ? ? ? ? ? ? ? ? ? ? ? ?isLeaf:false,
? ? ? ? ? ? ? ? ? ? ? ? "id":3,
? ? ? ? ? ? ? ? ? ? ? ? "child":{
? ? ? ? ? ? ? ? ? ? ? ? ? ? "name":"xx集團香港分公司第三分部",
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?isLeaf:false,
? ? ? ? ? ? ? ? ? ? ? ? ? ? "id":4,
? ? ? ? ? ? ? ? ? ? ? ? ? ? "child":{
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? "name":"xx集團香港分公司第第四分部",
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?isLeaf:true,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? "id":5,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? "child":{
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//此處省略層數(shù)不定 可能根據(jù)不同的人的權(quán)限層級樹不一樣 isLeaf為true 代表著在往后已經(jīng)沒有子層級
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ],
? ? "message":"成功"
}
? //因為開發(fā)中我個人自己開發(fā)和使用的控件是數(shù)組形式的 ?后端不小心弄成都是對象形式返回來 因為涉及的業(yè)務(wù)關(guān)聯(lián)表比較多 不方便改 所以作為前端還得處理，個人處理如下：
? 預期想達到的數(shù)據(jù)結(jié)構(gòu)效果：
?? ?"data":[
? ? {
? ? ? ? "name":"xx集團香港分公司",
? ? ? ? isLeaf:false,
? ? ? ? "id":2,
? ? ? ? "child":[ ??
? ? ? ? ? ? {
? ? ? ? ? ? ? ? "name":"xx集團香港分公司",
? ? ? ? ? ? ? ? isLeaf:false,
? ? ? ? ? ? ? ? "id":3,
? ? ? ? ? ? ? ? "child":[ ??
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? "name":"xx集團香港分公司",
? ? ? ? ? ? ? ? ? ? ? ? isLeaf:false,
? ? ? ? ? ? ? ? ? ? ? ? "id":4,
? ? ? ? ? ? ? ? ? ? ? ? "child":[ ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? "name":"xx集團香港分公司",
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? isLeaf:true,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? "id":5,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? child:[{
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }]
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? ]
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ]
? ? ? ? ? ? }
? ? ? ? ]
? ? }
]
? ?//復雜的對象轉(zhuǎn)化成為數(shù)組 遞歸實現(xiàn)
? ? objectToarray(dataObj, arr) {
? ? ? let newObj = {};
? ? ? if (Object.prototype.toString.call(dataObj) === "[object Object]") {
? ? ? ? for (let i in dataObj) {
? ? ? ? ? newObj[i] =
? ? ? ? ? ? i === "child" && !dataObj.isLeaf
? ? ? ? ? ? ? ? this.objectToarray(dataObj[i], [])
? ? ? ? ? ? ? : dataObj[i];
? ? ? ? }
? ? ? ? arr.push(newObj);
? ? ? }
? ? ? return arr;
? ? }
//取到數(shù)據(jù)和將數(shù)據(jù)塞進去進行處理 靜靜等待結(jié)果
?const dataObj = data.data[0].data;
?const result = objectToarray(dataObj , [])?

JS必會技巧之遞歸樹結(jié)構(gòu)

列表轉(zhuǎn)化為樹結(jié)構(gòu)（遞歸樹形結(jié)構(gòu)）

實際開發(fā)中，經(jīng)常會遇到的業(yè)務(wù)需求中，后端傳過來的是數(shù)組中包含許多“形式一樣”的對象，但實際這些對象是由層級關(guān)系的（樹結(jié)構(gòu)）。

因此前端需要經(jīng)過處理，轉(zhuǎn)化為樹結(jié)構(gòu)。

const list = [
    {
        id:1,
        pid:0,
        name:'中國'
    },
    {
        id:2,
        pid:1,
        name:'北京'
    },
    {
        id:3,
        pid:1,
        name:'深圳'
    },
    {
        id:4,
        pid:1,
        name:'武漢'
    },
    {
        id:5,
        pid:1,
        name:'西安'
    },
    {
        id:6,
        pid:2,
        name:'朝陽'
    },
    {
        id:7,
        pid:2,
        name:'海淀'
    }
]
const trancListToTreeData = (data,rootVal)=>{
    const res = [];
    //遍歷查找
    data.forEach((item)=>{
        if(item.pid == rootVal){ //找到了根--找根下面的數(shù)據(jù)
            res.push(item);
            const children = trancListToTreeData(data,item.id) //子節(jié)點
            children.length &&(item.children = children)
        }
    })
    return res;
}
//遍歷樹形的原則--有頭，才知道從哪開始
//要找根
console.log(trancListToTreeData (list,0))