如何将评论数据从扁平数组结构转为树形结构

蚊子前端博客
发布于 2022-02-28 10:09
以前的文章只讨论了下数据表的设计，这里我们主要讲解下如何从算法上把数组结构的数据转为树形结构

我们在之前的文章 如何实现一个楼中楼的评论系统，主要讲解了楼中楼评论系统的设计初衷、数据库表的结构，但没有讲解从数据库中拿到数据后，如何转成楼中楼的结构。

1. 定义下数据结构

我是使用的 mysql 数据库，mysql 数据库中是以行为单位，来存储数据的。

我们从数据库中拿到的数据是一个数组结构，大致如下，我最初考虑楼中楼最多只嵌套一层，因此加了一个pid字段用来表示该评论在哪个评论里：

COPYJAVASCRIPT
/**
 * 从数据库中查询到一篇文章里的所有评论
 * id: 当前评论的id
 * pid: 当前评论在哪个评论里，0表示是顶层评论
 * replyid: 该评论回复的是哪个评论，0表示是顶层评论
 * content: 内容
 */
const list = [
  { id: 1, pid: 0, replyid: 0, nick: '111', content: '' },
  { id: 2, pid: 0, replyid: 0, nick: '222', content: '' },
  { id: 3, pid: 2, replyid: 2, nick: '333', content: '' },
  { id: 4, pid: 2, replyid: 3, nick: '444', content: '' },
  { id: 5, pid: 2, replyid: 4, nick: '555', content: '' },
  { id: 6, pid: 1, replyid: 1, nick: '666', content: '' },
  { id: 7, pid: 2, replyid: 3, nick: '777', content: '' },
];

接下来，让我们通过代码来实现下数组转为树（楼中楼）的结构。

2. 嵌套一层的楼中楼

我们先实现一个只嵌套一层的树结构。

我们要实现的结构是这样的，若直接回复上层的评论，则省略该评论回复的是谁，若回复的是楼中楼的评论，则展示出回复的是哪条：

COPYBASH
- 1
  |- 6
- 2
  |- 3
  |- 4 -> 3
  |- 5 -> 4
  |- 7 -> 3

我们分析下 list 中数据的特点：

  • 每条数据都有个pid和replyid两个字段，指向他的父级，但若 pid 和 replyid 为 0 时，则表示该评论自己就是最顶层的评论；

  • 后一条评论回复之前的评论，pid 和 replyid 两个字段的值一定是存在的（不可能回复一条不存在的评论）；

依托于 js 中的对象引用的特性：在不同的地方操作相同的对象，所有使用该对象的数据都会发生变化。其实这并不是一个好的特性，但在这里特别好使。我们可以直接把后面的数据添加到前面的数据字段中。

COPYJAVASCRIPT
const listToTree = (list) => {
  const newList = JSON.parse(JSON.stringify(list)); // 避免影响外层的数组
  const map = new Map();
  const result = [];

  newList.forEach((comment) => {
    map.set(comment.id, comment);

    if (comment.pid) {
      // 楼中楼的评论
      const parentComment = map.get(comment.pid); // 回复的该评论，该评论是一定存在的

      if (!parentComment.children) {
        parentComment.children = []; // 通过对象引用，可以直接修改之前的数据
      }
      if (comment.pid !== comment.replyid) {
        comment.replyNick = map.get(comment.replyid).nick;
      }
      parentComment.children.push(comment);
    } else {
      result.push(comment);
    }
  });
  return result;
};

最终实现的效果的示意图：

list2tree-蚊子的前端博客

3. 不限制层数的树结构

若我们不限制树结构的层数，该怎么实现呢？

我们在这里把 list 数组的结构稍微改下，去掉 pid 的干扰，并再添加几条数据：

COPYJAVASCRIPT
/**
 * 从数据库中查询到一篇文章里的所有评论
 * id: 当前评论的id
 * replyid: 该评论回复的是哪个评论，0表示是顶层评论
 * content: 内容
 */
