关于javascript:可视化数据结构让你的树跃然纸上

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

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

关于javascript:可视化数据结构让你的树跃然纸上

前言

开始构建一棵树

节点渲染

节点边绘制

节点操作

选中节点

增删节点

树的遍历也能够动起来

最初