前沿

前端中设计数据结构的方面不多，最常用的就是对树结构的一些操作。从某种意义上来说，前端工作本身就是和树结构打交道的一个工作方向。毕竟，DOM就是天然的树结构。所以如何能够良好地对树结构进行操作，是前端工程师不可或缺的一项能力。

树结构

定义

什么是树结构呢？从数据结构的角度来讲：

树是非线性数据结构
每个节点可能会有0个或多个后代
每个节点具备唯一的父节点（如果有多个父节点，那就是图了）

前端中常见的树结构

DOM树结构

下面的html结构就是一个天然的树结构。每个Dom节点下面，有0/1/多个子节点。

对象树结构

数组形式

特点: 每一个对象节点，下面可能会有children，也可能没有children

let obj = [    {        id: 1,        type: 'dom',        children: [            {                id: 2,                type: 'html'            }        ]    },    {        id: 3,        type: 'css',        children: [            {                id: 4,                type: 'javascript'            }        ]    }];

对象形式

最常见的就是抽象语法树：

特点: 对象的属性下面有不同的属性，每一个属性下面可能还会有不同的属性

这种格式经常在数据统计中出现。

Javascript中树结构的遍历

其实在我看来，树的结构形式有很多种，但是，前端工作中很少涉及对树节点的修改等操作，大部分是遍历和统计数据。

需求场景：下面以Dom树结构为例：
1、需要输出每个节点的名称和节点深度
3、深度优先和广度优先都需要实现

假定已经有了对应的树结构，子节点是childNodes（为啥不用children呢？自己去查吧）

深度优先遍历

深度优先遍历，又叫DFS（deep first search），遍历顺序是优先遍历节点的子节点，然后再是节点的兄弟节点。

递归输出

function DeepSearch(node, deep = 0) {    const child = node.childNodes;    const { nodeName } = node;    console.log(`name:${nodeName},deep:${deep}`);    for(let i = 0, len = child.length; i < len; i++) {        DeepSearch(child[i], deep + 1);            }}

非递归输出

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( let i = node.length; i > 0; i--) {            stack.unshift(nodes[i]);            deep.unshift(deep + 1);        }    }}

广度优先遍历

广度优先，正好和深度优先策略相反，先遍历节点的兄弟节点，再遍历子节点。

递归输出

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);        }

非递归输出

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(let i = 0, len = child.length; i < len; i++) {            stack.push(child[i]);        }    }}

业务场景

前端中的树操作，经常是生成特定的树结构。常见的场景有生成路由和生成菜单。

路由

下面以react-router为例，说明：

简单情况（bad）

一般情况下，react-router的路由是下面的:

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

但是如果所有的都按照上面的写法，每加一个路由，都需要取在内容下面，加一个

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

这样会造成代码不容易维护，而且可读性不好。

配置的方式（better）

配置的方式总好过，每次打开路由的内部代码修改。

const routers = [    {        path: '/a',        component: A    },    {        title: '考试',        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>

菜单

菜单和路由的方式很相似，而且通常会结合在一起使用，具体的写法，这里就不赘述了，因为实在是太相似了，留给你们吧。。

参考资料

Javascript中的树结构

前沿

树结构

定义

分类