Common tree structure algorithm sharing

1. Tree Introduction:

Tree (English: tree) is an abstract data type (ADT) used to simulate a collection of data with a tree-like structure. It is composed of n (n>=1) finite nodes to form a set with hierarchical relations. It’s called a tree because it looks like an upside-down tree, meaning it has roots up and leaves down.

Binary tree: Each node has a maximum of two child nodes; Complete binary tree: a special binary tree. The characteristics of a complete binary tree are as follows: leaf nodes can only appear at the lowest and lower levels, and the lowest level of leaf nodes are concentrated in the left part of the tree. It should be noted that a full binary tree must be a complete binary tree, and a complete binary tree is not necessarily a full binary tree;

Binary search tree (BST, binary search tree) : The left child of a node is smaller than the parent, and the right child of a node is larger than the parent.

A red-black tree is a balanced binary tree. It is balanced by the fact that the height difference between the left subtree and the right subtree is no more than 1. The left subtree and the right subtree maintain an equilibrium relationship. Each node has a binary lookup tree with color attributes, red or black.

2. Recursive processing

Before we can start the tree, we must first talk about the recursive processing of the tree, transforming the data from the back end into a uniform format structure.

function handleTreeData(data) {
  let arr = [];
  data.forEach((item) = >{ arr.push({ ... item,title: item.name,
      key: item.id,
      children:
        item.children && item.children.length
          ? handleTreeData(item.children)
          : [],
    });
  });
  return arr;
}

let treedata = [
  {
    name: "1-1".id: 1.parentId: 0.children: [{name: "1-1-1".id: 2.parentId: 1,},],}];Copy the code

3. Traverse the tree:

One of the common scenarios of tree structure is traversal, which is divided into breadth-first traversal and depth-first traversal. Depth-first traversal is recursive, while breadth-first traversal is non-recursive and is usually realized by a loop. Depth-first traversal is divided into pre-order traversal, post-order traversal, binary tree and middle-order traversal, the implementation method can be recursive, can also be cyclic.

Breadth First (BFC) :

BFS starts at the root and traverses the nodes of the tree along the width of the tree. If all nodes are accessed, the algorithm aborts.

let tree = [
  {
    id: "1".title: "Node 1".children: [{id: "1-1".title: "Node 1-1"}, {id: "1-2".title: "Node 1-2",},],}, {id: "2".title: "Node 2".children: [{id: "2-1".title: "Node 2-1",},],},];// Breadth first
function treeForeach(tree, func) {
  let node;
  let list = [...tree];
  while((node = list.shift())) { func(node); node.children && list.push(... node.children);// Push the children element of the node to the end of the list each time, repeating until the last layer
  }
}
treeForeach(tree, (node) = > {
  console.log(node.title);
});
Copy the code

Depth First (DFC) :

These three traversal calculation methods can refer to the detailed content on the Internet

4. Tree data structure

The general knowledge is the common operation of function, recursion and array, and the basic algorithm of tree structure, so that we can better deal with business logic in the future.

1. List to tree:

A flat list of data, where we find the corresponding key fields, such as parentId and ID;

let list = [
  {
    id: "1".title: "Node 1".parentId: ""}, {id: "1-1".title: "Node 1-1".parentId: "1"}, {id: "1-2".title: "Node 1-2".parentId: "1"}, {id: "2".title: "Node 2".parentId: ""}, {id: "2-1".title: "Node 2-1".parentId: "2"}, {id: "3-1".title: "Node 3-1".parentId: "2-1",},];// Easy online version
function listToTree(list) {
  let info = list.reduce(
    (map, node) = > ((map[node.id] = node), (node.children = []), map),
    {}
  );
  return list.filter((node) = > {
    info[node.parentId] && info[node.parentId].children.push(node);
    return! node.parentId; }); }// console.log(listToTree(list));

// New user understanding version
function formatDataTree(list) {
  let parents = list.filter((p) = > p.parentId === "");
  let childrens = list.filter((c) = >c.parentId ! = ="");

  dataToTree(parents, childrens);

  return parents;
  function dataToTree(parents, childrens) {
    parents.map((p) = > {
      childrens.map((c, i) = > {
        if (c.parentId === p.id) {
          let _children = JSON.parse(JSON.stringify(childrens));
          _children.splice(i, 1);
          dataToTree([c], _children);
          if (p.children) {
            // Check whether children exist in the parent element
            p.children.push(c);
          } else{ p.children = [c]; }}}); }); }}console.log(formatDataTree(list));
