Summary of common operations on front-end tree structure data

This paper mainly introduces some common operation functions of tree structure data, such as tree traversal, tree to list, list to tree, tree node search, tree node path search and so on.

Combined with the actual project, some changes are processed, such as the encapsulation of the shuttle box components, which is essentially the processing of data, the filtering of data and the change of state, etc., reflected on the page display.

The simulated data is as follows:

const provinceList = [
  {
    id: "1000".label: Hubei Province.children: [{id: "1001".pid: "1000".label: "Wuhan".children: [{id: "100101".pid: "1001".label: "Flood area" },
          { id: "100102".pid: "1001".label: "Wuchang District" },
          { id: "100103".pid: "1001".label: "Hanyang District"},],}, {id: "1020".pid: "1000".label: "Xianning" },
      { id: "1022".pid: "1000".label: "Xiaogan" },
      { id: "1034".pid: "1000".label: "Xiangyang" },
      { id: "1003".pid: "1000".label: "Yichang"},],}, {id: "1200".value: Jiangsu Province.label: Jiangsu Province.children: [{id: "1201".pid: "1200".label: "Nanjing" },
      { id: "1202".pid: "1200".label: "Suzhou" },
      { id: "1204".pid: "1200".label: "Yangzhou"},],},];Copy the code

Tree traversal

Depth-first traversal

/** * depth-first traversal *@params {Array} Tree Indicates the tree data@params {Array} Func operator function */
const dfsTransFn = (tree, func) = > {
  tree.forEach((node) = > {
    func(node);
    // If the subtree exists, call recursively
    if (node.children?.length) {
      dfsTransFn(node.children, func);
    }
  });
  return tree;
};

// Prints the node
dfsTransFn(tree, (node) = > {
  console.log(`${node.id}.${node.value}`);
});
Copy the code

Deep loop traversal

Similar to breadth-first, a queue is maintained. However, this function is added to the front of the queue, whereas breadth-first traversal is added to the back.

const dfsTreeFn = (tree, func) = > {
  let node,
    list = [...tree];
  // shift()- take the first one
  while ((node = list.shift())) {
    func(node);
    // If the subtree exists, call recursively
    // The child node is appended to the front of the queue 'unshift'
    node.children && list.unshift(...node.children);
  }
};
Copy the code

Breadth-first traversal

/** * width first traversal *@params {Array} Tree Indicates the tree data@params {Array} Func operator function */
const bfsTransFn = (tree, func) = > {
  let node,
    list = [...tree];
  // shift()- take the first; Pop ()- take the last one
  while ((node = list.shift())) {
    func(node);
    // If the subtree exists, call recursively
    node.children && list.push(...node.children);
  }
};

// Prints the node
bfsTransFn(tree, (node) = > {
  console.log(`${node.id}.${node.value}`);
});
Copy the code

Trees turn list

Depth-first recursive

const dfsTreeToListFn = (tree, result = []) = > {
  if(! tree? .length) {return [];
  }
  tree.forEach((node) = > {
    result.push(node);
    console.log(`${node.id}.${node.label}`); // Displays node information
    node.children && dfsTreeToListFn(node.children, result);
  });
  return result;
};
Copy the code

Breadth first recursion

