可视化数据结构——让你的树跃然纸上
前言
大家好，我是jay。在平时的工作中，树这种数据结构想必我们都不会陌生。本文会介绍从数据到渲染一个树，节点间的连线我们会采用SVG来绘画，同时也会介绍节点间连线的计算方法。我们也会以动效的形式来展现树的一些常规操作，包括深度优先遍历和广度优先遍历。
开始构建一棵树
开始之前，先来大概说一下一棵常规的树的数据结构，一般来说，我们说的树只有一个根结点，每个节点的数据结构大概可以使用下面的代码来表示：
interface TreeNode {
value: T;
id: Number;
children: TreeNode[]
} 大致了解了树与节点的数据结构之后，我们约定一棵常规的树的数据结构如下：
export default {
name: 'root',
root: true,
id: 1,
children: [{
name: 2,
id: 2,
children: []
}, {
name: 3,
id: 3,
children: [{
name: 4,
id: 4,
children: []
}]
}]
}节点渲染 下面先来实现节点的渲染，像这种这么规整的树结构渲染，容易想到的应该是使用递归的形式去渲染节点以及其子节点，可以写出如下代码：
const app = document.querySelector('#app')
renderNodes()
function renderNodes() {
const html = `
${renderNode(tree, null)}
`
app.innerHTML += html
}function renderNode(tree, parentId) {
return `${tree.name}${tree.children.length > 0
?
tree.children.map(child => {
return renderNode(child, tree.id)
}).join('')
:
''}`
}通过上述的递归代码，我们可以渲染出节点如上，不过有一说一，上面渲染出来的东西可以说跟树毫不相关。别着急，我们利用
CSS让它初具树的模型，主要使用flex布局，让节点同层级自动撑开，布局代码如下：body {
padding: 0;
margin: 0;
}
.node {
width: 50px;
height: 50px;
border-radius: 100%;
border: 1px solid gray;
text-align: center;
line-height: 50px;
margin: 20px;
}
.tree-children {
display: flex;
}
.tree {
display: flex;
flex-direction: column;
align-items: center;
}可以看到通过数行
CSS代码，就可以让杂乱无章节点看起来具有树的形式。还没看出来？没事，把边加上就好了。节点边绘制 边的绘制利用的是
SVG，如果你对SVG还不是很了解的话，可以先看一下我的这一篇文章SVG实例入门与动画实战。边的绘制会涉及到一些计算，我会通过画图的形式来尽量详细讲解。首先，绘制边其实我们要做的是以一个子节点的中心作为起点，以它的父节点的中心作为终点，画一条斜线。父子节点的相对关系有如下三种：
- 父节点在子节点右上方
- 父节点在子节点左上方
- 父节点在子节点正上方
SVG元素的坐标与宽高计算，以及边的绘画。首先，画一条斜线的话就类似于下面这样：那么为了方便计算，我们可以这么地放置一个
SVG元素如下：这里我们让
SVG的两个顶点落在两个节点的中心点上，因为两个节点的中心点坐标是比较容易求得的，而利用两个点的位置信息也可以很方便的求得SVG的宽和高，进而SVG元素的位置就确定了。而我们画斜线的起点跟终点都是SVG元素的顶点，坐标也是十分明了的。让尽量多的点落在特殊点上，会让我们的求解变得简单很多。浏览器正常情况下都是以左上角的点为坐标原点，坐标轴关系大致如下：下面先来求
SVG的起始顶点坐标，即左上角点的坐标，如图所示：这里的节点因为我加了圆角不好表示，所以我这里把原先的矩形给一起表示出来，以下说的矩形坐标原点是矩形左上角的顶点。假设中心点为
A的矩形R1坐标原点横坐标为x1，R1宽度为w1；中心点为B的矩形R2坐标原点横坐标为x2，R2宽度为w2。那么从图中不难看出OA = (x1+w1/2) - (x2+w2/2)，OA就是SVG元素的宽度，O点横坐标也容易得出为x2+w2/2。同理，假设
R1坐标原点纵坐标为y1，R1高度为h1；R2坐标原点纵坐标为y2，R2高度为h2。也可求得OB = (y2+h2/2) - (y1+h1/2)，OB就是SVG元素的高度，O点的纵坐标为y1+h1/2。到这里，我们就求出了这个SVG元素的宽高，位置。宽高用来定位斜线的坐标，位置用来定位与节点间的关系。以上就是父节点在子节点右上方位置关系时，计算的思路，其他两种情况的计算思路大同小异。具体代码实现如下，主要的绘制逻辑是renderLine()：renderLines()
function renderLines() {
const nodes = document.querySelectorAll('.tree-node')
let fragment = document.createElement('div')
for (let i = 0;
i < nodes.length;
i++) {
const node = nodes[i]
const nodeId = node.getAttribute('id')
const parentId = node.getAttribute('parent-id')
const line = renderLine(`line-${nodeId}-${parentId}`)
fragment.appendChild(line)
}
const svgContainer = document.querySelector('.svg-container')
svgContainer.innerHTML = fragment.innerHTML
}//具体一条边的绘制逻辑
function renderLine(id) {
const line = document.querySelector(`.${id}`)
let svg = null,
path = null
if (!line) {
svg = document.createElementNS('http://www.w3.org/2000/svg', 'svg')
path = document.createElementNS('http://www.w3.org/2000/svg', 'path')
path.setAttributeNS('http://www.w3.org/2000/svg', 'd', '')
svg.appendChild(path)
svg.setAttribute('id', id)
} else {
svg = line
path = svg.querySelector('path')
}
const arr = id.split('-')
const nodeId = arr[1]
const parentId = arr[2]
const node = document.getElementById(nodeId)
const parentNode = document.getElementById(parentId)const { x: nx, y: ny } = getNodePosition(node)
const { w: nw, h: nh } = getNodeSize(node)
const { x: px, y: py } = getNodePosition(parentNode)
const { w: pw, h: ph } = getNodeSize(parentNode)let width, height, left, top
let d
height = (ny + nh / 2) - (py + ph / 2)
top = py + ph / 2
if (px > nx) {
width = (px + pw / 2) - (nx + nw / 2)
left = nx + nw / 2
d = `M${width} 0 L0 ${height}` //从右上角至左下角画线
} else if (px < nx) {
width = (nx + nw / 2) - (px + pw / 2)
left = px + pw / 2
d = `M0 0 L${width} ${height}` //从左上角至右下角画线
} else {
width = 2
left = px + pw / 2
d = `M ${width / 2} 0 L${width / 2} ${height}` //画一条竖直向下的线
}const length = Math.round(Math.sqrt(Math.pow(width, 2) + Math.pow(height, 2)))
const val = length - (pw / 2 + nw / 2)svg.setAttribute('width', width)
svg.setAttribute('height', height)
path.setAttributeNS('http://www.w3.org/2000/svg', 'd', d)
path.setAttribute('style', `stroke:black;
stroke-dasharray:${val};
stroke-dashoffset:-${pw / 2}`)
svg.style = `position:absolute;
left:${left}px;
top:${top}px`
return svg
}function getNodePosition(node) {
const { x, y } = node.getBoundingClientRect()
return { x, y }
}function getNodeSize(node) {
const { width, height } = window.getComputedStyle(node)
return { w: getNumFromPx(width), h: getNumFromPx(height) }
}function getNumFromPx(str) {
return Number(str.substring(0, str.indexOf('p')))
}
上面就是全部绘制边的逻辑，为了美观，我使用了
stroke-dasharray和stroke-dashoffset去隐藏掉了多余的线段，这两个属性也在我上面提到过的文章里介绍到，不熟悉的同学可以先去看看。实现效果如下：节点操作 这里我们来介绍一下最常见的几种节点操作，包括选中节点、增加节点、删除节点。在做增删节点之前首先要做的是选中节点，这里所有的事件都会委托在父元素上。
选中节点 选中节点的代码比较简单，保存点击的节点，将点击的对应节点加上样式即可。
let currentNodefunction initEvent() {
document.addEventListener('click', e => {
const classList = e.target.classList
if ([...classList].includes('node')) {
return clickNode(e)
} else {
//取消选中效果
return cancelClickNode()
}
})
}function clickNode(e) {
if (currentNode) {
currentNode.classList.remove('current')
}
currentNode = e.target
currentNode.classList.add('current')
}function cancelClickNode() {
if (currentNode) {
currentNode.classList.remove('current')
}
currentNode = null
}增删节点 增删节点这里采取的是直接操作
dom增加子节点或者删除节点，然后再去维护数据。节点的位置排开会有flex布局帮我们做，而边的计算则要在节点布局完成之后重新计算。有了布局实现与边的绘制之后，增删操作都会变的比较简单，可以直接看代码：
function findNodeById(node, id) {
let val = nullfunction dfs(node, id) {
if (val) return
if (node.id == id) {
val = node
return val
} else if (node.children.length > 0) {
for (let i = 0;
i < node.children.length;
i++) {
dfs(node.children[i], id)
}
}
}
dfs(node, id)
return val
}function addNode() {
if (!currentNode) {
return
}
const newId = genId()
const text = 'new' //为了方便，直接写死了节点的内容
const child = getNodeFragment(newId, currentNode.id, text)
const children = currentNode.parentNode.querySelector('.tree-children')
children.appendChild(child)
renderLines()//维护数据
const nodeData = https://www.it610.com/article/findNodeById(data, currentNode.id)
nodeData.children.push({ id: newId, name: text, children: [] })
}function getNodeFragment(id, parentId, text) {
const div = document.createElement('div')
div.classList = 'tree'
div.innerHTML = `
${text}`
return div
}function deleteNode() {
const parentId = currentNode.getAttribute('parent-id')
if (parentId === 'null') {
return
}
const node = currentNode.parentNode
node.parentNode.removeChild(node)
renderLines()
let parentNodeData = https://www.it610.com/article/findNodeById(data, parentId)
let index = null
for (let i = 0;
i < parentNodeData.children.length;
i++) {
const child = parentNodeData.children[i]
if (child.id == currentNode.id) {
index = i
break
}
}
if (index !== null) {
parentNodeData.children.splice(index, 1)
}
cancelClickNode()
}
树的遍历也可以动起来 树的遍历常规来说一般有两种，深度优先遍历和广度优先遍历。那么让树的遍历动起来是啥意思呢？不如先来看一下效果图吧：
以深度优先遍历为例，实现这个效果的思路如下：
dfs将数据节点取出来平铺到数组中- 【可视化数据结构——让你的树跃然纸上】遍历数组对每个节点进行动画：
- 根据树上的节点复制一个新节点
- 新节点先跳跃一下
- 设置新节点的偏移属性，移动到内容区指定的位置
具体代码如下：
let isAnimate = false
const fakeContainer = document.querySelector('.fake-container')
const content = document.querySelector('.content')//深度优先遍历
async function dfsTree() {
if (isAnimate) {
return
}
isAnimate = true
const res = []
dfs(data, res)
for (let i = 0;
i < res.length;
i++) {
const { id } = res[i]
await showNodeAnimate(id)
}
isAnimate = false
}function dfs(node, res) {
res.push(node)
if (node.children.length > 0) {
node.children.forEach(child => {
dfs(child, res)
})
}
}function showNodeAnimate(id) {
const perWidth = 50
return new Promise(async(resolve, reject) => {
const originNode = document.getElementById(id)
const node = originNode.cloneNode(true)
const { x, y } = getNodePosition(originNode)
node.style = `
position:absolute;
left:${x}px;
top:${y}px;
border-color:red;
z-index:99;
margin:0;
transition:all 1s
`
fakeContainer.appendChild(node)
const contentChildren = content.children
const { x: contentX, y: contentY } = getNodePosition(content)
const delY = contentY
let delX
if (contentChildren.length === 0) {
delX = contentX
} else {
const length = contentChildren.length
delX = length * (perWidth + 20)
}
node.classList.add('jump') //节点跳跃动画
await sleep(500)
node.classList.remove('jump')
originNode.style.backgroundColor = 'gray'
node.style.top = delY + 'px'
node.style.left = delX + 'px'
await sleep(1000)
content.appendChild(node)
resolve()
})}function sleep(timeout) {
return new Promise(resolve => {
setTimeout(() => {
resolve()
}, timeout);
})
}有了上面的
showNodeAnimate这个函数之后，我们也很容易去实现广度优先遍历时的动画。因为只要把广度优先遍历的数据推进数组就行，剩下的事情就是循环调用showNodeAnimate即可。代码如下：async function bfsTree() {
if (isAnimate) {
return
}
const res = bfs(data)
isAnimate = true
for (let i = 0;
i < res.length;
i++) {
const { id } = res[i]
await showNodeAnimate(id)
}
isAnimate = false
}function bfs(node) {
const tmp = []
doBfs(node, tmp, 0)
const res = []
tmp.forEach(item => {
res.push(...item)
})
return resfunction doBfs(node, res, level) {
if (!res[level]) {
res[level] = []
}
res[level].push(node)
if (node.children.length > 0) {
node.children.forEach(child => {
doBfs(child, res, level + 1)
})
}
}
}最后 以上就是本文的所有内容，如果觉得有意思或者对你有帮助的话，点个赞和关注吧～也期待你在评论区与我交流
推荐阅读
- request和response——请求响应对象
- Jackson原理探究—Mixins其一
- 羽夏逆向指引——反制
- Spark—GraphX编程指南
- java|我们一起学一学渗透测试——基础概念
- python|【十年网络安全工程师整理】—100渗透测试工具使用方法介绍
- 数据结构和算法|[字符串]重复的子字符串
- CSS|【总结】（前端面试必考题 —— CSS两栏布局（最全面））
- 面试|【总结】（大厂面试常考手撕代码 —— JavaScript实现效果）
- 推荐算法|相似度计算（1）——余弦相似度