资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/Javascript中的树结构

Javascript中的树结构

_Dreams / 764人阅读

摘要：前沿前端中设计数据结构的方面不多，最常用的就是对树结构的一些操作。毕竟，就是天然的树结构。递归输出非递归输出业务场景前端中的树操作，经常是生成特定的树结构。

前沿

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


    
    
    
    ... ...

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

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

配置的方式（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(
                
            );
        }
    }
    return res;
};


    {
        getRoute(routers)
    }
菜单

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

参考资料
GPU云服务器 云服务器 java中的树结构图 数据仓库中的逻辑结构 javascript中的 linux内核中的数据结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/104770.html

相关文章

  • JavaScript 数据结构与算法之美 - 非线性表中的树、堆是干嘛用的 ？其数据结构是怎样的 ？

    摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。非线性表中的树堆是干嘛用的其数据结构是怎样的希望大家带着这两个问题阅读下文。其中，前中后序，表示的是节点与它的左右子树节点遍历访问的先后顺序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 想学好前端，先练好内功，内功不行，...

    singerye 评论0 收藏0

  • 学习javascript数据结构(四)——树

    摘要：原文博客地址学习数据结构四树知乎专栏简书专题前端进击者知乎前端进击者简书博主博客地址的个人博客人之所能，不能兼备，弃其所短，取其所长。通常子树被称作左子树和右子树。敬请期待数据结构篇最后一篇文章学习数据结构五图参考文章树数据结构二叉树 前言 总括： 本文讲解了数据结构中的[树]的概念，尽可能通俗易懂的解释树这种数据结构的概念，使用javascript实现了树，如有纰漏，欢迎批评指正。 ...

    Dean 评论0 收藏0

  • 学习JavaScript数据结构与算法 — 树

    摘要：定义树同散列表一样，是一种非顺序数据结构。一个节点及其后代可以组成一个子树如图中的。方法允许传入子树一直遍历左侧子节点，直到底部搜索特定值搜索特定值的处理与插入值的处理类似。同理，找左侧子树的最大值替换上来也可以。 定义 树同散列表一样，是一种非顺序数据结构。现实中树的例子有家谱、公司组织架构图及其它树形结构关系。树由一系列节点构成，每个节点都有一个父节点（除根节点外）以及零个或多个子...

    shiguibiao 评论0 收藏0

  • 学习Virtual Dom笔记

    摘要：通过深度优先遍历两棵树，每层节点进行对比，记录下每个节点的差异。所以可以对那棵树也进行深度优先遍历，遍历的时候从步骤二生成的对象中找出当前遍历的节点差异，然后进行操作。 实现虚拟(Virtual) Dom 把一个div元素的属性打印出来，如下： showImg(https://segmentfault.com/img/bVbnPe1?w=1239&h=336); 可以看到仅仅是第一层，...

    DobbyKim 评论0 收藏0

  • 深度剖析：如何实现一个 Virtual DOM 算法

    摘要：本文所实现的完整代码存放在。这就是所谓的算法。两个树的完全的算法是一个时间复杂度为的问题。如果有差异的话就记录到一个对象里面。如和的不同，会被所替代。这牵涉到两个列表的对比算法，需要另外起一个小节来讨论。 作者：戴嘉华 转载请注明出处并保留原文链接（ https://github.com/livoras/blog/issues/13 ）和作者信息。 目录： 1 前言 2 对前端应用状...

    vvpvvp 评论0 收藏0

发表评论

登陆后可评论

0条评论

_Dreams

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<