前言
在前端的工作中,如果遇到树形 DOM
结构、树型控件、级联选择等等需求,都需要使用到深度优先遍历(简称 DFS
)和广度优先遍历(简称 BFS
)。 DFS
和 BFS
可能也是前端处理复杂需求用到最多的算法之一了。今天就让我们来好好学习它。
树
上面描述的“树型控件”、“级联选择”,它们处理的数据结构都是树,那么树又是什么呢?
树是一种分层数据的抽象模型,树可以看做是一种特殊的链表,只是链表只有一个 next
指向下一个节点,而树的每个节点都有多个 next
指向下一个节点。
一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点:
JavaScript 表示树
JavaScript
中没有树这种数据结构,但是可以用 Object
和 Array
来模拟一颗树。
const tree = {
value:"a",
children:[
{
value:"b",
children:[
{
value:"d",
children:[
{
value:"e",
children:[]
}
]
}
]
},
{
value:"c",
children:[
{
value:"f",
children:[]
},
{
value:"g",
children:[]
}
]
}
]
}
看到这个结构是不是非常熟悉,工作中应该算是经常碰到了把。对于树的常见操作有: DFS
、 BFS
以及二叉树(一种特殊的树)的先中后序遍历。今天本文的重点则是 DFS
以及 BFS
。
DFS
深度优先遍历,尽可能深的搜索树的分支。
序号表示被搜索的顺序,它的算法口诀是:
- 访问根节点;
- 对根节点的 children 挨个(递归)进行深度优先遍历。
代码实现:
# tree 为上文所述的结构,这里就不重复展示
# 深度优先代码
const dfs = (node)=>{
console.log(node.value);
node.children.forEach(dfs);
}
# 调用
dfs(tree);
打印结果输出顺序: a、b、d、e、c、f、g
。
BFS
广度优先遍历,先访问离根节点最近的节点。
序号表示被搜索的顺序,先把同层的节点给遍历完,再去遍历子节点。它的算法口诀是:
- 新建一个队列,把根节点入队;
- 把对头出队并访问;
- 把对头的
children
挨个入队; - 重复(循环)第二、三步,直到队列为空。
代码实现:
const bfs = (root)=>{
# 根节点入队
const stack = [root];
# 只要栈不为空就一直循环
while (stack.length > 0){
# 取出栈首
const node = stack.shift();
# 遍历根节点,把它的子节点推入栈尾
node.children.forEach((item)=> stack.push(item));
# 打印节点值
console.log(node.value);
}
}
bfs(tree);
打印结果输出顺序: a、b、c、d、e、f、g
。
渲染 Antd 中树组件
在实际工作中我们肯定碰到过需要去渲染一棵树的情景,我们就以渲染 Antd
中树组件为例来巩固下所学知识。
import { Tree } from 'antd';
const { TreeNode } = Tree;
class Demo extends React.Component {
render() {
return (
<Tree> <TreeNode title="parent 1" key="0-0"> <TreeNode title="parent 1-0" key="0-0-0" > <TreeNode title="leaf" key="0-0-0-0" /> <TreeNode title="leaf" key="0-0-0-1" /> </TreeNode> <TreeNode title="parent 1-1" key="0-0-1"> <TreeNode title="leaf" key="0-0-1-0" /> </TreeNode> </TreeNode> </Tree>
);
}
}
ReactDOM.render(<Demo />, mountNode);
渲染效果:
其中 TreeNode
是已经写好的,假设现在我们要根据后台返回的数据结构来渲染成相应的树,该怎么做呢?
后台返回的数据结构可能会长这个样子:
const tree = [
{
key: "0",
title: "0",
children: [
{
key: "0-1",
title: "0-1",
children: []
},
{
key: "0-2",
title: "0-2",
children: []
}
]
},
{
key: "1",
title: "1",
children: [
{
key: "1-1",
title: "1-1",
children: []
},
{
key: "1-2",
title: "1-2",
children: []
}
]
}
];
代码实现:
import React from "react";
import ReactDOM from "react-dom";
import "antd/dist/antd.css";
import "./index.css";
import { Tree } from "antd";
const { TreeNode } = Tree;
class Demo extends React.Component {
dfs = (node) => {
return (
<TreeNode title={node.title} key={node.key}> {node.children.map(this.dfs)} </TreeNode>
);
};
render() {
return <Tree>{tree.map(this.dfs)}</Tree>;
}
}
ReactDOM.render(<Demo />, document.getElementById("container"));
最终渲染效果:
小结
深度优先和广度优先并没有想象中的那么复杂,而且在平时项目中的应用非常广泛,因此需要我们重点掌握。
今天的文章JavaScript 算法之树的深度优先与广度优先分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/16397.html