preface

Hi, I’m Jay. In the usual work, the tree data structure must be familiar to us. This article will introduce the wiring between nodes, from data to rendering a tree. We will draw in SVG, and we will also introduce the calculation method of wiring between nodes. We will also show some general operations of trees in the form of dynamic effects, including depth-first traversal and breadth-first traversal.

Start building a tree

Before we begin, let’s outline the data structure of a conventional tree. In general, a tree has only one root node. The data structure of each node can be represented by the following code:

interface TreeNode<T> {
    value: T;
    id: Number;
    children: TreeNode<T>[]
}
Copy the code

After a general understanding of the data structure of trees and nodes, we agreed on a conventional tree data structure as follows:

export default {
    name: 'root'.root: true.id: 1.children: [{
        name: 2.id: 2.children: []}, {name: 3.id: 3.children: [{
            name: 4.id: 4.children: []}]}Copy the code

Node in the render

The following is to achieve the rendering of nodes, such as such a neat tree structure rendering, it is easy to think of the use of recursive form to render nodes and their children, you can write the following code:

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>
    `
}
Copy the code

With the above recursive code, we can render the node as above, but suffice it to say that the rendering above is completely unrelated to the tree. Don’t worry, we use CSS to give it a preliminary tree model, mainly using Flex layout, let the nodes with the same level automatically spread, layout code is as follows:

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;
}
Copy the code

As you can see, with just a few lines of CSS code, you can make clutter nodes look like trees. Don’t see it yet? It’s okay. Just add the edges.

Nodal edge drawing

Edge drawing using SVG, if you are not very familiar with SVG, you can take a look at my article SVG instance introduction and animation practice.

Drawing edges involves some calculation, and I’m going to go into as much detail as I can by drawing them. So first of all, draw the edges and what we’re going to do is we’re going to start at the center of a child node, and we’re going to end at the center of its parent node, and we’re going to draw an oblique line. There are three relative relationships between parent and child nodes:

The parent node is in the upper right of the child node
The parent node is in the upper left of the child node
The parent node is directly above the child node

Let’s take the example that the parent node is in the upper right of the child node to explain the coordinates and width and height calculation of SVG elements, as well as the drawing of edges. First, an oblique line would look something like this:

So for calculation purposes, we can place an SVG element like this:

Here we let the two vertices of SVG lie on the center points of the two nodes, because the coordinates of the center points of the two nodes are relatively easy to obtain, and the width and height of SVG can be easily obtained by using the position information of the two points, so that the position of the SVG elements can be determined. The beginning and end of the slash line are the vertices of the SVG element, and the coordinates are fairly straightforward. Having as many points as possible on a particular point makes our solution a lot easier. The browser normally uses the point in the upper left corner as the origin of the coordinates, and the axis relationship is roughly as follows:

Let’s find the starting vertex coordinates of SVG, i.e. the coordinates of the upper left corner point, as shown in the figure below:

The nodes here are hard to represent because OF the rounded corners, so I’m going to represent the original rectangles together, and the origin of the rectangles is the vertex in the upper left corner of the rectangle. Assume that the rectangle with center point A, R1, has coordinates of origin x1 and width W1; The R2 coordinates of the rectangle with center point B have the origin x-coordinate x2 and the width of R2 is w2. So it is not difficult to see from the figure that OA = (x1+w1/2) – (x2+w2/2), OA is the width of SVG element, and the abscissa of O point is also easily obtained as X2 + W2/2.

Similarly, assume that the origin of R1 coordinate is y1 and the height of R1 is H1; R2, the origin is y2, and R2 is h2. OB = (y2+ H1/2) – (y1+h1/2), OB is the height of the SVG element, and the ordinate of O is y1+ H1/2. At this point, we have figured out the width, height and position of the SVG element. Width and height are used to locate the diagonal coordinates, and position is used to locate the relationship between nodes. The above is the calculation idea when the parent node is in the upper right of the child node. The other two cases have the same calculation idea. The main drawing logic is 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
}

// Draw logic for a specific edge
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(The '-')
    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}` // Draw a line from upper right to lower left
    } else if (px < nx) {
        width = (nx + nw / 2) - (px + pw / 2)
        left = px + pw / 2
        d = `M0 0 L${width} ${height}` // Draw a line from the top left to the bottom right
    } else {
        width = 2
        left = px + pw / 2
        d = `M ${width / 2} 0 L${width / 2} ${height}` // Draw a line straight down
    }

    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')))}Copy the code

The above is all the logic of drawing edges. For aesthetics, I use stroke-Dasharray and stroke-Dashoffset to hide the redundant line segments. These two attributes are also introduced in the article I mentioned above, and students who are not familiar with them can have a look first. The implementation effect is as follows:

Node operation

Here we take a look at the most common node operations, including selecting, adding, and deleting nodes. The first thing to do before adding or deleting nodes is to select the node, where all events are delegated to the parent element.

The selected node

Select the node code is relatively simple, save the node click, click the corresponding node to add the style.

let currentNode

function initEvent() {
    document.addEventListener('click'.e= > {
        const classList = e.target.classList
        if ([...classList].includes('node')) {
            return clickNode(e)
        } else {
            // Deselect effect
            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
}
Copy the code

Add or delete a node

To add and delete nodes, dom is directly manipulated to add child nodes or delete nodes, and then maintain data. Flex layout will do the node placement for us, and the edge calculation will be recalculated after the node layout is complete.

With the layout and edge drawing, add and delete operations will become relatively simple, you can directly look at the code:

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' // For convenience, write the contents of the node directly
    const child = getNodeFragment(newId, currentNode.id, text)
    const children = currentNode.parentNode.querySelector('.tree-children')
    children.appendChild(child)
    renderLines()

    // Maintain data
    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()
}

Copy the code

Tree traversal can also be animated

Tree traversal generally has two kinds, depth first traversal and breadth first traversal. So what does it mean to make tree traversal work? Let’s take a look at the image first:

Taking depth-first traversal as an example, the idea to achieve this effect is as follows:

dfsThe data node is taken out and tiled into the array
The traversal number group animates each node:
- Copy a new node based on the node in the tree
- The new node jumps first
- Sets the offset property of the new node to move to the location specified in the content area

As for the calculation method of offset attribute of node, in fact, it is almost the same as the calculation of drawing edge described in the article, which will not be described here.

The specific code is as follows:

let isAnimate = false
const fakeContainer = document.querySelector('.fake-container')
const content = document.querySelector('.content')

Depth-first traversal
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') // Node jump animation
        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); })}Copy the code

With the showNodeAnimate function above, it is also easy to implement breadth-first animation. Because all that’s left is to push the breadth-first iterated data into the array, all that’s left is to loop through showNodeAnimate. The code is as follows:

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)})}}}Copy the code

The last

That’s all for this article. If you found it interesting or helpful, give it a thumbs up and follow. I look forward to hearing from you in the comments section

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Visualize data structures – make your trees pop out of the paper

preface

Start building a tree

Node in the render

Nodal edge drawing

Node operation

The selected node

Add or delete a node

Tree traversal can also be animated

The last

Visualize data structures – make your trees pop out of the paper

preface

Start building a tree

Node in the render

Nodal edge drawing

Node operation

The selected node

Add or delete a node

Tree traversal can also be animated

The last

Related Posts

What you don’t know about Console

Job Summary 2- Custom popboxes

叒 Yi is a dynamic resume