At the forefront of

There are few aspects of data structure design in the front end, the most commonly used is some operations on the tree structure. In a sense, front-end work itself is a work direction in dealing with tree structures. After all, DOM is a natural tree structure. Therefore, how to operate the tree structure well is an indispensable ability for front-end engineers.

Tree structure

define

What is a tree structure? From a data structure perspective:

  • Trees are nonlinear data structures
  • Each node may have zero or more descendants
  • Each node has a unique parent (if there are more than one parent, it is a graph)

classification

Trees can be divided into different types based on nodes. The most common types are:

  • Binary tree
  • Binary search tree
  • Balanced binary search tree
  • The difference between red and black trees is not detailed here, please check out the details

Common tree structure in the front end

The DOM tree structure

The following HTML structure is a natural tree structure. Below each Dom node, there are 0/1/ multiple child nodes.

Object tree structure

  • An array

Characteristics: For each object node, there may or may not be children

let obj = [
    {
        id: 1,
        type: 'dom',
        children: [
            {
                id: 2,
                type: 'html'
            }
        ]
    },
    {
        id: 3,
        type: 'css',
        children: [
            {
                id: 4,
                type: 'javascript'}}]];Copy the code
  • The most common form of object is the abstract syntax tree:

Characteristics: There are different properties under the properties of an object, and there may be different properties under each property

This format is often used in data statistics.

Tree structure traversal in Javascript

In fact, in my opinion, there are many forms of tree structure, but the front-end work rarely involves modification of tree nodes and other operations, most of which are traversal and statistical data.

Requirement scenario: Take Dom tree structure as an example: 1. Output the name and depth of each node; 3

  • Assuming you already have a tree structure, the childNodes are childNodes (why not children? Look it up yourself.)

Depth-first traversal

Depth-first traversal, also called DFS (Deep First Search), traverses the child nodes of a node first, and then the brother nodes of a node.

  • Recursive output
function DeepSearch(node, deep = 0) {
    const child = node.childNodes;

    const { nodeName } = node;
    console.log(`name:${nodeName},deep:${deep}`);

    for(leti = 0, len = child.length; i < len; i++) { DeepSearch(child[i], deep + 1); }}Copy the code
  • Non-recursive output
function deepSearch(node, deep = 0) {
    const stack = [];
    const deepArr = [];
    stack.push(node);
    deepArr.push(0);
    while(stack.length ! == 0){ const node = stack.shift(); const deep = deepArr.shift(); const { nodeName } = node; console.log(`name:${nodeName},deep:${deep}`);

        const nodes = child.childNodes;
        for( leti = node.length; i > 0; i--) { stack.unshift(nodes[i]); deep.unshift(deep + 1); }}}Copy the code

Breadth-first traversal

Breadth-first, as opposed to depth-first, traverses the sibling nodes of a node first, and then the child nodes.

  • Recursive output
function BreadSearch(node, deep = 0) {
    const child = node.childNodes;
    const res = [];

    for(let i = 0, len = child.length; i < len; i++) {

        const { nodeName } = node;
        console.log(`name:${nodeName},deep:${deep}`);

        res.push(child[i]);
    }

    DeepSearch(res, deep + 1);        

}
Copy the code
  • Non-recursive output
function breadSearch(node, deep = 0) {
    const stack = [];
    const deepArr = [];
    stack.push(node);
    deepArr.push(0);
    while(stack.length ! == 0 ) { const node = stack.shift(); cosnt deep = stack.shift(); const { nodeName } = node; console.log(`name:${nodeName},deep:${deep}`);

        for(leti = 0, len = child.length; i < len; i++) { stack.push(child[i]); }}}Copy the code

The business scenario

Tree operations in the front end, often to generate specific tree structures. Common scenarios include route generation and menu generation.

routing

The react-router is used as an example.

Simple case (BAD)

In general, react-router routes are as follows:

<Switch>
    <Route path="/home" component={A}/>
    <Route path="/manage" component={B}/>
    <Route path="/customer"component={C}/> ... . </Switch>Copy the code

But if everything is written the way above, for every route you add, you have to add one underneath the content

    <Route path="/extra" component={D}/>
Copy the code

This makes the code difficult to maintain and unreadable.

How to configure (better)

Configuration is better than internal code modification every time you open a route.

const routers = [
    {
        path: '/a',
        component: A
    },
    {
        title: 'test',
        id: 'exam',
        path: '/b',
        children: [
            {
                path: '/c',
                component: C
            },
            {
                path: '/d',
                component: D
            }
        ]
    }
];

function getRoute (routes, rootPath = ' ') {
    let res = [];
    for (let i = 0, len = routes.length; i < len; i++) {
        const route = routes[i];
        const { path } = route;
        if (route.children) {
            res = [...res, ...getRoute(route.children, path)];
        } else {
            res.push(
                <Route
                    path={`${rootPath}${path}`}... route /> ); }}return res;
};

<Switch>
    {
        getRoute(routers)
    }
</Switch>
Copy the code

The menu

Menus and routing are very similar, and are often used together. I won’t go into details here, because they are too similar. I’ll leave it to you.

The resources