At some point, a tree graph reflecting the parent-child relationship between nodes needs to be implemented on the page, as follows:

Figure 1



The online Demo


Generally speaking, the function of this kind of chart class is implemented by referring to a third-party library. At first, I also intended to directly introduce a library to complete this function, but I searched around and found that there are few third-party libraries to implement this function

  • OrgChart seems to be a library that has existed for a long time. The style and interaction are a little old, and the function redundancy is not simple enough. The compressed volume of Vue version is around 100KB, which is not small

  • The vuE-org-tree style and interaction are comfortable, but it can only be arranged vertically, with no options for horizontal arrangement, which is not suitable for the actual business encountered

For these reasons, not having a satisfactory third-party library to meet the business needs, and not being willing to deal with it, they decided to build their own wheels

DOM structure

First analyze the structure of UI, different from common tree structure, demand in the UI, I have received the parent node is not keep all the child nodes of the overall vertical center alignment (for the convenience of narrative, the alignment model for short transverse vertical alignment, temporary not consider vertical levels with the matching center alignment mode), Instead, it is centered with the first child node (referred to simply as first-element alignment for narrative purposes)

The advantage of this layout is that if there are enough children, the parent node is not positioned beyond the user’s easy reach in order to be aligned with the whole of the child nodes

For example, if the overall height of the child node is more than two screen heights, the parent node’s Y-axis height should be more than one screen height in order to be vertically centered with the child node as a whole, that is, to be outside the screen, the user needs to slide the screen to find the parent node. If the parent node is always centered with the first child node, this happens less often and more nodes are visible to the user

Figure 2

The downside, of course, is that it’s not as aesthetically pleasing as centering (but not ugly), and it only works with landscape trees, not vertical ones

Both layout modes have their advantages and disadvantages, not better or worse, but just a tradeoff of what you need more of

The first element alignment pattern has two problems to solve

  • Parent-child node alignment problem

For the first-element alignment pattern, the parent node must be aligned not only with the immediate first child, but also with the immediate first child of the immediate first child, and if there are more children below, then continue to be aligned

In the figure below, 0 is the root node, 1 is the first child of 0, 2 is the second child of 0, 3 is the third child of 0, 4 is the first child of 1, and 5 is the first child of 4. Then nodes 0, 1, 4, and 5 must be vertically centered

Figure 3
  • Height of the connecting line of the child node

If the first element alignment pattern is used, the height of the connection line is computed

1, 2, 3, as child nodes of node 0, 0 and 1, 2, 3 nodes connected the height of the vertical line, is the need for real-time calculation, because the node 0, 1, 2, 3, can be customized, so the height of the four nodes is different, the height of the vertical line depends on the 1, 2, 3 and 1, 2, 3, the height of each child nodes, When the tree is initialized, or nodes are expanded/contracted, the height of the vertical connection line needs to change accordingly

For the first point, I immediately thought that WE could put 0, 1, 4 and 5 in the same container and then set the VERtical-align: middle CSS property to solve the problem. However, this would disrupt the hierarchical structure relationship between nodes and also cause trouble for subsequent operations, so I decided to change the layout

Figure 4.

For example, node 3 is the child node of node 0, and node 3 is also the parent node of nodes 6 and 7. Then, we can combine the parent node (no matter which level the parent node is at, It is a parent as long as it has children) and all of its children (no matter how deep in the hierarchy they are included) are put into a container as a whole

Nodes for node 0, 1, 2, 3, 4, 5, 6, 7 are its children, will be 0, 1, 2, 3, 4, 5, 6, 7 together into a container, which is the blue box above For node 1, 4, 5 are its nodes, will be 1, 4, and 5 together into a container, which is the green box above

For node 3, nodes 6 and 7 are all children, so put 3, 6 and 7 together into a container, which is the red dotted box in the figure above

For node 4, node 5 is its child, so put 4 and 5 together into a container, which is the yellow dotted box in the figure above

For other nodes with no children, which can also be regarded as parents without children, they are put into a container themselves

This layout ensures that the DOM structure is consistent with the data structure and maintains the relationship between parent and child hierarchies

The node position is initialized

If each node is located in its correct position, then the whole tree is naturally correct. To ensure that each node is located in its correct position is actually the solution to the two problems mentioned above

The parent node is vertically centered with the first child node under all its child hierarchies

Vertical-align = vertical-align = vertical-align = vertical-align = vertical-align = vertical-align = vertical-align = vertical-align = vertical-align = vertical-align = vertical-align Middle (or any other way to center two flat elements vertically) will do

Figure 5

For the first element alignment mode, you can also place the parent node and its first child at all levels in the same DOM hierarchy and use vertical-align: Middle (or any other way to center two flat elements vertically) works, but as mentioned earlier, this DOM layout breaks the hierarchy and is not conducive to subsequent operations, and if multiple elements are distributed in multiple containers, it is difficult to center them vertically with CSS

CSS is not, can only use JS, and the use of JS calculation and DOM manipulation ability, in fact, is relatively simple

Depth-first traversal is used to obtain the DOM of the parent node and the first child node in all its child hierarchies. Then, from these nodes, the height of the node with the highest height is used as the height of the entire container, and the other nodes use this height as the baseline for vertical centering

For example, for nodes 0, 1, 4 and 5 in Figure 4 above, node 4 has the highest height, so the position of node 4 does not need to be changed. By adjusting the Y-axis position of nodes 0, 1 and 5, it is ensured that they are vertically centered and aligned with node 4 (I used margin-top here).

