Master the JavaScript tree structure depth-first algorithm in one article

What is a tree?

In real life, I believe everyone is familiar with trees. Whether they are willows, poplars or peach trees, it can be said that trees can be seen everywhere in our lives; in the computer world, trees are an abstraction of a hierarchical structure. model ,

as shown below:

There are many applications of tree structure. For example, a company's organizational structure can be represented by a tree, as shown below:

In addition to organizational structures, things like family trees, provinces and cities, etc. can be represented using tree structures.

Tree terminology

There are many terms for trees, as shown below:

• Tree : a finite set of n (n≥0) nodes. When n=0 , it is called an empty tree;
• node degree : the number of subtrees of a node. For example, the degree of node B is 2, and the degree of node A is It is 3;
• the degree of the tree : the maximum degree among all the nodes of the tree. For example, in the above figure, the degree of the tree is 3;
• leaf node : a node with degree 0, also called a leaf node ;
• child node : as shown in the figure above;
• sibling node : As shown in the picture above;
• root node : as shown in the picture above;
• tree depth : the maximum level among all nodes in the tree, for example, the depth of the tree in the picture above is 3;
• node level : for example, the level of the E node is 3, and the node level is the parent Node level + 1, the level of the root node is 1;
• path : the channel from one node to another node , for example, the path of A→H is ADH ;
• path length : the distance from one node to another node , such as the path of A→H That’s 3.

The tree structure in JavaScript

can be said to be one of the most common data structures in the front-end, such as DOM tree, cascading selection, tree components, etc.;

JavaScript does not provide the tree data structure, but we can use objects and Array to simulate a tree,

such as the following code:

const tree = {
  value: 'A',
  children: [
    {
      value: 'B',
      children: [
        { value: 'E', children: null },
        { value: 'F', children: null },
      ],
    },
    {
      value: 'C',
      children: [{ value: 'G', children: null }],
    },
    {
      value: 'D',
      children: [
        { value: 'H', children: null },
        { value: 'I', children: null },
      ],
    },
  ],
}

Advantages of breadth-first and depth traversal algorithms

Depth-first

The so-called depth-first traversal algorithm is to search the branches of the tree as deeply as possible. Its traversal order is as follows:

The implementation idea is as follows:

• visit the root node;
• continue depth-first traversal (recursion) of children of the root node;

the implementation code is as follows:

function dfs(root) {
  console.log(root.value)
  root.children && root.children.forEach(dfs) // Consistent with the following // if (root.children) {
  // root.children.forEach(child => {
  //dfs(child)
  // })
  // }
}
dfs(tree) //This tree is the tree defined previously/* Result A
B
E
F
C
G
D
H
I
*/

As you can see, the order is consistent with the picture, which means there is no problem with our algorithm.

Breadth priority

The so-called breadth priority is to visit the nodes closest to the root node in order. Its traversal order is as follows:

The implementation idea is as follows:

• Create a queue, add the root node to the queue;
• dequeue the head of the queue and access it;
• add children of the head of the queue to the queue in sequence;
• repeat steps 2 and 3 until the queue is empty.

The implementation code is as follows:

function bfs(root) {
  // 1. Create a new queue and add nodes to the queue const q = [root]
  // 4 Repeat while (q.length > 0) {
    const node = q.shift() // 2 queue head is dequeued console.log(node.value)
    // 3 children, the head of the team, are added to the team node.children &&
      node.children.forEach(child => {
        q.push(child)
      })
  }
}
bfs(tree)
/* Result A
B
C
D
E
F
G
H
I
*/

As you can see, the order is consistent with the picture, which means there is no problem with our algorithm.