I. Background and demand of the problem

1. The demand

  • Realize multi-layer keyword fuzzy search;
  • Search the whole tree node, including non-child node and child node, automatically expand the parent node when hit;
  • If a non-child node matches the match, all the child nodes are retained.
  • Keyword matching is highlighted.

[Tree display before search]

[Search keyword “test “]

2. Problems exist

  • The data returned by the back end is flat data, and the display needs to be transformed into a tree structure.
  • There is a large amount of data, 4000+ data in total. For performance considerations, it is necessary to reduce the number of traversal times when implementing the search function.

Two, the realization principle

1. Realization of tree structure of flat data transformation

The principle of

  • The scattered flattened nodes are constructed as object data indexed by ID.

  • Traverse the flattened nodes one by one to find their parent nodes and insert them.

    At the same time to determine whether the root node, if the root node directly extracted.

Code implementation

You need to iterate through the data twice: construct the object indexed by ID and find the parent data.

(parent === ‘0’)

// formateTree = (category) => {const treeMap = {} // const tree = [] ForEach ((o) => {treeMap[O.id] = object.assign (o, {children: []}}) category. ForEach ((o) => {treeMap[O.id] = object.assign (o, {children: []}}) category.if(o.parent ! = ='0') {
      treeMap[o.parent].children.push(treeMap[o.id])
    } else if (o.parent === '0') {
      tree.push(treeMap[o.id])
    }
  })
  return tree
}
Copy the code

2. Realize multi-layer keyword fuzzy search

To prepare

  • Tree structure
  • An object indexed by ID
  • FilterNode [] filterNode[]
  • The array treeData that holds the final result []

The principle of

1. [recursion] Traverse the tree structure according to the keyword to find the first hit node findTargetNode(), insert filterNode[], and insert the parent node into expandedList[].

Hit mark: ⭐

2. [recursion] Expand the path findExpandedNode() that contains key byte points under non-child nodes, and insert the matching node parent into expandedLish[].

⚠️ Note that if the keyword is not matched at more than two levels in the middle, the insertNodeParent() cannot be expanded. Finally, the insertNodeParent() must be replenished upward according to the nodes in the expandedList[].

3. [recursion] Find the parent node of the hit node and splicing it into a tree findParend().

4. ExpandedList [] to heavy.

[recursion] The insertNodeParent() object is used to make up the parent of the expanded node based on the nodes in filterNode[].

5. The principle is the same as 3

6. ExpandedList [] to heavy.

Code implementation

  • findTargetNode()

    When the first hit node is the last node: Insert (push the node into filterNode[]), expand (and push its parent ID into expandedList[]).

    When the first matching node is not a child node: Insert, and need to traverse the path to continue to find the remaining matching node findExpandedNode().

const findTargetNode = (val, tree, filterNode, expandedList) => {
  tree.forEach((item) => {
    if (item.title.indexOf(val) > -1) {
      if(! item.children.length) { filterNode.push(item); expandedList.push(item.parent); }else{ filterNode.push(item); expandedList.push(item.parent); findExpandedNode(val, tree, expandedList); }}else{ findTargetNode(val, item.children, filterNode, expandedList); }})}Copy the code


  • findExpandedNode()

    The last section contains the keywords: expand; None: No processing is required.

    Non-terminal points contain keywords: expand, continue recursion; Not included: Continue recursion.

const findExpandedNode = (val, tree, expandedList) => {
  tree.forEach((item) => {
    if(! item.children.length && item.title.indexOf(val) > -1) { expandedList.push(item.parent); }else if (item.children.length && item.title.indexOf(val) > -1) { 
      expandedList.push(item.parent);
      findExpandedNode(val, item.children, expandedList)
    } else if (item.children.length && item.title.indexOf(val) === -1) {
      findExpandedNode(val, item.children, expandedList)
    }
  })
}
Copy the code


  • findParend()

    The parent node is not the root node

    Whether the parent node in the object tree already contains this node. Not included: The parent node is inserted. (Avoid duplication)Copy the code

    The parent node is the root node

    The current result indicates whether the root node is included. If yes, no action is required. Not included: Inserted into the result.Copy the code
const findParend = (item, treeMap, treeData, expandedList) => {
  if(item.parent ! = ='0') {
    const ids = treeMap[item.parent].children.map(o => o.id);
    if (!ids.includes(item.id)) {
      treeMap[item.parent].children.push(item);
      expandedList.push(item.parent);
      findParend(treeMap[item.parent], treeMap, treeData, expandedList);
    }
  } else {
    const ids = treeData.map(o => o.id);
    if(! ids.includes(item.id)) { treeData.push(item); expandedList.push(item.id) } } }Copy the code


  • ExpandedList [] to heavy

    Es6 SET data structure

expandedList = [...new Set(expandedList)]
Copy the code


  • insertNodeParent()

    If the current node is not the root node, insert the parent ID of the node

    Returns if the current node is the root node

const insertNodeParent = (key, expandedList, treeMap) => {
  if (key === '0') {
    return 
  }
  const { parent } = treeMap[key]
  expandedList.push(parent)
  if(parent ! = ='0') {
    insertNodeParent(parent, expandedList, treeMap)
  }
}
Copy the code