Depth-first traversal DFS and breadth-first traversal BFS are commonly used for traversal of tree structures. The most common is traversal of Dom nodes, which is used to search the Dom tree, as shown below

Depth-first traversal of DFS

Assuming that the initial state is that all vertices in the graph are not accessed, the graph starts from a certain vertex V, visits this vertex first, and then starts from its adjacent points that are not accessed successively, until all vertices in the graph that share paths with V are accessed. If there are other vertices that have not been accessed at this time, select another vertex that has not been accessed as the starting point, and repeat the process until all vertices in the graph have been accessed. Deep traversal first DFS can be implemented in three ways, two recursive and one non-recursive

let deepTraversal1 = (node, nodeList = []) => { if (node ! == null) { nodeList.push(node) let children = node.children if(children.length) { for (let i = 0; i < children.length; i++) { deepTraversal1(children[i], nodeList) } } } return nodeList } let deepTraversal2 = (node) => { let nodeList = [] if (node ! == null) { nodeList.push(node) let children = node.children if(children.length) { for (let i = 0; i < children.length; // divide and conquer, NodeList = nodelist. concat(deepTraversal2(children[I]))}} return nodeList} let deepTraversal3 = (node) => {// Define the stack data structure, Let nodeList = [] if (node) {// Push (node) while (stack.length) { Pop () nodelist. push(item) let children = item.children if(children.length) {for (let I = children.length - 1; i >= 0; Push (children[I])}}}} return nodeList}Copy the code

The second recursive method, deepTraversal2, uses the idea of divide-and-conquer. As the name implies, divide and conquer means that a problem is broken down into several small problems, which are further broken down into several small problems until the problem is simple enough to obtain the result, and then the sub-results are continuously merged upward to become the final result.

Breadth-first traversal of BFS

Starting from a vertex v in the figure, after visited v visit v each in turn have not visited the adjacent points, then separately from the adjacent point to access them in order of adjacent points, and make “first accessed the vertices of the adjacent point before being accessed after the vertices of the adjacent point is accessed, until all has been accessed in the figure vertex adjacent points are access to. If there are still vertices in the graph that have not been accessed, select another vertex that has not been accessed as a new starting point and repeat the process until all vertices in the graph are accessed.

Let widthTraversal2 = (node) => {let nodes = [] Let queue = [] if (node) {queue.push(node) while (queue.length) {// Let item = queue.shift().push(item) let children = item.children if(children.length) { for (let i = 0; i < children.length; I ++) {queue. Push (children[I])}}}} return nodes}Copy the code

Application: Recursive tree data query all parent nodes of the node, query all child nodes of the node, etc

Example:

Const data = [{id: 1, label: '1', children: [{id: 4, label:' 1 1', children: [{id: 9, label: '1 1', children: [{id: 9, label:' 1 1', children: [{id: 9, label: '1 1', children: [{id: 9, label: 'level 3' 1-1-1}, {id: 10, label: 'level 3' 1-1-2}]]}}, {id: 2, label: 'level 2' children: [{id: 5, label: 'secondary 2-1}, {id: 6, label: 'secondary 2-2'}}, {id: 3, label: 'level 3' children: [{id: 7, label: 'secondary 3-1}, {id: 8, label:' secondary 3-2}]}];Copy the code

Gets the objects of all the parent nodes of this node by ID

function getParentId(list,id) { for (let i in list) { if(list[i].id==id){ return [list[i]] } if(list[i].children){ let node=getParentId(list[i].children,id); if(node! Return node.concat(list[I])}}}} console.log(getParentId(data,10)) // Print the desired dataCopy the code

Gets the object of the node based on its ID

function getId(list,id) { for (let i in list) { if(list[i].id==id){ return [list[i]] } if(list[i].children){ let node=getParentId(list[i].children,id); if(node! ==undefined){ return node; }}}} console.log(getId(data,4)) // Print out the desired dataCopy the code