前言

大家好，我是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 currentNode

function 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 = 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 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)
            })
        }
    }
}

最后

以上就是本文的所有内容，如果觉得有意思或者对你有帮助的话，点个赞和关注吧～也期待你在评论区与我交流

可视化数据结构——让你的树跃然纸上

前言

开始构建一棵树

节点渲染

节点边绘制

节点操作

选中节点

增删节点

树的遍历也可以动起来

最后

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

可视化数据结构——让你的树跃然纸上

前言

开始构建一棵树

节点渲染

节点边绘制

节点操作

选中节点

增删节点

树的遍历也可以动起来

最后

热门文章

最新文章

相关课程

相关电子书