JavaScript processing of tree-structured data

Scenarios

There are some situations in front-end projects where you need to handle tree-structured data. (A year) ago I wrote an article about it, but now, I have a better solution.

Thinking

Previously I used Proxy to smooth out the differences in tree-structured data and then process it. Then I realized that this is totally redundant, and after using antd's Tree component, deepdash, indeed the first step is totally unnecessary.

The following code is implemented by TypeScript, it is better to know TypeScript type manipulation

In fact, the tree structure data can be abstracted to a very simple interface (interface)

interface Node {
  id: string
  children: Node[]
}

It's just that there are some more fields in the business, and the two fields have different names.

For example, system menu and system permissions

interface SysMenu {
  id: number // menu id
  name: string // the name to be displayed
  sub: SysMenu[] // sub-level menu
}

interface SysPermission {
  uid: string // System unique uuid
  label: string // The name of the menu to be displayed
  children: SysPermission[] // sub permissions
}

As you can see, they both have id and children fields, just with different names. Then, according to the encapsulation principle of encapsulating the parts that remain the same and leaving the parts that change to external input, these two fields are then specified externally.

Operations

So, what operations are available in the tree structure?

• reduce merge
• each traverses
• map mapping
• filter filtering
• treeToList tree to list
• listToTree list to tree

However, the only thing I'm currently using is each/map/filter/treeToList, so I'll implement the following first.

Define the mandatory parameter types required for a generic tree structure

If the tree structure must contain id/children, then this can be used to define generic parameters for tree structure operations.

export interface TreeOption<T extends object> {
  /**
   * A uniquely identified field
   */
  id: keyof T
  /**
   * Field for child nodes
   */
  children: keyof T
}

The above is an interface that must declare what the field name of id/children is, to make it easier for the internal implementation to read tree node information.

Thanks to TypeScript, without it it would be impossible to define types and check for subtle errors in the code. Java, for example, has difficulty defining reflection-related types, and usually has to use String.

treeMap

The following implementation of treeMap is actually a recursive function.

import { TreeOption } from '. /treeOption'

/**
 * Tree structure mapping
 * Using depth-first algorithm
 * @param nodeList
 * @param fn
 * @param options
 */
export function treeMap<
  T extends object,
  C extends TreeOption<T>,
  F extends (
    t: Omit<T, C['children']> & Record<C['children'], ReturnType<F>[]>,
    path: T[C['id']][],
  ) => object
>(nodeList: T[], fn: F, options: C): ReturnType<F>[] {
  function inner(nodeList: T[], parentPath: T[C['id']][]): any {
    return nodeList.map((node) => {
      const path = [. .parentPath, node[options.id]]
      const children = (node[options.children] as any) as T[]
      if (!children) {
        return fn(node as any, path)
      }
      return fn(
        {
          ... . node,
          [options.children]: inner(children, path),
        },
        path,
      )
    })
  }

  return inner(nodeList, [])
}

But those who are careful may have noticed that two strange operations are done here

1. all child nodes are processed first, and then the processed child nodes are passed into the map function instead of the other way around. -- this is actually to be compatible with the JSX front-end framework react.
2. compute the path of the node and throw it into the map function. -- This is to make it easy to know all the parents of the current node and the hierarchy, so that you can get this key information when you need it (e.g. to convert to a list).

treeFilter

Well, the following functions will be based on the treeMap implementation (#grin)

import { TreeOption } from '. /treeOption'
import { treeMap } from '. /treeMap'

/**
 * Filter a list of tree nodes
 * @param nodeList
 * @param fn
 * @param options
 */
export function treeFilter<T extends object, C extends TreeOption<T>>(
  nodeList: T[],
  fn: (t: T, path: T[C['id']][]) => boolean,
  options: C,
): T[] {
  return treeMap(
    nodeList,
    (node: any, path) => {
      const children = (node[options.children] as any) as T[] | undefined
      // if it's the wrong node just blow it up
      if (!fn(node as T, path)) {
        return null
      }
      //return if it is a leaf node
      if (!children) {
        return node
      }
      //count all children nodes that are not null
      const sub = children.filter((node) => node ! == null)
      //If all children are null, blow them up
      if (sub.length === 0) {
        return null
      }
      return {
        ... . node,
        children: sub,
      }
    },
    options,
  ).filter((node) => node ! == null)
}

Flowchart of the above filter

! treeFilter flowchart.drawio

originalDrawio

treeEach

Again, based on treeMap, this is actually a bit lackluster.

import { TreeOption } from '. /treeOption'
import { treeMap } from '. /treeMap'

/**
 * Tree structure mapping
 * Use depth-first algorithm
 * @param nodeList
 * @param fn
 * @param options
 */
export function treeEach<T extends object, C extends TreeOption<T>>(
  nodeList: T[],
  fn: (t: T, path: T[C['id']][]) => void,
  options: C,
) {
  treeMap(
    nodeList,
    (node, path) => {
      fn(node as T, path)
      return node
    },
    options,
  )
}

treeToList

Same as above.

import { TreeOption } from '. /treeOption'
import { treeEach } from '. /treeEach'

/**
 * Flatten a list of tree nodes
 * @param nodeList
 * @param options
 */
export function treeToList<
  T extends object,
  C extends TreeOption<T> & { path: string },
  R extends T & { [K in C['path']]: NonNullable<T[C['id']]>[] }
>(nodeList: T[], options: C): R[] {
  const res: R[] = []
  treeEach(
    nodeList,
    (node, path) => {
      res.push({ . . node, [options.path]: path } as R)
    },
    options,
  )
  return res
}

FAQ

So, here are some questions that may exist in the mud, I'll answer them here, if you have other questions, you can comment directly below.

• Q: Why not use deepdash?
• A: Because it relies on lodash and the API provided is a bit complicated.
• Q: Why use the depth-first algorithm?
• A: Because of the need to be compatible with web frameworks such as react, where all JSX children need to be computed and passed to the parent node.
• Q: Why do you use recursion instead of loops?
• A: This is purely a personal preference. Loops provide better performance, but in most cases, performance is not important, so I use the more intuitive recursion.
• Q: Why use the TypeScript implementation?
• A: Because TypeScript's type system is more user-friendly and more maintainable for code users. -- but because TypeScript's type system is too complex, so it is not very friendly to newcomers, see TypeScript Type Programming

Finally, I have created a module @liuli-util/tree that already contains the above functionality.