Recently, while writing a project, I came across the need to extend TreeSelect because the existing tree components did not meet the current requirements. The function of the extension is mainly to filter the tree structure by entering the search keyword. In the process of the extension, we encountered the mutual conversion of data structure and the filtering of the tree structure. Here we share it with you.

1. Data structure

A typical tree structure would look like this:

const treeData = [
  {
    id:"p1".title: 'in guangdong'.children: [{
      id:"p1-1".title: 'guangzhou',}}, {id:"p2".title:"Sichuan".children: [{id:"p2-1".title:"Chengdu".children: [{
        id:"p2-1-1".title:"High-tech Zone",}}, {id:"p2-2".title:Deyang ""
    },
    {
      id:"p2-3".title:"City"}}]]Copy the code

But sometimes the back end returns a tiled structure instead of the above:

const listData = [
  {
    id:"p1".title: 'in guangdong'}, {id:"p1-1".pid: 'p1'.title: 'guangzhou'}, {id:"p2".title:"Sichuan"}, {id:"p2-1".pid: 'p2'.title:"Chengdu"}, {id:"p2-2".pid: 'p2'.title:Deyang ""
  },
  {
    id:"p2-3".pid: 'p2'.title:"City"
  },
  {
    id:"p2-1-1".pid: 'p2-1'.title:"High-tech Zone",}]Copy the code

At this time, we need to generate a tree structure according to the ID and PID traversal data. Of course, sometimes we need to convert the tree structure into a flat array.

2. List to tree

2.1, the recursion

Use recursion to convert list to tree

function list2tree(list) {
  const tree = []
  for(const node of list) {
    // If there is no PID, it can be considered as the root node
    if(! node.pid) {letp = { ... node } p.children = getChildren(p.id, list) tree.push(p) } }function getChildren(id, list) {
    const children = []
    for(const node of list) {
      if(node.pid === id) {
        children.push(node)
      }
    }
    
    for(const node of children) {
       const children = getChildren(node.id, list)
       if(children.length) {
         node.children = children
       }
    }
    
    return children
  }
  
  return tree
}
Copy the code

2.2. Two-layer circulation

First, each node is iterated as the parentNode (parentNode), and then the data is iterated again to determine whether the pid of the data is equal to the id of the parentNode.

function list2tree(list) {
  list.forEach(child= > {
    const pid = child.pid
    if(pid) {
      list.forEach(parent= > {
        if(parent.id === pid) {
          parent.children = parent.children || []
          parent.children.push(child)
        }
      })
    }
  })
  return list.filter(n= >! n.pid) }Copy the code

Tree to list

Tree structure into an array involves tree traversal, tree traversal is divided into depth traversal (front, middle and back order) and breadth traversal, below respectively use depth traversal and breadth traversal tree and convert to array.

3.1 Breadth traversal

Traverse the nodes along the width of the tree. Use queues to assist in breadth traversal.

function tree2list(tree) {
  const list = []
  const queue = [...tree]
  while(queue.length) {
    const node = queue.shift()
    const children = node.children
    if(children) { queue.push(... children) } list.push(node) }return list
}
Copy the code

3.2 depth traversal

It traverses the depth of the tree. A stack is used to assist in depth traversal.

function tree2list(tree) {
  const list = []
  const stack = [...tree]
  while(stack.length) {
    const node = stack.pop()
    const children = node.children
    if(children) { queue.push(... children) } list.push(node) }return list
}
Copy the code

4. Tree filtering

Filtering the tree by passing in keywords involves two main cases:

  1. Putting the data that meets the criteria in an empty array and then returning the array breaks the tree structure
  2. After filtering, the data remains in the original tree structure. If a node meets the filtering criteria, its parent node is also returned

So in the first case, you just return the array and you just iterate through the tree and return whatever satisfies the criteria.

The second case needs to retain the original tree structure:

function filterTree(tree, key) {
    const filterChildrenTree = (resTree, treeItem) = > {
      if (treeItem.title.includes(key)) {
        resTree.push(treeItem)
        return resTree
      }
      if (Array.isArray(treeItem.children)) {
        const children = treeItem.children.reduce(filterChildrenTree, []);
        
        constdata = { ... treeItem, children }if(children.length) { resTree.push({ ... data }) } }return resTree;
    };
    return tree.reduce(filterChildrenTree, []);
  }
Copy the code