const list = [
  { id: 1, replyid: 0, nick: '111', content: '' },
  { id: 2, replyid: 0, nick: '222', content: '' },
  { id: 3, replyid: 2, nick: '333', content: '' },
  { id: 4, replyid: 3, nick: '444', content: '' },
  { id: 5, replyid: 4, nick: '555', content: '' },
  { id: 6, replyid: 1, nick: '666', content: '' },
  { id: 7, replyid: 3, nick: '777', content: '' },
  { id: 8, replyid: 5, nick: '888', content: '' },
  { id: 9, replyid: 8, nick: '999', content: '' },
  { id: 10, replyid: 9, nick: 'aaa', content: '' },
  { id: 11, replyid: 10, nick: 'bbb', content: '' },
];

其实不限制树结构的层数，要比固定的层数简单一些，不用判断是否要折叠树结构，一直追加下去即可。

3.1 使用循环的方式

我们顺着上面循环的方式，来实现下不限制层数的树结构。

COPYJAVASCRIPT
const listToTreeDeep = (list) => {
  const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组
  const map = new Map();
  const result = [];

  newList.forEach((comment) => {
    map.set(comment.id, comment);

    if (comment.replyid) {
      // 楼中楼的评论
      const parentComment = map.get(comment.replyid); // 回复的该评论，该评论是一定存在的

      if (!parentComment.children) {
        parentComment.children = [];
      }
      // 这里按照层级来表示回复关系，不再获取要回复的哪个评论
      // if (comment.pid !== comment.replyid) {
      //   comment.replyNick = map.get(comment.replyid).nick;
      // }
      parentComment.children.push(comment);
    } else {
      result.push(comment);
    }
  });
  return result;
};

最终实现的效果示意图：

listToTreeDeep-蚊子的前端博客

具体效果可以查看实现的 demo：【 数组转树结构的自定义层数的循环实现方式 】。

3.2 使用递归的方式

无限嵌套的结构也可以使用递归的方式，但这并不是最好的方式，因为每次递归都要用当前 id 循环查找一次。

我们在这里用代码实现一次，但不推荐这种方式。

COPYJAVASCRIPT
/**
 * @param {any[]} list 评论列表
 * @param {number} replyid 回复的那个评论的id
 **/
const listToTreeRecursion = (list, replyid = 0) => {
  const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组
  const result = [];

  newList.forEach((comment) => {
    if (comment.replyid === replyid) {
      comment.children = listToTreeRecursion(list, comment.id);
      result.push(comment);
    }
  });
  return result;
};

递归中我们不使用额外的数据来存储数据，是因为每次的执行，都会从头循环一遍。

4 自定义层数的树结构

若再复杂一点，可以自定义层数 n，前 n-1 层一直向内嵌套，最后的第 n 层采用平铺的方式。即把前面的两种展示方式进行结合。

这里我们依然分成两部分来讲解。

4.1 使用循环的方式

上面不限制层数时，直接往其父级的 children 属性中追加即可。但现在可以自定义层数后，就要在循环时，判断当前节点的深度，若该节点的深度小于 设定的层数 n ，则添加到其父级的 children 中；否则就得添加到其深度为 n-1 的祖先节点的 children 里。

我在这里使用了两个字段来进行标记：

  1. deep: 当前节点的深度；

  2. pid: 该节点所属的父级节点是哪个；

具体的代码实现：

COPYJAVASCRIPT
/**
 * @param {any[]} list 评论列表
 * @param {number} maxPath 自定义的层数
 **/
const listToTreeSelf = (list, maxPath = 4) => {
  const newList = JSON.parse(JSON.stringify(list));
  const map = new Map();
  const result = [];

  newList.forEach((comment) => {
    map.set(comment.id, comment);

    if (comment.replyid) {
      // 楼中楼的评论
      const parentComment = map.get(comment.replyid);
      comment.deep = parentComment.deep + 1; // 当前深度是父级节点的深度+1

      if (comment.deep >= maxPath) {
        // 若当前节点的深度超过了设定的最大深度
        // 则该节点不能挂载在其父节点了，
        // 通过父节点的pid查找父节点挂载在哪个节点上，
        // 该节点也挂载上面
        const ancestorComment = map.get(parentComment.pid);

        comment.replyNick = parentComment.nick;
        if (!ancestorComment.children) {
          ancestorComment.children = [];
        }

        // 当前节点挂载的节点
        comment.pid = ancestorComment.id;
        ancestorComment.children.push(comment);
      } else {
        // 没有超过设定的最大深度
        // 挂载在其父节点上
        if (!parentComment.children) {
          parentComment.children = [];
        }
        comment.pid = parentComment.id;
        parentComment.children.push(comment);
      }
    } else {
      comment.deep = 0;
      result.push(comment);
    }
  });
  return result;
};

