Generate trees from lists (JavaScript/TypeScript)

In most cases, the data you get from the server for the tree display is itself flat, that is, a list. This is because a relational database stores data in rows, so it stores data for each node, which contains its relationship to the parent node (such as parentId).

To display such tabular data as a tree, the front end needs to convert the tabular data into tree-structured data. The tree structure of this is that each node data contains its set of children (usually the children attribute). So the data structure of the tree node mainly needs to contain the following information (TypeScript data structure declaration) :

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

The TypeScript generic syntax is used to describe the tree node structure. It is not difficult to understand from the natural semantics:

The tree nodeid(includingparentId) isstringornumberType, or, less commonly, a hybrid type.
The tree node contains oneparentIdBecause of thisparentIdNot optional (useless?So the root node usually uses a special value, or an ID value that should not exist, such as0(if the database increment field, generally from1Start)
The tree node contains an optional set of child nodeschildrenEach element of the current element is of the same type
defineTKeyThe purpose of this type parameter is to restrict the type of the child node to be the same as that of the parent nodeid 是 stringType of a child nodeidBut intostringThis is the case (mixed typeidIs not included)

Popular science finished the data structure of the tree node, and then the conversion process. In general, there are three phases of conversion that might occur:

Deal with the back end before you send it out
The front end is then converted, and the converted array is then used to render the page
The front-end uses UI components with their own conversion capabilities that developers don’t need to worry about (such as zTree)

Here’s an example of how to do this with JS/TS. The language is not important. What is important is how to think and what method to use to transform. The reason for using both JS and TS here is that having a similar TS can clearly describe the data structure, while the JS code may look less stressful to most people.

I. Prepare sample data (randomly generated)

The tree data is represented as a list, each of which must clearly describe the three elements of the node:

Self-identification (ID), usually usedid,key,nameAttribute name that uniquely identifies a node
The relationship with the parent node by usingparentId,upstreamIdThe name of the node clearly indicates its parent node
The data carried by the node itself, such as the text displayed,title,labelEtc., and some other data.

To prepare the sample data quickly, we use one of the simplest data structures with well-defined attributes. Note that this structure is a flat structure that matches the data table and does not contain the children subset.

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

Then write a piece of code to randomly generate the data. Before that, we agreed that the ID of a valid node starts at 1. If parentId === 0 for a node, the node has no parent. Ideas:

The loop produces a set of nodes, each of which has the ID number + 1 (the number starts at 0).

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

Next, parentId is a previously generated node whose ID ranges in the interval [0, I] (closed interval, if you don’t understand, review your high school math). We randomly select one from this range as its parent node. Here we need to generate a random integer, so let’s say randomInt(Max)
```
// JavaScript
function randomInt(max) {
    return Math.floor(Math.random());
}
```

Note that the value range of 'Math.random()' is a floating point number in '[0, 1)' (left closed and right open interval), so the result set of 'randomInt()' is in the range of '[0, Max)'. In order to ensure the integers in '[0, I]' that are needed, That is, integers between '[0, I + 1)'. If you need to call 'I + 1' : 'randomInt(I + 1)'. Continue to improve the 'parentId' part of 'node.push(...)' above:  ```typescript { id: i + 1, parentId: randomInt(i + 1) } ```

The next step is to generate a random label. The character set can be converted to an array using the Spread operator, since the string itself can be iterated over. The code is as follows:
```
// JavaScript
const CHARS = ((chars, nums) => {
    return [...`${chars}${chars.toLowerCase()}${nums}`];
})("ABCDEFGHIJKLMNOPQRSTUVWXYZ", "0123456789");
```

In fact, we can simply give a string containing all the characters, but we don't want to write 'a~z' again, so we use a IIFE to repeat 'a~z'. One other thing to note is that the string itself can be fetched using the '[]' index operator, so it is possible not to pre-convert to a character array. The next step is to randomly generate the string. Randomly select n characters according to their length and then concatenate them together:  ```js // JavaScript function randomString(length) { return Array.from( Array(length), () => CHARS[randomInt(CHARS.length)] ).join(""); } ``` `randomString() 'generates a randomString of specified length. Here 'Array(length)' produces an Array of 'length' without any elements. You can use 'array.from ()' to change it to an Array with elements (default is' undefined '). During the conversion, the second argument to 'array.from ()' is a mapping function, just like the argument to 'array.prototype.map ()'. Now, we can go ahead and refine 'node.push(...)'. ' ' 'js {id: I + 1, parentId: randomInt(I + 1), label: RandomString (5 + RandomInt (10)) // RandomString (5 + RandomInt (10)

So far, we have the key code to prepare the sample data. Let’s have a complete one

// 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), parentId: randomInt(I + 1), RandomString (5 + randomInt(10)) // Randomly generate a string of length [5, 15]});

The full code is written in TypeScript. If you need JavaScript, you can spell it out according to the key code for each step above. Or take the TypeScript code
TypeScript PlaygroundTo convert.

Finally, we can directly call randomTreeNodes() to generate the tree structure we need:

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

The resulting treeNodes will be used as the data source for the spanning tree demonstration code below. Here are the results of one of these runs:

[
  { 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' }
]

If it is expressed graphically, it is:

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")

MermaidIt’s a good thing, Sifl support oh!

Generate a tree from the presentation data

“Experimenting” is the practice of picking up the keyboard and typing code before the idea is fully formed. But even for an experiment, you should have thought through it first.

It is now known that each node already includes key data: the ID used to identify the node, and parentId used to identify its parent relationship. Then, when processing a node, it only needs to find the parent node according to its parentId and add the current node into the children[] array of the parent node to generate data with tree structure. There are a few related issues to consider here:

Since there is only one nodeparentId, so it will only end up being added to a nodechildren[]It is not possible to appear on more than one nodechildren[];
With noparentIdorparentId 为 0Which we consider to be the root node. But it may not be the only root node, so we need an extra oneroots[]Array to hold all the root nodes.
Thinking: How should the basisparentIdTo find the corresponding node data, right?

The first two problems are easy to understand, and the third problem requires thinking about algorithms. Since there is a parent node in the node list, you can find parentId directly in the node list

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

When traversing a processing node, it can be determined that the parent node of the current node must precede it, based on the logic of the data generated above. If you know that the parent and child nodes are close to each other, you can optimize for a reverse lookup. This procedure can be defined as a function findParent() :

// const findParent = (id, const findParent = ()); // const findParent = (id, const findParent = ()); index) => { for (let i = index - 1; i >= 0; i--) { if (treeNodes[i].id === id) { return treeNodes[i]; }}};

In fact, in most cases it is not clear whether the parent node is close to the origin or the ion node, so there is no need to write a reverse search, using
Array.prototype.find()It’ll be ok.

Once the parentNode is found, pay special attention to whether the current node node exists before adding it to the parentNode child set. Logical Nullish Assignment (?? =) operator to simplify the code, in one sentence:

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

There is also a performance-related issue here. In the case of large amount of data, whether in order or in reverse order, many nodes may be swept, so using Map can greatly improve the efficiency of searching. If the nodes are ordered (that is, the parent node must be in front of it), the Map can be generated at the same time as the traversal. A relatively complete code example:

// 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; }

The above JavaScript code, if replaced with TypeScript code, would still have a problem with the type declaration: The Parent. Children at the end will be marked red Parent and will report “Object is possibly ‘undefined’.” .

This problem illustrates the possibility that when looking for a parent node in a Map by parentId, it may not be found.

In this example, the code that generates the treeNodes is guaranteed to be found, so we can ignore the compiler’s concerns and simply replace it with Parent! .children just hide this risk warning. However, actual data coming in from the background does not guarantee that nodesMap.get(node.parentid) will not return undefined. There are at least two ways to create this problem:

Node order is not in parent-child order (most occurs after moving a holiday point). In this case, since the parent node is after the child node, it has to look in the Map before it is added to the Map. Of course, it cannot be found. To solve this problem, just commit to traverse all the nodes to produce a complete Map.
Failed to send back all nodes due to a backend error or business need. In addition to reporting errors, the front end has two fault-tolerant handling methods:
1. Discards nodes that do not have a parent. This kind of fault tolerance method is not difficult to deal with, so I won’t say much.
2. Treat the node that has no parent as the root node — this is the fault-tolerant approach most of the time, since the data is here

The next step is to add fault-tolerant Maketree.

Generate the full TypeScript code from the list tree

interface TreeNode { id: number; parentId: number; label: string; children? : TreeNode[]} function MakeTree (TreeNode: TreeNode[]): TreeNode[] {// Pregenerate the node lookup table. // If you specify the order of the nodes, you can save this traversal. Const nodesMap = new Map<number, treeNode >(treeNode.map (node => [node.id, node])); Const VirtualRoot = {} as Partial<TreeNode>; treeNodes.forEach((node, i) => { const parent = nodesMap.get(node.parentId) ?? virtualRoot; (parent.children ?? = []).push(node); }); return virtualRoot.children ?? []; }

Yes, this code is not very long. However,

Has the hierarchical analysis and processing process been received?
Did TypeScript type checking impress you?

Come to my class: TypeScript from Beginners to Practice [2021 Edition] – Sympher Programming, You Can

Deep understanding of TypeScript language features to write high quality code
Mastering the application of TypeScript VUE front-end and KOA back-end technology
Master the development pattern, design pattern and release method of front and back end separation
Integrate type system into programming thinking, improve understanding ability and design ability

Generate trees from lists (JavaScript/TypeScript)

I. Prepare sample data (randomly generated)

Generate a tree from the presentation data

Generate the full TypeScript code from the list tree

Related Posts

How to optimize the concurrency capacity of a single server?

Almost surprised by SystemJS jaw, decrypt module load black magic

I almost got fired for using a micro front end on a company project