巧妙利用引用,将数组转换成树形数组

更新日期: 2019-11-09阅读: 2.6k

前言

笔者所做的一个项目需要做一个前端的树形菜单,后端返回的数据是一个平行的list,list中的每个元素都是一个对象,例如list[0]的值为{id: 1, fid: 0, name: 一级菜单},每个元素都指定了父元素,生成的菜单可以无限级嵌套。一开始找的插件需要手动将生成好的树形数组传进去才能使用(尽管后来找到了一个UI框架,可以直接传list进去,只需要指定id和fid),但是当时思索了好久都没能正确写出来,故在空下来的时候认真想了一下,整理成笔记,以便后期查阅。


准备工作

因为是前端处理,所以本文实现语言为js。

如下,有一个平行的list列表和一个不在list中的根节点root:

var s = [
  { id: 1, fid: 0, name: "第一级菜单1" },
  { id: 2, fid: 0, name: "第一级菜单2" },
  { id: 3, fid: 1, name: "第二级菜单1.1" },
  { id: 4, fid: 1, name: "第二级菜单1.2" },
  { id: 5, fid: 2, name: "第二级菜单2.1" },
  { id: 6, fid: 3, name: "第三级菜单1.1.1" },
  { id: 7, fid: 3, name: "第三级菜单1.1.2" },
  { id: 8, fid: 4, name: "第三级菜单1.2.1" },
  { id: 9, fid: 4, name: "第三级菜单1.2.2" },
  { id: 10, fid: 6, name: "第四级菜单1.1.1.1" },
  { id: 11, fid: 6, name: "第四级菜单1.1.1.2" },
  { id: 12, fid: 9, name: "第四级菜单1.2.2.1" },
  { id: 13, fid: 9, name: "第四级菜单1.2.2.2" },
  { id: 14, fid: 0, name: "第一级菜单3" }
]

var root = { id: 0, fid: 0, name: "根菜单" };

需要整理成类似于下面的样子,如果该节点没有子节点,就没有node属性:

{
    id: xx,
    fid: xx,
    name: xx,
    node: [
        id: xx,
        fid: xx,
        name: xx,
        node: [...]
    ]
}

需要一个打乱list顺序的shuffle算法,该算法会对原数组进行影响:

function shuffle(a) {
  var len = a.length;
  for (var i = 0; i < len; i++) {
    var end = len - 1;
    var index = (Math.random() * (end + 1)) >> 0;
    var t = a[end];
    a[end] = a[index];
    a[index] = t;
  }
};

使用JSON序列化来实现数组的深度拷贝:

function deepCopy(arr) {
  return JSON.parse(JSON.stringify(arr));
}

使用一个简单的方式来初步判断结果是否正确:

function check(node) {
    return JSON.stringify(node).match(/菜单/g).length;
}

使用递归

【思路】

对于这种问题,因为不知道到底要循环多少层,所以使用递归能够以一种很方便的方式来解决。

【步骤】

1. 遍历当前列表,找出fid为传入的父元素的id的节点,并挂到父元素的node上;

2. 每找到一个节点就从当前列表删除这个元素(不然递归怎么终止);

3. 对于每一个子节点,重复如上步骤,将子节点当成下一层的父节点继续查找该节点的子节点。

可以看到,时间复杂度最坏为O(n!)。

【实现】

function arr2tree(arr, father) {
  // 遍历数组,找到当前father的所有子节点
  for (var i = 0; i < arr.length; i++) {   
    if (arr[i].fid == father.id) {
      // 这里是有子节点才需要有node属性(也就是说有node里绝不会为空list)
      if (!father.node) { 
        father.node = [];
      }
      var son = arr[i];
      father.node.push(son);
      arr.splice(i, 1); // 删除该节点,当list为空的时候就终止递归
      i--; // 由于删除了i节点,所以下次访问的元素下标应该还是i
    }
  }
  // 再对每一个子节点进行如上操作
  if (father.node) { // 需要先判断有没有子节点
    var childs = father.node;
    for (var i=0; i<childs.length; i++) {
      arr2tree(arr, childs[i]); // 调用递归函数
    }
    // 用于按名称进行排序,如果不强调顺序可以去掉
    father.node.sort(function (a, b) {
      return a.name > b.name;
    })
  }
}

【检验】

shuffle(s); // 打乱数组
var arr = deepCopy(s); // 拷贝一份,避免对原数组进行修改
arr2tree(arr, root);
console.log(check(root)); // 预期输出15
console.log(root); // 手工检查输出是否正确

不使用递归

【思路】

当数据量大的时候,使用递归及其容易因为内存溢出而无法运行,有没有不使用递归的方式呢?能不能够直接就用循环来搞定呢?能不能边遍历这个元素,就直接把这个元素放到正确的位置上,这样就可以省好多事情。可以用一个哈希表(字典/对象)来储存这些元素,键(属性名)就是元素的id,这样就可以直接判断当前遍历的元素的父元素在不在哈希表里面了。