Copy the code

2. Tree to list:

Ant. Design/Components /…

Often used in the use of tables to display the tree, before the back end for us to deal with, the front end can also do their own.

let tree = [
  {
    id: "1".title: "Node 1".children: [{id: "1-1".title: "Node 1-1"}, {id: "1-2".title: "Node 1-2",},],}, {id: "2".title: "Node 2".children: [{id: "2-1".title: "Node 2-1",},],},];// Implement recursion
function treeToList(tree, result = [], level = 0) {
  tree.forEach((node) = > {
    result.push(node);
    node.level = level + 1;
    node.children && treeToList(node.children, result, level + 1);
  });
  return result;
}
console.log(treeToList(tree))

// Method two: loop implementation
// function treeToList (tree) {
// let node, result = tree.map(node => (node.level = 1, node))
// for (let i = 0; i < result.length; i++) {
// if (! result[i].children) continue
// let list = result[i].children.map(node => (node.level = result[i].level + 1, node))
// result.splice(i+1, 0, ... list)
/ /}
// return result
/ /}

// Method 3: Easy online version
function treeToList(tree) {
  return (tree || []).reduce((total, current) = > {
    const{ children, ... obj } = current;returntotal.concat(obj, treeToList(children)); } []); }Copy the code

5. Tree structure search

Find node:

Finding nodes is actually a traversal process, traversal to meet the conditions of the node is returned, traversal is not found, return null. Similar to the array >find method, passed a function to determine whether the node meets the criteria, here we use the depth first, the code is as follows: Application scenario: directory tree search function.

Here are two aspects: depth priority and breadth priority.

let tree = [
  {
    id: "1".title: "Node 1".children: [{id: "1-1".title: "Node 1-1"}, {id: "1-2".title: "Node 1-2",},],}, {id: "2".title: "Node 2".children: [{id: "2-1".title: "Node 2-1",},],},];// Depth first
function treeFind(tree, func) {
  for (const data of tree) {
    if (func(data)) return data; // If yes, return directly
    if (data.children) { // If there is no child node to find, recursive call
      const res = treeFind(data.children, func);
      if (res) returnres; }}return null; // If none is found, return null
}
function findsingle(data) {
  if (data.title === "Node 1-2") {
    return true; }}console.log(treeFind(tree,findsingle)) //{id: '1-2', title: '1-2'}
Copy the code

// Breadth first
function treeFind(tree, func) {
  for (const data of tree) {
    if (func(data)) return data // Loop through all nodes of the first layer directly
  }

  const chidrens = tree.reduce((total, current) = > {
    returntotal.concat(current.children || []); } []);const res =  treeFind(chidrens, func);
  if (res) return res;
  return null;
}
Copy the code

Find node path:

It’s a little bit more complicated, because you don’t know what subtree the nodes are in, and you use the idea of backtracking. To find the path, use a sequential traversal, maintaining the ID of each node on the path in a queue, assuming the node is in the current branch, and backtracking if the current branch is not found.

let tree = [
  {
    id: "1".title: "Node 1".children: [{id: "1-1".title: "Node 1-1"}, {id: "1-2".title: "Node 1-2",},],}, {id: "2".title: "Node 2".children: [{id: "2-1".title: "Node 2-1",},],},];function treeFindPath(tree, func, path = []) {
  if(! tree)return []; / / short judgment
  for (const data of tree) {
    path.push(data.id);
    if (func(data)) return path;
    if (data.children) {
      const findChildren = treeFindPath(data.children, func, path);
      if (findChildren.length) return findChildren;
    }
    path.pop();
  }
  return [];
}

function findsingle(data) {
  if (data.title === "Node 1-2") {
    return true; }}console.log(treeFindPath(tree, findsingle, (path = []))) / / [' 1 ', '2')
Copy the code

Query multiple node paths

The idea is similar to finding a node path, but the code is simpler:

let tree = [
  {
    id: "1".title: "Node 1".children: [{id: "1-1".title: "Node 1-1"}, {id: "1-2".title: "Node 1-2",},],}, {id: "2".title: "Node 2".children: [{id: "2-1".title: "Node 2-1",},],},];function treeFindPath(tree, func, path = [], result = []) {
  for (const data of tree) {
    path.push(data.id);
    func(data) && result.push([...path]);
    data.children && treeFindPath(data.children, func, path, result);
    path.pop();
  }
  return result;
}

