树转合并单元格的实现

不难想到，树形结构和合并单元格之间是可以相互转换的。我们可能会遇到有业务场景需要以合并单元格的形式展示，但是数据结构是以树的形式维护的。

如图：

   Tree
   /  \
  A    B
 /\   
C  D

预期我们需要转换成这样：

我们以vue为实例，实现树与合并单元格的转换

数据结构分析

树结构我们约定为以children为子节点的属性，结构如下：

{
  id: 'root',
  text: 'tree',
  children: [
    {
      id: 'eb1d5347-0a91-4d9c-99d5-a65a98f84147',
      text: 'A',
      children: [
        {
          id: '7b5a2809-70c8-4460-987b-b2df5649c672',
          text: 'C',
        },
        {
          id: '02a66fd8-4f6d-4bea-aca8-00e5e33c0d63',
          text: 'D',
        }
      ]
    },
    {
      id: '78de42cb-7b25-495d-ac7e-02a180d1f28f',
      text: 'B',
    }
  ]
}

那么需要转换成什么样的数据结构才能生成这样的表格呢？

<table>
    <tbody>
        <tr>
            <td colspan="1" rowspan="3">
                tree
            </td>
            <td colspan="1" rowspan="2">
                A
            </td>
            <td colspan="1" rowspan="1">
                C
            </td>
        </tr>
        <tr>
            <td colspan="1" rowspan="1">
                D
            </td>
        </tr>
        <tr>
            <td colspan="2" rowspan="1">
                B
            </td>
        </tr>
    </tbody>
</table>

首先它DOM结构是这样子的，v-for根据每一行每一列来遍历，因此需要的数组应该是：[[tree,A,C],[D],[B]]这种嵌套数组的形式;
其次，每一个item上都有对应的属性colspan，rowspan和text。因此最终的每一个元素应该有这三个属性。

所以：我们最终需要将树结构转换成嵌套数组，每个数组元素带colspan，rowspan和text属性：

[
    [
        { "id": "root", "text": "tree", "children": null, "level": 1, "leafCount": 3, "isLeaf": false, "rowSpan": 3, "colSpan": 1 },
        { "id": "eb1d5347-0a91-4d9c-99d5-a65a98f84147", "text": "A", "children": null, "level": 2, "leafCount": 2, "isLeaf": false, "rowSpan": 2, "colSpan": 1 },
        { "id": "7b5a2809-70c8-4460-987b-b2df5649c672", "text": "C", "level": 3, "leafCount": 1, "isLeaf": true, "children": null, "rowSpan": 1, "colSpan": 1 }
    ],
    [{ "id": "02a66fd8-4f6d-4bea-aca8-00e5e33c0d63", "text": "D", "level": 3, "leafCount": 1, "isLeaf": true, "children": null, "rowSpan": 1, "colSpan": 1 }],
    [{ "id": "78de42cb-7b25-495d-ac7e-02a180d1f28f", "text": "B", "level": 2, "leafCount": 1, "isLeaf": true, "children": null, "rowSpan": 1, "colSpan": 2 }]
]

数据转换

数据结构已经有了，下面就要考虑如何进行转换了，经过观察对比规律，得到下面的结论：

先序遍历构造数组

叶子节点：当前节点没有后代
先序遍历：根结点 —> 左子树 —> 右子树

对树进行先序遍历，遍历到了叶子节点，当前数组结束（即以该叶子节点为分界线，当前行结束）。

例子经过遍历后，得到嵌套数组：

[
    [tree,A,C],
    [D],
    [B]
]

数组有了，但是直接遍历渲染出来是不符合预期的，因为还差每个元素自己的行列合并数值

colSpan计算

通过观察研究，可发现：

每个td的列合并数值等于树的最终高度 – 当前节点的高度 + 1

这是最核心的规则之一

rowSpan计算

通过观察研究，可发现：

每个td的列合并数值等于当前节点子代的所有叶子节点个数（如果当前节点是叶子节点，也需要包含在内，即等于1）

这是最核心的规则之二

最终逻辑

经过上述分析，我们知道，树需要做遍历，并且需要知道树的高度、每一个节点的高度、每一个节点的叶子个数。
所以，在组件实现时，直接往树结构中注入下面属性

字段	解释
level	当前节点的层级,从根节点=1 开始
leafCount	当前节点拥有的叶子数量
isLeaf	是否叶子节点

属性注入逻辑：

...
/**
   * 递归建立以下内容：
   * 树的每个节点的深度（根节点深度为1）;
   * 每个节点下属所有的叶子（包括孙子和所有后代）个数;
   * 节点是否是leaf
   *
   * @param {*} arr
   * @param {*} parentLevel
   * 返回，有效内容为当前节点的所有后代叶子个数，所有后代节点中，最深的节点的深度
   */
  calcLevelLeaf(arr, parentLevel = 0) {
    let count = 0
    let deep = parentLevel + 1
    arr.forEach(item => {
      item.level = parentLevel + 1
      item.leafCount = 0
      if (this._hasChildren(item)) {
        const {count: c, deep: d} = this.calcLevelLeaf(
          item.children,
          item.level
        )
        item.leafCount += c
        item.isLeaf = false
        count += c
        deep = Math.max(deep, d)
      } else {
        item.isLeaf = true
        item.leafCount = 1
        count += 1
      }
    })
    return {
      count,
      deep
    }
  }
...

然后再执行先序遍历构造数组，此时就可以把colspan和rowspan都计算出来了，得到最终数组，然后给v-for遍历即可。

最终成品

尽管对上面的三个操作的算法写得不好，但是起码是实现了这套逻辑。

也把这套逻辑封装成了组件 merge-table
NPM: merge-table
gitee: merge-table

后记

算法优化

逻辑虽然实现，但是内部的算法还是比较糟糕的，希望后续能够优化减少遍历次数，欢迎issue。

属性抽离

对于注入属性，参考iview-tree的实现也是做了属性注入，个人觉得没有问题，只是后续应该可以换一个不容易冲突的属性名。

另外，tree遍历过程用到的比如 id,children的key应该抽离，因为组件是从以前的业务里搬出来的，所以暂时没考虑这一块，后续可以考虑进去。

树转合并单元格的实现