乐趣区

Javascript中的树结构

jiezi

前沿

    前端中设计数据结构的方面不多，最常用的就是对 树结构的一些操作。从某种意义上来说，前端工作本身就是和树结构打交道的一个工作方向。毕竟，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>

菜单

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

参考资料

退出移动版