前言
大家好，我是jay。在平时的工作中，树这种数据结构想必咱们都不会生疏。本文会介绍从数据到渲染一个树，节点间的连线咱们会采纳SVG来绘画，同时也会介绍节点间连线的计算方法。咱们也会以动效的模式来展示树的一些惯例操作，包含深度优先遍历和广度优先遍历。
开始构建一棵树
开始之前，先来大略说一下一棵惯例的树的数据结构，一般来说，咱们说的树只有一个根结点，每个节点的数据结构大略能够应用上面的代码来示意：
interface TreeNode<T> { value: T; id: Number; children: TreeNode<T>[]}大抵理解了树与节点的数据结构之后，咱们约定一棵惯例的树的数据结构如下：
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 = ` <div class="tree-container">${renderNode(tree, null)}</div> ` app.innerHTML += html}function renderNode(tree, parentId) { return ` <div class="tree"> <div id="${tree.id}" parent-id="${parentId}" class="${tree.root ? 'root-node' : 'tree-node'} node"> ${tree.name} </div> <div class="tree-children"> ${tree.children.length > 0 ? tree.children.map(child => { return renderNode(child, tree.id) }).join('') : ''} </div> </div> `}通过上述的递归代码，咱们能够渲染出节点如上，不过有一说一，下面渲染进去的货色能够说跟树息息相关。别着急，咱们利用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 = null function 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 = 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 = ` <div id="${id}" parent-id="${parentId}" class="tree-node node">${text}</div> <div class="tree-children"></div> ` 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 = 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 = falseconst 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 res function 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) }) } }}最初
以上就是本文的所有内容，如果感觉有意思或者对你有帮忙的话，点个赞和关注吧～也期待你在评论区与我交换