前端之数据结构（四）

Augus

关注

发布于: 1 小时前

前文已经介绍了，栈、队列、链表、集合和字典。今天就该介绍树这一数据结构，接下来且听我娓娓道来。

树

树是什么呢？在生活中，大家对树肯定不陌生，不就是一种植物嘛。像杨树、柳树、榆树等等。

但在计算机科学中就不一样了。

一种 分层 数据的抽象模型，在前端应用广泛。
前端工作中常见的树包括： DOM 树、级联选择、树形控件...

JS 中没有树，但是可以用 Object和Array 构建树。
像这样满足分层数据结构的都可以说是树。

树的常用操作：深度/广度优先遍历、先中后序遍历。

深度优先遍历

尽可能深的搜索树的分支。

1. 访问根节点。

2. 对根节点的 children 挨个进行深度优先遍历。

const tree = {    val: 'a',    children: [        {            val: 'b',            children: [                {                    val: 'd',                    children: []                }, {                    val: 'e',                    children: []                }]        },        {            val: 'c',            children: [{                val: 'f',                children: []            }, {                val: 'g',                children: []            }]        }    ]}
const dfs = (root) => {    console.log(root.val);    root.children.forEach(dfs)}
dfs(tree)
// a b d e c f g

复制代码

广度优先遍历

先访问离根节点最近的节点。

1. 新建一个队列，把根节点入队。

2. 把队头出队并访问。

3. 把对头的 children 挨个入队。

4. 重复第二、第三，直到队列为空。

const tree = {    val: 'a',    children: [        {            val: 'b',            children: [                {                    val: 'd',                    children: []                }, {                    val: 'e',                    children: []                }]        },        {            val: 'c',            children: [{                val: 'f',                children: []            }, {                val: 'g',                children: []            }]        }    ]}
const dfs = (root) => {    console.log(root.val);    root.children.forEach(dfs)}
const bfs = (root) => {    const q = [root];    while (q.length > 0) {        const n = q.shift()        console.log(n.val);        n.children.forEach(child => q.push(child))    }}
bfs(tree)
// a b c d e f g

复制代码

今天先分享到这里啦，拜拜~~~

发布于: 1 小时前阅读数: 3

Augus

关注

爱瞎搞的软件开发工程师 2021.06.10 加入

某摸鱼集团

发布

暂无评论

创作场景

前端之数据结构（四）

树

深度优先遍历

广度优先遍历

Augus

评论