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

以前的文章只讨论了下数据表的设计，这里我们主要讲解下如何从算法上把数组结构的数据转为树形结构

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

1. 定义下数据结构

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

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

/**
 * 从数据库中查询到一篇文章里的所有评论
 * 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. 嵌套一层的楼中楼

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

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

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

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

每条数据都有个pid和replyid两个字段，指向他的父级，但若 pid 和 replyid 为 0 时，则表示该评论自己就是最顶层的评论；
后一条评论回复之前的评论，pid 和 replyid 两个字段的值一定是存在的（不可能回复一条不存在的评论）；

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

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 的干扰，并再添加几条数据：

/**
 * 从数据库中查询到一篇文章里的所有评论
 * 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 使用循环的方式

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

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 循环查找一次。

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

/**
 * @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 里。

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

deep: 当前节点的深度；
pid: 该节点所属的父级节点是哪个；

具体的代码实现：

/**
 * @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 使用递归的方式

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

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

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. 不规则的数组

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

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

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

// 把数据调换下位置
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;
};

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

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

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

1. 定义下数据结构

2. 嵌套一层的楼中楼

3. 不限制层数的树结构

3.1 使用循环的方式

3.2 使用递归的方式

4 自定义层数的树结构

4.1 使用循环的方式

4.2 使用递归的方式

5. 不规则的数组

Recommend

Samsung announces Galaxy Book2 Pro Series delivering mobile-first PC experiences...

数据治理一体化实践之体系化建模

How to do an Impossible Join with String Split

Armbian 22.02 has been released

Stop aggregating away the signal in your data

Free Static HTML Website Templates, 2021 Updated

黑客组织窃取了英伟达7万多名员工的登陆凭证，以及两份代码签名证书

网络协议之:socket协议详解之Unix domain Socket

Sematext recognized as one of the Best Software Products by G2 and Gartner revie...

YDS: What Happens When The Scrum Master Goes on Vacation?

About Joyk