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

This article brings you relevant knowledge about javascript, mainly introducing the JavaScript tree structure depth-first algorithm. The tree structure can be said to be one of the most common data structures in the front-end, for example Let’s take a look at DOM tree, cascade selection, and tree components. I hope it will be helpful to everyone.

[Related recommendations: javascript video tutorial, web front-end]

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 a kind of layering The abstract model of the structure ,

is shown in the figure below:

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

In addition to the organizational structure, tree structures such as genealogy, provinces and cities can also be used To represent.

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;
• The degree of the node: The number of subtrees of the node , for example, the degree of node B is 2, the degree of node A is 3;
• The degree of the tree: all of the tree The maximum degree of a node. For example, in the above figure, the degree of the tree is 3;
• Leaf node:A node with degree 0 is also called a leaf node;
• Child node: As shown above;
• Sibling node: As shown above;
• Root node: As shown in the picture above;
• The depth of the tree: the maximum level among all nodes in the , for example, the depth of the tree in the picture above is 3;
• The level of the node: For example, the level of the E node is 3, the level of the node is The level of the parent node is 1, and the level of the root node is 1;
• Path : The channel from one node to another node, for example, the path from A→H is A D H;
• Path length: The distance from one node to another node, for example, the path A→H is 3.

Tree in JavaScript

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

JavaScript does not provide a tree data structure, but we can simulate a tree through objects and arrays,

For example, 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 },
      ],
    },
  ],
}

Breadth-first and depth-advantage 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 sequence is as follows :

The implementation idea is as follows:

• Visit the root node;
• To root The children of the node continues to perform depth-first traversal (recursive);

The implementation code is as follows:

function dfs(root) {
  console.log(root.value)
  root.children && root.children.forEach(dfs) // 与下面一致
  // if (root.children) {
  //   root.children.forEach(child => {
  //     dfs(child)
  //   })
  // }
}
dfs(tree) // 这个tree就是前面定义的那个树
/* 结果
A
B
E
F
C
G
D
H
I
*/

As you can see, and the figure The order in is consistent, 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 sequence. Its traversal sequence is as follows:

The implementation ideas are as follows:

• Create a queue and add the root node to the queue;
• Dequeue the head of the queue and access it;
• Add the children at the head of the queue into the queue in turn;
• Repeat steps 2 and 3 until the queue is empty.

The implementation code is as follows:

function bfs(root) {
  // 1. 新建队列 跟节点入队
  const q = [root]
  // 4 重复执行
  while (q.length > 0) {
    const node = q.shift() // 2 队头出队
    console.log(node.value)
    // 3 队头 children 依次入队
    node.children &&
      node.children.forEach(child => {
        q.push(child)
      })
  }
}
bfs(tree)
/* 结果
A
B
C
D
E
F
G
H
I
*/

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

【Related recommendations: javascript video tutorial, web front-end】

The above is the detailed content of Master the JavaScript tree structure depth-first algorithm in one article. For more information, please follow other related articles on the PHP Chinese website!