function computedParentElesPosition(parentEles: HTMLElement[]) {
  const heights = parentEles.map(ele= > ele.offsetHeight)
  // Find the maximum height
  const maxHeight = Math.max.apply(null, heights)
  const halfMaxHeight = maxHeight / 2
 parentEles.forEach((ele, index) = > {  if (heights[index] < maxHeight) {  ele.style.marginTop = halfMaxHeight - heights[index] / 2 + 'px'  } else {  ele.style.marginTop = '0'  }  }) } Copy the code

Height of the connecting line of the child node

If the horizontal, vertical and center alignment mode is used, it can be solved with CSS alone

Figure 6.

As shown above, for the parent node 0, its direct child nodes 1, 2, 3, the height of the vertical cable is node and all its level 1 half the height of the child nodes in the container together, add node 2 container’s height, and node 3 and all level half the height of the child nodes in the container together

As shown in the figure above, the height of the vertical connection line is the height of all the child nodes: half the height of the first child node + half the height of the last child node + the height of all other child nodes

The height of the child node refers to the height of the child node and the height of a large container made up of all the children at all levels

For node 1, for example, the height is refers to the node 1 and 4, 5, 6, 7 of the height of the large container, that is the height of the red dotted box in the figure, in addition to keep the tree, coordination between child nodes under the parent node will exist certain spacing, up and down this portion of the gap is also as part of a large container

You can take advantage of these child elements in a large container, to vertical cable splicing, to node 1, 4, 5, 6, 7 in the red dotted line for big container elements, the lower part of the left margin can be as part of the vertical line, usually using a half height big container element is red dotted line height of pseudo elements to complete;

For node 2, the entire left border of the large container is part of the vertical connection line;

For the large container element with cyan dotted line where nodes 3, 8 and 9 are located, the upper part of the left border can be used as part of the vertical connection line, which can be completed by using a pseudo-element whose height is half of the large container element with cyan dotted line.

In this way, the vertical connection line is completed, as for those horizontal connection lines, it is even simpler, generally also through the pseudo-elements

But if you switch to the first-element alignment mode, it’s not so simple

First element alignment mode, the alignment is all levels of the first child of the node, the node is not under the same level, and its height, height of any child nodes, child nodes, there are several straton nodes is uncertain, such as child nodes, the starting point of the vertical line can’t lead to determine the position and height, so need through calculation to complete

However, it is not difficult, just need to find the first and last child nodes of all children under the parent node, by calculating the position between the two, can get the height of the vertical connection line, because the DOM structure maintains the hierarchical structure between the parent and child, so it is easy to get

For example, for node 0 in Figure 4, the vertical connection height of the connector’s child nodes is:

Node3.bottom - Node1.top - Node1.height / 2 - Node3.height / 2
Copy the code

Of course, in addition to the height, the position of the vertical connection line also needs to be calculated, it is relatively simple

Tree update

The contraction/expansion of nodes and the change of node content height will inevitably affect the layout of the tree

For horizontal, vertical and center alignment, no additional operations are required. After the node is shrunk/expanded, the CSS is automatically applied

Figure 7.

Nodes for example above, 1 after shrinkage, 4, 5, 6, 7 is removed from the tree, the node 1, 4, 5, 6, 7 in the large container elements, namely the red dotted line frame element height automatically become smaller, nodes 1, 2, 3, in a large container consisting of a vertical cable height with the smaller, vertical center alignment node 0 and the large container, so will automatically change position

But if it’s the first element alignment, it’s a little bit of a hassle, and you still need to do the calculation

Updates can be regarded as a whole tree initialization, again through the whole of the re-initialization to solve, but it’s certainly not too friendly, a page is beating happens, may also affect the operation of the user (such as the change of the scroll bar), the second is certainly exist a lot of double counting, not to achieve optimum performance, the idea of do not conform to the pursuit of perfection

Most of the updates are partial, affecting only a small number of nodes in the region, and there is no need to re-initialize the entire tree

Figure 8.

For example, for node 2 in the figure above, it shrinks child node 4 (and thus makes node 5 invisible), affecting two places

  1. Container node 2 is highly before node 2, 4, 5, 3, 4 at the nodes as a benchmark for vertical center alignment, node 4, 5, now left node 2, then the height of the node 2 is the height of the container, it should be restored to its original position, don’t need any node to keep centered vertically aligned

  2. The height of the container where nodes 2, 4 and 5 are located before the height of the connecting line of child elements is higher than the height of the container where node 2 is located now, so the height of the vertical connecting line connecting nodes 1, 2 and 3 is definitely shorter, and the height needs to be recalculated

In addition, because the components support node at the time of initialization allows his son not spread (that is, there may be some child nodes and not at the time of initialization), so if the child nodes of the node is the first time, you will need to put this node as a small tree, on the local initialization, To calculate the position relation of the first expanded child node under it

However, node 0 and node 1 above node 2 will not have any change, which is a rule. That is, the change of node will only affect the nodes at the same layer and below it, and the nodes above it will not be affected. Therefore, in the process of calculation, there is no need to calculate the elements above

summary

Although this component is Vue based, there is actually a lot of direct DOM calculation, which is the price of pursuing component customization. If you do not use first-element alignment but normal horizontal and vertical alignment, then the rendering result is basically the final result without any DOM adjustment. However, this does not mean that the first-element alignment pattern performance is poor, because by hitting the necessary logic and caching, a lot of meaningless calculations can be reduced

On my computer, to initialize a 100 nodes of the tree, 30 ms, even the general class of computer, no more test results should be, because even without using any optimization measures, this calculation is also fundamental for the CPU is not the bottleneck, and the actual scene, to show the user’s tree, It’s hard to get as many as 100 nodes (more than that, and you have to wonder if it makes sense to show the user that much information all at once), so it’s fine

The code has been put on Github, and this component is packaged as an NPM package, if you are interested, you can take a look