关于树形结构:从列表生成树-JavaScriptTypeScript

39次阅读

共计 7377 个字符，预计需要花费 19 分钟才能阅读完成。

少数状况下，从服务端拿到用于树形显示的数据，自身是立体的，也就是列表。这是因为关系型数据库是以“行”为单位保留数据，所以它保留了每一个节点的数据，而这个数据中蕴含了它与父节点之间的分割（比方 parentId）。

前端要以树形显示这样的列表数据，须要把列表数据转换成树形构造数据。这个的树形构造是指：每个节点数据中都含有其子节点集（通常是 children 属性）。所以树形结节的数据结构次要须要蕴含如下信息（TypeScript 数据结构申明）：

interface TreeNodeBase<TKey extends string | number = number> {
    id: TKey;
    parentId: TKey
    children?: TreeNodeBase<TKey>[]}

这里应用了 TypeScript 的泛型语法来形容树节点构造。从天然语义不难明确：

  • 树节点的 id（包含 parentId）是 string 或者 number 类型，较为少见的状况下也可能是混合类型。
  • 树节点蕴含一个 parentId，因为这个 parentId 不是可选的（没用 ? 号申明），所以根节点通常会用一个非凡值，或者不应该存在的 ID 值，比方 0（如果是数据库自增字段，个别会从 1 开始）
  • 树节点蕴含一个可选的子节点集 children，其每个元素了以后元素是雷同的类型
  • 定义 TKey 这个类型参数的作用就是为了束缚子节点类型必须和父节点统一，防止父节点的 id 是 string 类型，子节点的 id 却搞成了 string 这种状况（混合类型 id 的状况不含在内）

科普完树节点的数据结构，再来说转换过程。一般来说可能会在三个阶段进行转换：

  • 后端送进去之前先解决好
  • 前端拿到之后本人转换，再用转换后数组去渲染页面
  • 前端应用的 UI 组件自带转换性能，不须要开发者去操心（比方 zTree）

这里就以 JS/TS 为例来说说如何进行转换。语言不重要，重要的是该如何来思考，以及应用什么办法进行转换。这里同时应用 JS 和 TS 的起因在于：带相似的 TS 能够清晰地形容数据结构，而 JS 代码可能少数人看起来更没有压力。

一、筹备示例数据（随机产生）

以列表示意的树形数据，其每一条（行）肯定须要分明的形容这个节点的三个因素：

  1. 本身标识（ID），通常用 id、key、name 等属性名，它能惟一标识一个节点
  2. 与父节点的关系，通过应用 parentId、upstreamId 等名称，分明的指明其父节点
  3. 节点本人携带的数据，比方显示的文本，title、label 等，和一些其余数据。

为了疾速筹备示例数据，咱们应用一个最简略，属性意义也十分明确的数据结构。留神，这个构造是与数据表相匹配的立体构造，不含 children 子集。

// TypeScript
interface TreeNode {
    id: number;
    parentId: number;
    label: string;
}

而后写一段代码来随机生成数据。在这之前，咱们约定，无效节点的 id 从 1 开始。如果某个节点的 parentId === 0，则示意该节点没有父节点。思路：

  • 循环产生一组节点，每个节点的 id 就是 序号 + 1（序号是从 0 开始的）

    // JavaScript
const nodes = [];
count nodesCount = 20;
for (let i = 0; i < nodesCount; i++) {
    nodes.push({id: i + 1,})
}

  • 接下来，parentId 是之前曾经产生的节点，其 ID 范畴在区间 [0, i]（关闭区间，如果不懂，请温习一下高中数学）。咱们随机从这个范畴内一个作为其父节点。这里咱们须要产生一个随机 整数，所以先写一个 randomInt(max)

    // JavaScript