const bfsTreeToListFn = (tree, result = []) = > {
  let node,
    list = [...tree];
  while ((node = list.shift())) {
    result.push(node);
    console.log(`${node.id}.${node.label}`); // Displays node informationnode.children && list.push(... node.children); }return result;
};
Copy the code

Cycle to achieve

export const treeToListFn = (tree) = > {
  let node,
    result = tree.map((node) = > ((node.level = 1), node));
  for (let i = 0; i < result.length; i++) {
    // There is no child node, skip the current loop and go to the next loop
    if(! result[i].children)continue;
    // There are child nodes, traverse the child nodes, add hierarchy information
    let list = result[i].children.map(
      (node) = > ((node.level = result[i].level + 1), node)
    );
    // Add the child node to the array
    result.splice(i + 1.0. list); }return result;
};
Copy the code

List to the tree

const listToTreeFn = (list) = > {
  // Create a mapping with id=>node
  let obj = list.reduce(
    // map- accumulator, node- current value
    (map, node) = > ((map[node.id] = node), (node.children = []), map),
    / / initial value{});return list.filter((node) = > {
    // Find the parent element processing:
    // 1. Iterate through the list: time is O(n), and the total time is O(n^2) in the loop.
    // 2. Object value: Time complexity is O(1), overall time complexity is O(n)
    obj[node.pid] && obj[node.pid].children.push(node);
    // The root node has no PID, which can be used as a filter condition
    return! node.pid; }); };Copy the code

Find nodes

Checks whether a node exists, true if it does, false otherwise

const treeFindFn = (tree, func) = > {
  for (let node of tree) {
    if (func(node)) return node;
    if (node.children) {
      let result = treeFindFn(node.children, func);
      if (result) returnresult; }}return false;
};

// Test the code
let findFlag1 = treeFindFn(provinceList, (node) = > node.id === "1020");
let findFlag2 = treeFindFn(provinceList, (node) = > node.id === "100125");
console.log(`1020 is The ${JSON.stringify(findFlag1)}, 100125 is ${findFlag2}`);

// Print the result:
1020 is {"id":"1020"."pid":"1000"."label":"Xianning"."key":"1020"."title":"Xianning"."level":2."children": []},100125 is null
Copy the code

Find node path

const treeFindPathFn = (tree, func, path = []) = > {
  if(! tree)return [];

  for (let node of tree) {
    path.push(node.id);
    if (func(node)) return path;
    if (node.children) {
      const findChild = treeFindPathFn(node.children, func, path);
      if (findChild.length) return findChild;
    }
    path.pop();
  }
  return [];
};

// Test the code
let findPathFlag = treeFindPathFn(
  provinceList,
  (node) = > node.id === "100102"
);
console.log(`100102 path is ${findPathFlag}`);

// Print the result
100102 path is 1000.1001.100102
Copy the code

Practical function application

The page display

<template>
  <div class="demo-block">
    <div class="demo-block-title">Shuttle box data processing function:</div>
    <div class="demo-block-content">
      <div class="demo-block-title">The original data:</div>
      <a-tree blockNode checkable defaultExpandAll :tree-data="provinceData" />
    </div>
    <div
      class="demo-block-content"
      style="margin-left: 40px; vertical-align: top;"
    >
      <div class="demo-block-title">Processed data: filterSourceTreeFn</div>
      <a-tree
        blockNode
        checkable
        defaultExpandAll
        :tree-data="optProvinceData"
      />
    </div>
  </div>
</template>

<script>
  import * as R from "ramda";
  import provinceList from "./mock.json";
  export default {
    data() {
      return {
        provinceData: [].optProvinceData: [],}; }};</script>

<style lang="scss"></style>
Copy the code

Data conversion (traversal)

Convert mock data to data required by the component, iterate over the data, and add title and key fields

const treeTransFn = (tree) = >
  dfsTransFn(tree, (o) = > {
    o["key"] = o.id;
    o["title"] = o.label;
  });

this.provinceData = treeTransFn(provinceList);
Copy the code

Select node Disable

const disabledTreeFn = (tree, targetKeys) = > {
  tree.forEach((o) = > {
    let flag = targetKeys.includes(o.id);
    o["key"] = o.id;
    o["title"] = flag ? `${o.label}(Configured) : o.label;
    o["disabled"] = flag;
    o.children && disabledTreeFn(o.children, targetKeys);
  });
  return tree;
};

this.provinceData = disabledTreeFn(provinceList, ["100101"."1022"."1200"]);
Copy the code

Select node filtering

Source data box data processing, filtering out the selected node, do not display

/** * Select node filter *@params {Array} Tree Indicates the tree data@params {Array} TargetKeys Select the set of data keys * if the current node and its descendants have no data */
const filterSourceTreeFn = (tree = [], targetKeys = [], result = []) = > {
  R.forEach((o) = > {
    // 1. Check whether the current node contains qualified data. No - filter
    if (targetKeys.indexOf(o.id) < 0) {
      // 2. Check whether there are child nodes: yes - continue; No - Return directly
      if(o.children? .length) {// 3. Recursive processing of child nodes
        o.children = filterSourceTreeFn(o.children, targetKeys);
        // 4. If a child node exists and the child node also has a child node that matches the condition, the system returns the following information
        if (o.children.length) result.push(o);
      } else {
        result.push(o);
      }
    }
  }, tree);
  return result;
};

this.optProvinceData = treeTransFn(
  filterSourceTreeFn(R.clone(provinceList), ["100101"."1022"."1200"]));Copy the code

Sometimes, data is returned normally when the parent satisfies the condition, but no child satisfies the condition. The above method does not meet the criteria, and is implemented as follows.

export const filterSourceTreeFn = (tree = [], targetKeys = []) = > {
  return R.map(
    (o) = > {
      // 2. There are child nodes, recursive processing
      if(o.children? .length) { o.children = filterSourceTreeFn(o.children, targetKeys) || []; }return o;
    },
    // 1. Filter unqualified data
    R.filter(
      (r) = > targetKeys.indexOf(r.id) < 0.// Avoid modifying the original data directly. This should be handled by r.lone ()
      R.clone(tree)
    )
  );
};
Copy the code

Reserve selected Nodes

Target data processing, showing only selected nodes, filtering out other data

// The filtering criteria are: the current node or its descendant node has data that meets the criteria
filterTargetTreeFn = (tree = [], targetKeys = []) = > {
  return R.filter((o) = > {
    // If the current node meets the criteria, the current node is returned
    if (R.indexOf(o.id, targetKeys) > -1) return true;
    // If not, see if the child is qualified
    if(o.children? .length) {// The child node is called recursively
      o.children = filterTargetTreeFn(o.children, targetKeys);
    }
    // The existence of descendant nodes is returned
    return o.children && o.children.length;
  }, tree);
};

this.optProvinceData = treeTransFn(
  filterTargetTreeFn(R.clone(provinceList), ["100101"."1022"."1200"]));Copy the code

Keyword filtering

export const filterKeywordTreeFn = (tree = [], keyword = "") = > {
  if(! (tree && tree.length)) {return [];
  }
  if(! keyword) {return tree;
  }

  return R.filter((o) = > {
    // 1. If the parent node meets the condition, the parent node is returned
    if (o.title.includes(keyword)) {
      return true;
    }
    if(o.children? .length) {// 2. Otherwise, if there are child nodes, recursive processing is performed
      o.children = filterKeywordTreeFn(o.children, keyword);
    }
    // 3. If the child node meets the condition, the value is returned
    return o.children && o.children.length;
    // To avoid modifying the original data, use r.lone () here
  }, R.clone(tree));
};
Copy the code