A tree is an abstract data model that layers data. The most common example of a tree in real life is a family tree, or an organizational chart of a company, as shown below.

In the front-end data structure, the most common tree structure we see is DOM tree, cascade selection, tree selection.

Such as:

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

For data in this tree structure, our common operations are depth-first traversal and breadth-first traversal.

Depth-first traversal

The so-called depth-first traversal is to parse the in-depth data first. For example, the data is read in a => B => C => D => E => F => G

Depth-first traversal idea

① Traverse the tree node

② If the tree node has children, traverse the children node

Repeat (1) (2) (3)

Code implementation

function dfs(treeNodes) {
    treeNodes.forEach(item= > {
        console.log(item.val);
        if(item.children){ dfs(item.children); }})}Copy the code

Breadth-first traversal

Breadth-first traversal means traversing the external nodes as much as possible. Wait until the external nodes are traversed, then traverse the internal nodes. For example, our traversal order would be a => B => E => C => D => E => f => G

Breadth-first traversal idea

Because when you iterate, you have to follow a certain order, and you have a fifO order. So consider using the data structure queue to do this for us.

① Create a queue.

② Add nodes to the team.

③ Nodes exit the queue and traverse the nodes. At the same time, children of nodes are added to the queue.

Repeat (2) (3) (4)

Code implementation

function bfs (treeNodes){
    const queue = [...treeNodes];
    while(queue.length) {
        const item = queue.shift();
        console.log(item.val);
        if(item.children){ queue.push(... item.children); }}}Copy the code