function randomInt(max) {return Math.floor(Math.random());
}
留神 `Math.random()` 的取值范畴是 `[0, 1)`（左闭右开区间）内的浮点数，所以 `randomInt()` 的后果集在 `[0, max)` 范畴内。为了保障须要的 `[0, i]` 内的整数，即 `[0, i + 1)` 间的整数，须要调用时给参数为 `i + 1`：`randomInt(i + 1)`。持续欠缺下面 `node.push(...)` 中的 `parentId` 局部：```typescript
{
    id: i + 1,
    parentId: randomInt(i + 1)
}
```

  • 下一步，是产生随机的 label。也不定太简单的规矩，就产生一个由大小写字母及数字组成的，长度在 [5, 15) 范畴的随机字符串。因为字符串自身是能够迭代（遍历）的，所以能够用扩大 (Spread) 运算符来转换成数组，从而失去字符集，代码如下：

    // JavaScript
const CHARS = ((chars, nums) => {return [...`${chars}${chars.toLowerCase()}${nums}`];
})("ABCDEFGHIJKLMNOPQRSTUVWXYZ", "0123456789");
其实间接给一个蕴含所有字符的字符串就能够，然而不想把 `a~z` 再写一遍，所以用了一个 IIFE 来复用 `A~Z`。另外有一点须要留神：字符串自身能够应用 `[]` 索引运算符来取字符，所以不事后转换成字符数组也是能够的。接下来是随机产生字符串。依据长度随机抉择 n 个字符，再连接起来即可：```js
// JavaScript
function randomString(length) {
    return Array.from(Array(length),
        () => CHARS[randomInt(CHARS.length)]
    ).join("");
}
```

`randomString()` 能够产生一个指定长度的随机字符串。这里 `Array(length)` 会产生一个长度为 `length` 但不含任何元素的数组，能够用 `Array.from()` 把它变成含有元素（默认是 `undefined`）的数组。在转换的过程中，`Array.from()` 的第二个参数是一个映射函数，跟 `Array.prototype.map()` 的参数一样。当初，咱们能够持续欠缺 `node.push(...)` 中的 `label` 局部：```js
{
    id: i + 1,
    parentId: randomInt(i + 1),
    label: randomString(5 + randomInt(10))    // 长度在 [5, 15) 区间的随机字符串
}
```

到目前为上，筹备示例数据的要害代码都有了，来个残缺的

// TypeScript

interface TreeNode {
    id: number;
    parentId: number;
    label: string;
}

const CHARS = ((chars, nums) => {return [...`${chars}${chars.toLowerCase()}${nums}`];
})("ABCDEFGHIJKLMNOPQRSTUVWXYZ", "0123456789");

function randomInt(max: number): number {return Math.floor(Math.random() * max);
}

function randomString(length: number = 10): string {
    return Array.from(Array(length),
        () => CHARS[randomInt(CHARS.length)]
    ).join("");
}

function randomTreeNodes(count: number = 20): TreeNode[] {return [...Array(count).keys()]
        .map(i => ({
            id: i + 1,
            parentId: randomInt(i + 1),     // 从曾经产生的节点中去随机找一个
            label: randomString(5 + randomInt(10))  // 随机产生长度为 [5, 15) 的字符串
        }));
}

残缺代码是 TypeScript 写的。如果须要 JavaScript，能够依据下面每一步的要害代码拼出来。或者拿 TypeScript 代码到 TypeScript Playground 中去转换一下。

最初能够间接调用 randomTreeNodes() 来生成咱们须要的树形构造：

// JavaScript | TypeScript
const treeNodes = randomTreeNodes();

失去的 treeNodes 会用于上面生成树演示代码的数据源。上面是其中一次运行的后果：

