「算法学习」：扁平数据结构转tree、数据结构扁平化

扁平数据结构转tree

//给定的数据结构
let arr = [
    {id: 1, name: '分部1', parentsId: 0},
    {id: 2, name: '分部2', parentsId: 1},
    {id: 3, name: '分部3', parentsId: 1},
    {id: 4, name: '分部4', parentsId: 3},
    {id: 5, name: '分部5', parentsId: 4},
]

//转换后的数据结构
 [
    {
        "id":1,
        "name":"分部1",
        "parentsId":0,
        "children":[
            {
                "id":2,
                "name":"分部2",
                "parentsId":1,
                "children":[]
            },
            {
                "id":3,
                "name":"分部3",
                "parentsId":1,
                "children":[
                    {
                        "id":4,
                        "name":"分部4",
                        "parentsId":3,
                        "children":[
                            {
                                "id":5,
                                "name":"分部5",
                                "parentsId":4,
                                "children":[]
                            }
                        ]
                    }
                ]
            }
        ]
    }
]

递归解法

/**
 * 递归查找，将根节点传进去，然后遍历节点数组，递归的将item.id传入，判断是否为当前元素的父节点，是则推进children数组
 */
const getChildren = (data, result, pid) => {
  for (const item of data) {
    if (item.parentsId === pid) {
      const newItem = {...item, children: []};
      result.push(newItem);
      //递归的将item.id传入，判断parentsId 是否为当前元素的父节点，是则推进children数组
      getChildren(data, newItem.children, item.id);
    }
  }
}

/**
* 转换方法
*/
const arrayToTree = (data, pid) => {
  const result = [];
  getChildren(data, result, pid)
  return result;
}

for循环+Map

function arrayToTree(arr) {
  const result = [];   // 存放结果集
  const itemMap = {};  // Map结构存放数组引用
    
  // 把数据转成Map去存储，之后儿子节点直接推引用进栈，时间复杂度为O(2n)，空间复杂度O(n)
  for (const item of arr) {
    itemMap[item.id] = {...item, children: []}
  }
  
  for (const item of arr) {
    const id = item.id;
    const pid = item.parentsId;
    const treeItem =  itemMap[id];
    if (pid === 0) {
      //根节点直接推入结果数组
      result.push(treeItem);
    } else {
      //当Map中没有pid存在的父节点时候赋children空数组对象
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      //匹配到父节点将子节点推入
      itemMap[pid].children.push(treeItem)
    }

  }
  //返沪结果
  return result;
}

//优化
function arrayToTree(arr) {
  const result = [];   // 存放结果集
  const itemMap = {};  // 
  for (const item of arr) {
    const id = item.id;
    const pid = item.pid;

    itemMap[id] = {
      ...item,
      children: []
    }

    const treeItem =  itemMap[id];

    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }

  }
  return result;
}

结构扁平化

对象扁平化

let obj = { a: { d: 1 }, 
            d:  2, 
            e: [3, 4],
            f:{},
            g:[]
          }

function flatten(data) {
    var result = {};
    function recurse(cur, prop) {
        // 如果输入进来的是不是对象，就将其放在数组中，返回
        // console.log(Object(cur),cur,Object(cur) !== cur)
        if (Object(cur) !== cur) {
            result[prop] = cur;
        // 如果输入进来的是数组，长度不为0就递归数组，得出结果
        } else if (Array.isArray(cur)) {
            for (var i = 0, len = cur.length; i < len; i++)
                recurse(cur[i], prop + `[${i}]`);
            //为0则是空数组情况，推入空数组
            if (len == 0)  result[prop] = [];
        } else {
        //当前是对象时候递归
            var isEmpty = true;
            for (var p in cur) {
                console.log(prop,p)
                isEmpty = false;
                recurse(cur[p], prop ? `${prop}.${p}` : p);
            }
            //如果为空无法进行遍历则推入空对象
            if (isEmpty && prop)
                result[prop] = {};
        }
    }
    //执行深度遍历
    recurse(data, "");
    return result;
};

console.log(flatten(obj))  // {a.d: 1, d: 2, e[0]: 3, e[1]: 4,f:{},g:[]}

数组扁平化

toString()+split()

//先将数组转化为字符串，在使用split将字符串转化为数组，然后对元素进行基本型转换
let arr = [1, [2, 3, [4, 5]]]
function flat(arr) {
    return arr.toString().split(',').map( item => Number(item))
}
console.log(flat(arr)) // [1, 2, 3, 4, 5]

reduce

let arr = [1, [2, 3, [4, 5]]] 
const flat = function(arr){
  return arr.reduce((pre,cur)=>pre.concat(Array.isArray(cur)?flat(cur):cur),[])
}
console.log(flat(arr)); // [1,2,3,4,5]

递归

let arr = [1, [2, 3, [4, 5]]] 
function flat(arr) {
    var res = [];
    arr.map(item => {
        if(Array.isArray(item)) {
            res = res.concat(flat(item));
        } else {
            res.push(item);
        }
    });
    return res;
}
console.log(flat(arr)) // [1,2,3,4,5]

扩展运算符+some

let arr = [1, [2, 3, [4, 5]]] 
   function flat(arr) {
     while (arr.some(item => Array.isArray(item))) {
       arr = [].concat(...arr);
     }
     return arr;
   }
console.log(flat(arr)); // [1, 2, 3, 4, 5]

flat()

 let arr1 = [1, 2, [3, 4]];
 arr1.flat(); // [1, 2, 3, 4],flat()不传值的时候默认提取一层嵌套

 // 指定要提取嵌套数组的结构深度为1层
 let arr2 = [1, 2, [3, 4, [5, 6]]];
 arr2.flat(1); // [1, 2, 3, 4, [5, 6]]

 // 指定要提取嵌套数组的结构深度为2层
 let arr3 = [1, 2, [3, 4, [5, 6]]];
 arr3.flat(2); // [1, 2, 3, 4, 5, 6]

 // 使用 Infinity 作为深度，展开任意深度的嵌套数组
 let arr4 = [1, 2, [3, 4, [5, 6]]]
 arr4.flat(Infinity); // [1, 2, 3, 4, 5, 6]

 // 移除数组中的空项
 let arr5 = [1, 2, , 4, 5];
 arr5.flat(); // [1, 2, 4, 5]