忽然,笔者想到了一个特性——引用js中的对象都是引用的,哪怕我已经把a对象push进一个list中了,我在后面对a对象进行的任何修改都会在list中反映出来。也就是说,我把a元素挂到对应的父元素f上了,当我在后面找到a元素的子元素b时,我把该子元素b挂到a上,f中挂载的a也会一样有b元素。

【步骤】

1. 新建一个对象temp用于存放临时信息。遍历列表,将当前访问元素a加到temp中(属性名为对象id,属性值为该对象);

2. 在temp中查找是否有a的子节点,有的话就将子节点挂到a上;

3. 在temp中查找是否有a的父节点,有的话就将a挂到父节点上;

可以看到,时间复杂度为O(n^2^),空间复杂度也不会太高,该方法不会对原数组进行修改。

【实现】

function arr2tree2(arr, root) {
  var temp = {};
  temp[root.id] = root;
  for (var i = 0; i < arr.length; i++) {
    // 插入一个新节点,后面对该节点的修改都会同步到该节点的父节点上
    temp[arr[i].id] = arr[i];
    // 查找是否有子节点
    var keys = Object.keys(temp);
    for (var j = 0; j < keys.length; j++) {
      if (temp[keys[j]].fid == arr[i].id) {
        temp[arr[i].id].node ? "" : temp[arr[i].id].node = [];
        temp[arr[i].id].node.push(temp[keys[j]]); // 将该子节点挂到当前节点的node上
      }
    }
    // 查找是否有父节点
    if (temp[arr[i].fid]) {
      temp[arr[i].fid].node ? "" : temp[arr[i].fid].node = [];
      temp[arr[i].fid].node.push(arr[i]); // 将当前节点挂到父节点的node上
    }
  }
  return temp;
}

【检验】

shuffle(s); // 打乱数组
var result = arr2tree2(s, root);
console.log(check(result[root.id])); // 预期输出15
console.log(result[root.id]); // 手工检查输出是否正确

总结

平时笔者所做的项目大多也不涉及到算法,平时秉承的也是能用循环解决的就用循环解决,可以看到,算法对于程序员而言还是很重要的,本文也只是个人的想法,欢迎一起探讨。

链接: https://fly63.com/article/detial/6514

挑战常规--不要使用||赋予默认值

js是一种弱类型的编程语言,代表着传入的变量并不清楚作为何种类型使用。对js来说传入的任意参数都应该考虑不同类型的结果,而不是单单考虑一种情况。若传入0、false等,||所要实现默认值的功能完全错误的

YodaOS 中是如何生成 API 的

本文简单介绍了 YodaOS 在 API 设计过程中,如何利用 DSL,解决 YodaOS API 在多种应用形态保持一致性。以此,我们希望抛砖引玉:帮助读者更好地了解 YodaOS API 的生成过程,帮助读者了解到 DSL,也能将这种思路应用在自己的项目中

JavaScript 私有成员

JavaScript 一直没有私有成员并不是没有原因,所以这一提议给 JavaScript 带来了新的挑战。但同时,JavaScript 在 ES2015 发布的时候已经在考虑私有化的问题了,所以要实现私有成员也并非毫无基础。

web前端学习之路

对于程序员来说,如果哪一天开始他停止了学习,那么他的职业生涯便开始宣告消亡。这不是什么危言耸听的怪语,而是一位大牛几年前告诉我的,他的信条。

web前端开发好学吗?

随着互联网+时代的到来,移动互联网行业的发展也是突飞猛进。无论你是否承认,这个时代已经被网页所包围了,这所有一切,都是前端工程师的杰作。今天给大家聊的就是\"前端真的好学吗?\"

Web前端小白入门

Web前端开发怎么入门,主要都有哪些要素组成?Web前端开发是由网页制作演变而来的,主要由HTML、CSS、JavaScript三大要素组成。专业的Web前端开发入门知识也一定会包含这些内容,下面就给大家简单介绍一下。

highcharts 时间少8小时问题

Highcharts 中默认开启了UTC(世界标准时间),由于中国所在时区为+8,所以经过 Highcharts 的处理后会减去8个小时。如果不想使用 UTC,有2种方法可供使用:

NodeJS/JWT/Vue 实现基于角色的授权

在本教程中,我们将完成一个关于如何在 Node.js 中 使用 JavaScript ,并结合 JWT 认证,实现基于角色(role based)授权/访问的简单例子。作为例子的 API 只有三个路由,以演示认证和基于角色的授权

forward和redirect的区别?http状态码301,302分别代表什么?

从地址栏显示来说:forward是服务器内部重定向,客户端浏览器的网址不会发生变化;redirect发生一个状态码,告诉服务器去重新请求那个网址,显示的的新的网址数据共享:forward使用的是同一个request

为什么不建议使用 index 作为 key 值

使用 index 作为 key 值有什么问题呢? 在我们日常开发中我们经常会和 key 值打交道. 但是我们扪心自问, 真的理解 key 吗? 我想大多数朋友可能会有些许犹豫.

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!