[{ id: 1, parentId: 0, label: '8WUg35y'},
  {id: 2, parentId: 1, label: 'Pms1S5Mx'},
  {id: 3, parentId: 1, label: 'RUTKSF'},
  {id: 4, parentId: 1, label: 'IYkxXlhmU12x'},
  {id: 5, parentId: 4, label: 'p2Luabg9mK2'},
  {id: 6, parentId: 0, label: 'P6mtcgfCD'},
  {id: 7, parentId: 1, label: 'yluJgpnqKthR'},
  {id: 8, parentId: 6, label: 'm6o5UsytQ0'},
  {id: 9, parentId: 2, label: 'glcR5yGx'},
  {id: 10, parentId: 0, label: 'lhDGTNeeSxLNJ'},
  {id: 11, parentId: 1, label: 'r7ClxBCQS6'},
  {id: 12, parentId: 7, label: '5W6vy0EuvOjN'},
  {id: 13, parentId: 5, label: 'LbpWq'},
  {id: 14, parentId: 6, label: 'ysYwG8EFLAu1a'},
  {id: 15, parentId: 8, label: 'R2PmAh1'},
  {id: 16, parentId: 10, label: 'RKuQs4ki65wo'},
  {id: 17, parentId: 10, label: 'YN88ixWO1PY7f4'},
  {id: 18, parentId: 13, label: '03X6e4UT'},
  {id: 19, parentId: 7, label: 'LTJTeF'},
  {id: 20, parentId: 19, label: '3rqUqE3MLShh'}
]

如果用图形来示意就是：

flowchart LR
%%{init: { "theme": "forest"} }%%

S(("Virtual\nRoot")) --> N1
S --> N6
S --> N10

N1("1 | 8WUg35y") --> N2("2 | Pms1S5Mx")
N1 --> N3("3 | RUTKSF")
N1 --> N4("4 | IYkxXlhmU12x")
N4 --> N5("5 | p2Luabg9mK2")
N6("6 | P6mtcgfCD")
N1 --> N7("7 | yluJgpnqKthR")
N6 --> N8("8 | m6o5UsytQ0")
N2 --> N9("9 | glcR5yGx")
N10("10 | lhDGTNeeSxLNJ")
N1 --> N11("11 | r7ClxBCQS6")
N7 --> N12("12 | 5W6vy0EuvOjN")
N5 --> N13("13 | LbpWq")
N6 --> N14("14 | ysYwG8EFLAu1a")
N8 --> N15("15 | R2PmAh1")
N10 --> N16("16 | RKuQs4ki65wo")
N10 --> N17("17 | YN88ixWO1PY7f4")
N13 --> N18("18 | 03X6e4UT")
N7 --> N19("19 | LTJTeF")
N19 --> N20("20 | 3rqUqE3MLShh")

Mermaid 是个好货色，思否反对哦！

二、从演示数据生成树

在思路没有齐全造成之前，拿起键盘就开始敲代码 —— 这种行为个别算作“试验”。不过即便是试验，也应该先捋捋思路。

目前已知，每个节点上曾经包含了要害数据：用于辨认节点的 id，用于辨认其父级关系的 parentId。那么，只须要在解决某个节点时，依据其 parentId 找到父节点，并在父节点的 children[] 数组中退出以后节点即可生成树形构造的数据。这里还要思考几个相干问题：

  1. 因为一个节点只有一个 parentId，所以它最终只会增加到某一个节点的 children[] 中，不可能呈现在多个节点的 children[] 中；
  2. 对于没有 parentId 或者 parentId 为 0 的节点，咱们认为是根节点。但它有可能不是惟一根节点，所以咱们须要一个额定的 roots[] 数组来保留所有根节点。
  3. 思考：该怎么依据 parentId 来找到对应的节点数据？

前两个问题好了解，第 3 个问题须要思考算法。因为节点列表中存在父节点，所以能够间接拿 parentId 在节点列表中去查找

// JavaScript
const parentNode = treeNodes.find(node => node.id === parentId);

在遍历解决节点的过程中，依据下面生成数据的逻辑，能够判定以后节点的父节点肯定在它之前。如果晓得 父节点和子节点之间关系较近，能够优化为逆序查找。这个过程能够定义成一个函数 findParent()：

// JavaScript
/**
 * @param id 要查找的父节点 id
 * @param index 以后节点在 treeNodes 中的序号
 */
const findParent = (id, index) => {for (let i = index - 1; i >= 0; i--) {if (treeNodes[i].id === id) {return treeNodes[i];
        }
    }    
};

