前端List结构与Tree结构相互转换（详解）

1.数据结构

一个典型的数结构应该是这样的：

const treeData = [
  {
    id:"p1",
    title: '广东',
    children: [{
      id:"p1-1",
      title: '广州',
    }]
  },
  {
    id:"p2",
    title:"四川",
    children:[{
      id:"p2-1",
      title:"成都",
      children: [{
        id:"p2-1-1",
        title:"武侯区",
      }]
    },
    {
      id:"p2-2",
      title:"自贡"
    },
    {
      id:"p2-3",
      title:"绵阳"
    }]
  }
]

但有时后端传过来的数据却是一个平铺的数据：

      const listData = [
        {
          id: "p1",
          title: '广东',
        },
        {
          id: "p1-1",
          pid: 'p1',
          title: '广州',
        },
        {
          id: "p2",
          title: "四川",
        },
        {
          id: "p2-1",
          pid: 'p2',
          title: "成都",
        },
        {
          id: "p2-2",
          pid: 'p2',
          title: "自贡"
        },
        {
          id: "p2-3",
          pid: 'p2',
          title: "绵阳"
        },
        {
          id: "p2-1-1",
          pid: 'p2-1',
          title: "武侯区",
        }
      ]

这个时候就需要前端人员进行根据id和pid遍历数据生成一个树形的结构。当然有些时候我们也需要将树形结构转换为扁平的数组形式。

2.List转Tree

1.递归

function list2tree(list) {
  const tree = []
  for(const node of list) {
    // 如果没有pid就可以认为是根节点
    if(!node.pid) {
      let p = { ...node }
      p.children = getChildren(p.id, list)
      tree.push(p)
    }
  }
  function getChildren(id, list) {
    const children = []
    for(const node of list) {
      if(node.pid === id) {
        children.push(node)
      }
    }
    
    for(const node of children) {
       const children = getChildren(node.id, list)
       if(children.length) {
         node.children = children
       }
    }
    
    return children
  }
  
  return tree
}

        通过检查 pid 是否为 null 或 undefined 来确定根节点。
        通过递归调用 getChildren 函数，为每个节点找到它的子节点，并将这些子节点添加到节点的 children 属性中。
        getChildren 函数通过递归的方式不断查找每个节点的子节点，直到没有更多的子节点为止。 

2.双重循环

function list2tree(list) {
  list.forEach(child => {
    const pid = child.pid
    if(pid) {
      list.forEach(parent => {
        if(parent.id === pid) {
          parent.children = parent.children || []
          parent.children.push(child)
        }
      })
    }
  })
  return list.filter(n => !n.pid)
}

 第一次 forEach 循环遍历每个节点，将其视为子节点。
第二次 forEach 循环遍历每个节点，将其视为父节点，并检查是否匹配当前子节点的 pid，如果匹配，将子节点添加到父节点的 children 数组中。
最后，过滤出所有没有 pid 的节点，这些节点就是树的根节点。

3.Map

function list2tree(list) {
  const [map, treeData] = [{}, []];

  for (let i = 0; i < list.length; i += 1) {
    map[list[i].id] = i;
    list[i].children = [];
  }

  for (let i = 0; i < list.length; i += 1) {
    const node = list[i];
    if (node.pid && list[map[node.pid]]) {
      list[map[node.pid]].children.push(node);
    } else {
      treeData.push(node);
    }
  }
  return treeData;
}

3.Tree转List

树形结构转换为数组就涉及到树的遍历了，树的遍历分为深度遍历（前中后序）和广度遍历，下面分别使用深度遍历和广度遍历来遍历树并转为数组。

1.广度遍历

沿着树的宽度遍历节点。采用队列来辅助完成广度遍历。

function tree2list(tree) {
  const list = []
  const queue = [...tree]
  while(queue.length) {
    const node = queue.shift()
    const children = node.children
    if(children) {
        queue.push(...children)
    }
    list.push(node)
  }
  return list
}

2.深度遍历

沿着树的深度遍历。采用栈来辅助完成深度遍历。

function tree2list(tree) {
  const list = []
  const stack = [...tree]
  while(stack.length) {
    const node = stack.pop()
    const children = node.children
    if(children) {
        queue.push(...children)
    }
    list.push(node)
  }
  return list
}