preface

In the front-end work, if you meet the requirements of tree DOM structure, tree control, cascading selection, etc., you need to use depth first traversal (DFS) and breadth first traversal (BFS). DFS and BFS are probably one of the most popular front-end algorithms for handling complex requirements. Let’s learn it well today.

The tree

The “tree controls” and “cascading selection” described above all deal with data structures that are trees, but what is a tree?

A tree is an abstract model of hierarchical data. A tree can be thought of as a special linked list, but there is only one linked listnextPoints to the next node, and there are multiple nodes in the treenextPoint to the next node.



A tree structure consists of a series of nodes that have parent-child relationships. Each node has a parent (except the first node at the top) and zero or more child nodes:



JavaScript said the tree

There is no tree data structure in JavaScript, but you can use Object and Array to simulate a tree.

const tree = {
  value:"a".children:[
    {
      value:"b".children:[
        {
          value:"d".children:[
            {
              value:"e".children:[]}]}, {value:"c".children:[
        {
          value:"f".children:[]
        },
        {
          value:"g".children:[]}]}Copy the code

See this structure is not very familiar, should be often encountered in the work. Common operations on trees include DFS, BFS, and middle-before-back-traversal of binary trees (a special kind of tree). Today’s article focuses on DFS and BFS.

DFS

Depth-first traversal, searching branches of the tree as deep as possible.





Serial number indicates the order to be searched, and its algorithm formula is:

  1. Access the root node;
  2. The children of the root node are traversed depth-first one by one (recursively).

Code implementation:

# tree is the structure described above, so the # depth-first code will not be shown again hereconst dfs = (node) = >{
  console.log(node.value); node.children.forEach(dfs); } # call DFS (tree);Copy the code

Output sequence: A, B, D, E, C, F, and G.

BFS

Breadth-first traversal visits the node closest to the root node first.



Serial number indicates the order to be searched. First, the nodes of the same layer are traversed, and then the child nodes are traversed. Its algorithm formula is:

  1. Create a queue and add the root node to the queue.
  2. To take the enemy out and visit;
  3. The adversarychildrenTeam up one by one;
  4. Repeat the second and third steps until the queue is empty.

Code implementation:

const bfs = (root) = >{# the root node is queuedconststack = [root]; Loop as long as the stack is not emptywhile (stack.length > 0){# fetch the top of stackconstnode = stack.shift(); # loop through the root node and push its children to the end of the stack(item) = >stack.push(item)); Print the node valueconsole.log(node.value);
  }
}

bfs(tree);
Copy the code

Output sequence: A, B, C, D, E, F, and G.

Render the tree component in Antd

In the actual work we must have encountered the need to render a tree, we will render Antd tree components as an example to consolidate the knowledge.

import { Tree } from 'antd';

const { TreeNode } = Tree;

class Demo extends React.Component {

  render() {
    return (
      <Tree>
        <TreeNode title="parent 1" key="0-0">
          <TreeNode title="parent 1-0" key="0-0-0" >
            <TreeNode title="leaf" key="0-0-0-0" />
            <TreeNode title="leaf" key="0-0-0-1" />
          </TreeNode>
          <TreeNode title="parent 1-1" key="0-0-1">
            <TreeNode title="leaf" key="0-0-1-0" />
          </TreeNode>
        </TreeNode>
      </Tree>
    );
  }
}

ReactDOM.render(<Demo />, mountNode);
Copy the code

Render effect:





Among themTreeNodeIt’s already written. Suppose we now want to render the corresponding tree based on the data structure returned in the background. How do we do that?



The data structure returned in the background might look something like this:

const tree = [
  {
    key: "0".title: "0".children: [{key: "0-1".title: "0-1".children: []}, {key: "0-2".title: "0-2".children: []}]}, {key: "1".title: "1".children: [{key: "1-1".title: "1-1".children: []}, {key: "1-2".title: "1-2".children: []}]}];Copy the code

Code implementation:

import React from "react";
import ReactDOM from "react-dom";
import "antd/dist/antd.css";
import "./index.css";
import { Tree } from "antd";

const { TreeNode } = Tree;

class Demo extends React.Component {
  dfs = (node) = > {
    return (
      <TreeNode title={node.title} key={node.key}>
        {node.children.map(this.dfs)}
      </TreeNode>
    );
  };

  render() {
    return <Tree>{tree.map(this.dfs)}</Tree>;
  }
}

ReactDOM.render(<Demo />.document.getElementById("container"));
Copy the code

Final render:



summary

Depth first and breadth first are not as complex as imagined, and are widely used in daily projects, so we need to focus on mastering them.