实际上，少数状况下并不分明要查找到父节点到底是离起始地位近还是离子节点近，所以齐全没必要去写个逆序查找，用 Array.prototype.find() 就好了。

找到父节点之后，在把以后节点 node 退出到 parentNode 子节点集之前，特地要留神其子节点集是否存在。能够应用 Logical nullish assignment (??=) 运算符来简化代码，一句搞定：

(parentNode.children ??= []).push(node);

这里还有一个性能相干的问题。在数据量较大的状况下，不论程序还是逆序查找都可能扫过十分多的节点，应用 Map 能够大大提高查找效率。在节点有序（即父节点肯定在后面）的状况下，Map 能够在遍历的同时生成。绝对残缺的代码示例：

// JavaScript

function makeTree(treeNodes) {const nodesMap = new Map();
    const roots = [];
    treeNodes.forEach((node, i) => {nodesMap.set(node.id, node);

        if (!node.parentId) {roots.push(node);
            return;
        }

        const parent = nodesMap.get(node.parentId);
        (parent.children ??= []).push(node);
    });

    return roots;
}

下面这段 JavaScript 代码，如果改成 TypeScript 代码，在补充了类型申明的状况下，依然会有一个问题：快结尾处的 parent.children 会标红 parent 并报告“Object is possibly ‘undefined’.”。

这个问题阐明依据 parentId 在 Map 中查找父节点时，存在找不到的可能性。

在这个示例中，于咱们生成 treeNodes 的代码能够保障肯定找失去，能够疏忽编译器的担心，间接改为 parent!.children 暗藏掉这个危险提醒即可。然而，实在从后盾过去的数据并不能保障 nodesMap.get(node.parentId) 不会返回 undefined。至多存在两种造成这个问题的状况：

  1. 节点程序并不是按先父后子的程序（少数是产生在挪动过节点之后）。这种状况下，因为父节点在子节点之后，还没退出 Map 就要从外面查找，当然是找不到的。要解决这个问题，只须要提交遍历所有节点生成残缺的 Map 就好。

  2. 因为后端失误或业务须要，未能把所有节点都送回来。那前端除了报错之外，还有两种容错解决形式：

    1. 抛弃没有找到父节点的节点。这种容错形式解决起来不难，就不多说了。
    2. 把没人父节点的节点当作根节点 —— 既然数据都来了，少数状况下会采纳这种容错形式

接下来就是退出容错解决的 makeTree。

三、从列表生成树的残缺 TypeScript 代码

interface TreeNode {
    id: number;
    parentId: number;
    label: string;
    children?: TreeNode[]}

function makeTree(treeNodes: TreeNode[]): TreeNode[] {
    // 提前生成节点查找表。// 如果明确节点是程序能够保障先父后子，能够省去这次遍历，在前面边遍历过程中填充查找表
    const nodesMap = new Map<number, TreeNode>(treeNodes.map(node => [node.id, node])
    );

    // 引入虚构根节点来对立实现 parent 始终无效，防止空判断
    const virtualRoot = { } as Partial<TreeNode>;
    treeNodes.forEach((node, i) => {const parent = nodesMap.get(node.parentId) ?? virtualRoot;
        (parent.children ??= []).push(node);
    });

    return virtualRoot.children ?? [];}

是的，这段代码并不长。然而，

  • 层层递进的剖析和处理过程有没有 Get 到？
  • TypeScript 的类型查看有没有感动到你？

来我的课堂：TypeScript 从入门到实际【2021 版】– 思否编程，你能够

  • 深刻了解 TypeScript 语言个性，编写高质量代码
  • 把握基于 TypeScript 的 Vue 前端、Koa 后端技术使用
  • 把握前后端拆散的开发模式、设计模式和公布办法
  • 将类型零碎融入编程思维，晋升理解能力和设计能力

正文完
树形结构
发表至： 树形结构
2021-07-13
 0
关于树形结构:差分树上差分
关于树形结构:从列表生成树-JavaScriptTypeScript
关于树形结构:并查集
关于树形结构:树形结构先序遍历树实践MPTT