将数组转成树结构 (动态路由权限)

“这是我参与2022首次更文挑战的第2天，活动详情查看：2022首次更文挑战”

在后端返回的数据式中，以以下格式存储信息是相当普遍的，尤其是在存在一对多父/子节点关系的情况下：

const data = [
  { id: 56, parentId: 62 },
  { id: 81, parentId: 80 },
  { id: 74, parentId: null },
  { id: 76, parentId: 80 },
  { id: 63, parentId: 62 },
  { id: 80, parentId: 86 },
  { id: 87, parentId: 86 },
  { id: 62, parentId: 74 },
  { id: 86, parentId: 74 },
];

那么，如何从这种对象数组格式转变为分层树格式？

const tree = {
  id: 74,
  parentId: null,
  children: [
    {
      id: 62,
      parentId: 74,
      children: [{ id: 56, parentId: 62 }, { id: 63, parentId: 62 }],
    },
    {
      id: 86,
      parentId: 74,
      children: [
        {
          id: 80,
          parentId: 86,
          children: [{ id: 81, parentId: 80 }, { id: 76, parentId: 80 }],
        },
        { id: 87, parentId: 86 },
      ],
    },
  ],
};

数据算法

数组中的每个元素都是一个“节点”。一个节点可以是多个节点的“父级”，也可以是一个节点的“子级”。在下面的图片，86是80和87的“父级”。74的“子级”是86。我们树的顶部节点是“根”。

要构建我们的树，我们将要：

1. 遍历data数组
2. 查找当前元素的父元素
3. 在父元素的对象中，添加对子元素的引用
4. 如果某个元素没有父元素，那么我们知道这将是树的“根”元素

首先保存对应关系，方便我们通过儿子可以快速找到父亲。

const idMapping = data.reduce((acc, el, i) => {
  acc[el.id] = i;
  return acc;
}, {});

通过对象是引用类型的机制我们可以这样创建树结构。

let root;
data.forEach(el => {
  // 根节点
  if (el.parentId === null) {
    root = el;
    return;
  }
  // 父节点
  const parentEl = data[idMapping[el.parentId]];
  // 子节点
  parentEl.children = [...(parentEl.children || []), el];

});

当您利用JavaScript对象引用时，这实际上变得相当容易。无需递归即可在 O（n）时间内完成。

路由权限

后台提供的菜单列表，通常也是数组，他们通常不会直接把树结构保存到数据库中。其中 auth 字段是权限的唯一标识。

const data = [
  { parentId: -1, id: 1, name: '首页', path: '/home', auth: 'home' },
  { parentId: 1, id: 2, name: '列表', path: '/list', auth: 'list' },
  { parentId: -1, id: 3, name: '推荐', path: '/rank', auth: 'rank' },
  { parentId: -1, id: 4, name: '关于', path: '/about', auth: 'about' },
]

路由权限分为默认权限 defaultRoutes 和动态权限 authRoutes。

// 定义默认路由
export let defaultRoutes = [
  {
    path: '/about',
    component: about
  },
  {
    path: '*',
    component: about
  }
]
// 定义动态路由
export let authRoutes = [
  {
    path: '/home',
    component: home,
    name: 'home'
    children: [
      {
        path: 'list',
        component: list,
        name: 'list'
      }
    ]
  },
  {
    path: '/rank',
    component: rank,
    name: 'rank'
  }
]

export default new Router({
  mode: 'history',
  base: process.env.BASE_URL,
  routes: defaultRoutes // 默认
})

格式化后端的动态路由，计算出菜单树结构，然后使用 element--ui 的菜单组件渲染页面。authList 是权限标识的列表，menuList 是树结构列表（给 UI 组件用的）。

let formatMenuList = (data) => {
  const idMapping = data.reduce((acc, el, i) => {
    acc[el.id] = i;
    return acc;
  }, {});
  const authList = []
  const menuList = data.filter(el => {
    authList.push(el.auth)
    if (el.parentId === -1) {
      return el;
    }
    const parentEl = data[idMapping[el.parentId]];
    parentEl.children = [...(parentEl.children || []), el];
  });
  return [authList, menuList]
}
// authList [ 'home', 'list', 'rank', 'about' ]
// menuList ...

过滤掉没有权限的页面，在动态权限 authRoutes 中判断是否存在 authList 中。

let formatAuthList = (authList) => {
  function r(authRoutes) {
    return authRoutes.filter(route => {
      if (authList.includes(route.name)) {
        if (route.children) {
          route.children = r(route.children)
        }
        return true
      }
    })
  }
  return r(authRoutes)
}

添加路由钩子处理

// 只要页面切换就执行的钩子
// 根据权限动态添加路由 （我们的路由要分成两部分 一部分是有权限 另一部分是没权限的）
router.beforeEach(async (to,from,next)=>{
  // 当前有没有获取过权限，如果获取过了 就不要在获取了
  if(!store.state.hasRules){
    // 获取权限,获取权限，调用获取权限的接口
    await store.dispatch('getMenuList'); // 去action中获取数据
    let r = await store.dispatch('getAuthRoute');
    router.addRoutes(r); // history.resplace()
    next({...to,replace:true}); // hack 为了保证addRoute添加成功后在跳转
  }else{
    next(); // 如果已经获取了权限就可以访问页面了
  }
})

vuex配合路由一般这么操作

export default new Vuex.Store({
  state: {
     // 存放菜单的数据
     menuList:[],
     authList:[], // iview 角色 admin
     buttonAuth:{},
     hasRules:false // 表示没有获取过权限，获取完毕后 把状态改成true
  },
  mutations: {
    set_menuList(state,m){
      state.menuList = m;
    },
    set_authList(state, a){
      state.authList = a;
      state.hasRules = true;
    }
  },
  actions: {
    async getMenuList({commit}){
      let {data} = await axios.get('http://localhost:3000/role');
      let {menuList, authList} = formatMenuList(data.menuList);
      commit('set_menuList',menuList);
      commit('set_authList',authList);
    },
    async getAuthRoute({commit,state}){
      // 要拿到所有权限的路由  权限列表了
      let r = formatAuthList(state.authList);
      // 当前需要动态添加的路由
      return r;
    }
  }
})

数据结构和算法无处不在，我们要学会在实践中落地和使用。扁平化数组转换成为树结构也是一道很经典的算法题目，希望每个人都学会。

点赞再看，养成好习惯，谢谢大家！