假设我们设定的最大层数为 4，最终的效果是：

listToTreeSelf-蚊子的前端博客

4.2 使用递归的方式

在使用递归的方式来构建自定义层数的树形结构时，当深度达到设定的最大层级时，就需要转为循环了。然后开始查找该节点下所有的子节点和子孙节点。

注意：这里不要遗漏子孙节点。

COPYJAVASCRIPT
const listToTreeSelfRecursion = (list, maxPath = 4, replyid = 0) => {
  const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组
  const result = [];

  newList.forEach((comment) => {
    if (maxPath <= 1) {
      // 到达最内层
      // 查找最直接的子节点
      if (comment.replyid === replyid) {
        result.push(comment);
      } else {
        // 查找所有的子孙节点
        const child = result.find((child) => child.id === comment.replyid);
        if (child) {
          comment.replyNick = child.nick;
          result.push(comment);
        }
      }
    } else {
      // 还可以继续递归
      if (comment.replyid === replyid) {
        comment.children = listToTreeSelfRecursion(list, maxPath - 1, comment.id);
        result.push(comment);
      }
    }
  });
  return result;
};

5. 不规则的数组

我们在上面所有的循环实现中，都默认了父节点在前面，毕竟对评论系统而言，肯定现有的父级评论，才能有当前评论。但比如我们把场景扩展到无限嵌套的部门列表中时，就不一定有序了。

最近新创建了一个中间部门，然后把下面所有的部门都归属到这个中间部门里。就会出现父级节点在后面的情况。

这里我们只以不限层数的循环实现方式为例，看下若父级节点在后面，如何实现：

COPYJAVASCRIPT
// 把数据调换下位置
const list = [
  { id: 6, pid: 1, replyid: 1, nick: '666', content: '' },
  { id: 7, pid: 2, replyid: 3, nick: '777', content: '' },
  { id: 8, pid: 2, replyid: 5, nick: '888', content: '' },
  { id: 9, pid: 2, replyid: 8, nick: '999', content: '' },
  { id: 10, pid: 2, replyid: 9, nick: 'aaa', content: '' },
  { id: 11, pid: 2, replyid: 10, nick: 'bbb', content: '' },
  { id: 1, pid: 0, replyid: 0, nick: '111', content: '' },
  { id: 2, pid: 0, replyid: 0, nick: '222', content: '' },
  { id: 3, pid: 2, replyid: 2, nick: '333', content: '' },
  { id: 4, pid: 2, replyid: 3, nick: '444', content: '' },
  { id: 5, pid: 2, replyid: 4, nick: '555', content: '' },
];

const listToTreeDeep = (list) => {
  const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组
  const map = new Map();
  const result = [];

  newList.forEach((comment) => {
    // 可能先把该节点的children存储起来
    // 这里把之前存储的数据合并下，然后再存储起来
    comment = { ...comment, ...map.get(comment.id) };
    map.set(comment.id, comment);

    if (comment.replyid) {
      // 楼中楼的评论
      const parentComment = map.get(comment.replyid) || {}; // 以空的Object兜底

      if (!parentComment.children) {
        parentComment.children = [];
      }
      parentComment.children.push(comment);
      map.set(comment.replyid, parentComment);
    } else {
      result.push(comment);
    }
  });
  return result;
};

可见在乱序的情况下，逻辑就要多一些。在可行的情况，我们把父级节点放在前面，但若实现起来比较困难，上面的那种方式也是可行的。

6. 总结

我们从最开始的二层楼中楼结构，扩展到了无限层级，最终扩展到了可以自定义层级。就目前递归的实现方式来看，并没有循环的性能好，因为每次递归都要循环一遍数据，若在数组节点比较多时，递归的性能就会直线下降。

下一篇文章，我们再讨论下，如何把树形结构转成数组结构。

标签：
阅读(866)

公众号：

qrcode

微信公众号：前端小茶馆

相关文章

如何实现一个楼中楼的评论系统 (2017/09/01)
博客里评论系统的前端总结 (2019/03/31)
树形结构转为扁平数组结构 (2022/03/03)

公众号：

qrcode

微信公众号：前端小茶馆