function findsingle(data) {
  if (data.title === "Node 1-2") {
    return true; }}console.log(treeFindPath(tree, findsingle)) //[['1', '1-2']]
Copy the code

6. Other common algorithms

The maximum depth of a tree

The maximum depth of the tree is what you do when you write drag; Use scenarios to achieve a maximum of 5 layers of drag trees. When dragging a node under the current node, it is necessary to determine whether the drag will exceed 5 layers. In this case, it is necessary to calculate the depth of the drag node and the depth of the current node, which cannot exceed 5.

let treedata = {
  name: "1-1".id: 1.parentId: 0.children: [{name: "1-1-1".id: 2.parentId: 1.children: []}, {name: "1-1-3".id: 4.parentId: 1.children: [{name: "1-1-3".id: 5.parentId: 4.children: []}, {name: "1-1-3".id: 6.parentId: 4.children: [],},],},],}; maxDepth =(root) = > {
  if (root === null) {
    return 0;
  }
  var max = 0;
  for (var i = 0; i < root.children.length; i++) {
    max = Math.max(max, maxDepth(root.children[i]));
  }
  return max + 1;
};
Copy the code

The total number of nodes in the tree

Application scenario: Mainly for the tree expansion level, if there are too many nodes, the page effect is not good if all expanded, according to the height of the current page and the number of nodes, see the expansion level.

let treedata = [
  {
    name: "1-1".id: 1.parentId: 0.children: [{name: "1-1-1".id: 2.parentId: 1.children: []}, {name: "1-1-3".id: 4.parentId: 1.children: [{name: "1-1-3".id: 5.parentId: 4.children: []}, {name: "1-1-3".id: 6.parentId: 4.children: [],},],},];let leafcount = 0;
function treeNodecount(data) {
  let arr = [];
  data.forEach((item) = > {
    leafcount++;
    arr.push({
      children:
        item.children && item.children.length
          ? treeNodecount(item.children)
          : [],
    });
  });
  return arr;
}

treeNodecount(treedata)
console.log(leafcount)
Copy the code

Tree structure screening

Tree structure filtering is to keep some nodes that meet the conditions and cut out others. Whether a node remains in the filtered tree structure depends on whether there are qualified nodes in its > and descendant nodes. We can pass in a function that describes the nodes that meet the criteria:

let tree = [
  {
    id: "1".title: "Node 1".children: [{id: "1-1".title: "Node 1-1"}, {id: "1-2".title: "Node 1-2",},],}, {id: "2".title: "Node 2".children: [{id: "2-1".title: "Node 2-1",},],},];function treeFilter(tree, func) {
  // Use map to copy nodes to avoid changing to the original tree
  return tree
    .map((node) = > ({ ...node }))
    .filter((node) = > {
      node.children = node.children && treeFilter(node.children, func);
      return func(node) || (node.children && node.children.length);
    });
}

function findsingle(data) {
  if (data.title === "Node 1") {
    return true; }}console.log(treeFilter(tree,findsingle)) 
/ / {
// id: "1"
// title: "node 1",
// children:[]
// }
Copy the code

Parse data from a tree based on conditions:

Application scenario: To find the type of data we want in a bunch of product customer hierarchies, the data returned is flat, so that we can use tables or other forms to show the results we want to see.

let tree = [
  {
    name: "1-1".id: 1.parentId: 0.type: "user".children: [{name: "1-1-1".id: 2.parentId: 1.children: [].type: "manager"}, {name: "1-1-3".id: 4.parentId: 2.type: "user".children: [{name: "1-1-3".id: 5.parentId: 4.children: [].type: "manager"}, {name: "1-1-3".id: 5.parentId: 4.children: [].type: "manager",}],},],},];function parseTreeData(tree) {
  return (tree || []).reduce((total, current) = > {
    const{ type, children, ... obj } = current;if (type === "manager") {
      return total.concat(obj);
    }
    const paserChildren = parseTreeData(children);

    returntotal.concat(paserChildren); } []); }console.log(parseTreeData(tree));
Copy the code

Add, delete, modify, and look up nodes in the tree:

This is relatively simple, such as the idea of inserting: get the current node, and then use the inserted node as the children data of the current node. Other delete, change, search are the use of recursive processing tree data, in the recursive process, do some operations.

Finally:

If you are interested in tree algorithms, you can click on the address below to learn more about algorithms. Tree – Leetcode brush problem link leetcode-cn.com/tag/tree/