用 DOM 与 CSS 展示二叉树

发布于 2022-05-04 21:53:07 字数 12623 浏览 1064 评论 0

本文内容较长，主要涉及如下内容：

二叉树及相关算法
Flexbox 布局
CSS 背景图片，计数器等应用
使用 SVG 做为背景图片会遇到的问题

最近在讲各种树的算法与题目的时候，为了给学生演示，总是想要看到树的结构，总是画出来又慢又丑，在控制台里展开看的话实在太麻烦，而且不够直观，我就寻思能不能把树给展示在页面里。

什么是二叉树

首先看一下二叉树的定义：一颗二叉树是由一个根结点和一个左子树和一颗右子树组成的结构，其左右子树分别又是一颗二叉树。

画成图就是下面这种形状：

           1
          / \
         /   \
        2     3
       / \   / \
      4   5 6   7
     / \
    8   9

关于二叉树的更多内容已经超出了本文的讨论范围，有兴趣的同学可以自行维基百科或者找其它相关的资料。

如何展示二叉树

现成的工具当然也有不少，比如 LeetCode 的自测数据输入框。一开始我也想要不自己做个这样的好了，但是细细想，感觉还蛮复杂的，每层的树的数量不确定，而且越往下层树的结点越多，真要想通过一颗树生成一个漂亮的图片，不管是 SVG 还是画在 Canvas 里，都是相当复杂的。

这是其一，其二是展示成图片的话还不利于交互，万一以后想要与展示出来的结构做些简单的交互，图片很显然是不行的，Canvas 实现交互需要计算坐标；SVG 虽然可以为结点绑定事件，但 SVG 的另一个问题是元素之间不能嵌套，虽然有 g 标签，但 g 标签其实只是对 SVG 中的标签进行分组，而不是实现树状（或递归）的嵌套，所以想要容易的在 SVG 里画出树也并不会比在 Canvas 里容易，一样需要计算每个结点的大小和坐标。

于是我就想，能不能用 HTML 跟 CSS 来显示一颗树的视觉结构呢？毕竟 CSS 可以方便的实现多级菜单，而多级菜单的本质其实就是多叉树。

经过简单的分析，我总结出如下几点：

首先，DOM 的结构就是树状的，用它来显示同为树结构的二叉树应该是相当容易的
第二，目前 CSS 有非常强大的布局功能，用上所有 CSS 最新的功能，可以很容易的实现非常灵活的布局
第三，用 DOM 来展示树结构，可以很方便的实现交互

从二叉树的定义来看，它是一个递归结构，根结点的左子树与右子树分别又是一颗二叉树，所以只要把一颗树考虑成其根结点、左子树和右子树就可以了，而左右子树的结构跟根结点一样，就像级联菜单一样，那么不难构想出如下 DOM 结构：

<div class="tree">
  <span>根结点</span>
  <div>【左子树】</div>
  <div>【右子树】</div>
</div>

其中左子树与右子树的 DOM 结构依然是你上面看到的这种，由于左右子树自身已经被一个 div.tree 元素包着，所以上面的结构其实并不需要里面的两个 div，而且去掉两个额外的 div 会在后面为我们带来一些便利，我们可以方便的用 CSS 仅选择表示叶子结点的 span 元素：span:only-child。

那么前面那颗二叉树如果按照上面的结构写成 DOM 将会是下面这样的（为了方便观察，把结点用【】括起来了）：

<div class="tree">
  <span class="leaf-node">【1】</span>
  <div class="tree">
    <span class="leaf-node">【2】</span>
    <div class="tree">
      <span class="leaf-node">【4】</span>
      <div class="tree">
        <span class="leaf-node">【8】</span>
      </div>
      <div class="tree">
        <span class="leaf-node">【9】</span>
      </div>
    </div>
    <div class="tree">
      <span class="leaf-node">【5】</span>
    </div>
  </div>
  <div class="tree">
    <span class="leaf-node">【3】</span>
    <div class="tree">
      <span class="leaf-node">【6】</span>
    </div>
    <div class="tree">
      <span class="leaf-node">【7】</span>
    </div>
  </div>
</div>

光有这个结构当然是看不出其树形结构的，还得考虑如何用 CSS 展示它。很明显，对于树，我们需要按如下形式展示它————根结点的值位于左子树与右子树的上方且居中，左右子树平分下方的空间：

------------------------
|        根结点        |
------------------------
|  左子树  |  右子树   |
------------------------

根结点独自在一行上占用全部的水平空间，左子树与右子树平分左右的空间，所以 span 元素的宽度应该要是 100%，左右子树的 div 宽度分别为 50%，这里必需要使用百分比的单位来布局，因为越往下层树的结点越多，每个结点的空间就越小，用绝对长度单位肯定是行不通的。

由于左右子树分别又是一个 div.tree，而且它们需要展示在左边和右边各占一半的空间，所在这个 div.tree 必须要能自适应其可用空间，放在多宽的位置它就展示多宽，这样一来，顶层的 div 结构（即根结点）也能自动占满可用空间。

当然是用 flex 布局了，虽然传统布局手段也可以做到想要的效果

div.tree {
  display: flex;
  flex-wrap: wrap;/*span 需要独占一行，所以此 flex 布局必须要折行显示 */
}
div.tree > span {
  width: 100%;
  text-align: center;
}
.tree > .tree {
  width: 50%;
}

对于前面那颗树，展示出来后有点奇怪，右子树都往下偏了一些，就像下面这样：

点击查看实时 Demo

究其原因，是因为 flex 布局中元素在侧轴上默认会拉伸，这个好办，给所有的 flex 父元素（即 div.tree）加一个 align-items: flex-start; 就可以了。

每层结点之间有点太近，这个好办，给 span 元素加点高度就可以了。

于是乎我们得到了如下视觉效果的二叉树，看起来很不错！

点击查看实时 Demo

但还差一件事，那就是父子结点之间的连线，这个好像不太好办，虽然可以使用边框生成斜线，但真心不太好控制；当然，还可以使用 2D 变幻来实现，但计算量还是有的，主要在于不同层级的连线，倾斜程度不同（如下图），能不能找到一个简单点的办法显示结点间的连线呢？

通过观察我们注意到父结点与两个子结点的相对位置比例总是保持不变的，如果把一颗树占用的水平宽度计为 100%，那么父结点总是在上方 50% 的位置，而两颗子树的根结点总是在下方 25% 和 75% 的位置。

所以只要能够实现一个能够随元素自动按比例拉伸的效果就可以了。很显然，背景图片可以满足我们的这个要求，而且足够简单。

事实上我们只需要一张像下面这样的倒 V 型的图片即可：

     /\
    /  \
   /    \

然后把它展示为 span 元素的背景图片，再做些简单的位置和大小调整就可以了！由于这张图片要占用一定的空间，span 元素的高度也要相应增加一丢丢：

为了方便演示，我给这张图片打了些底色以方便观察：

代码也很简单，使用背景图片把元素设置上去就可以了：

div.tree > span {
  width: 100%;
  text-align: center;
  padding-bottom: 3em;

  /* 设置这张黄颜色的背景图片 */
  background-image: url(dom-binary-tree/ud-v.png);
  background-repeat: no-repeat;
  background-size: 100% calc(100% - 1em);
  background-position: 0 1em;
}

由于图片中的倒 V 的顶点总是要在结点文字的下方，这里使用了 background-size 以及 calc 设置了图片的高度总为 100% - 1em，再合适 background-position 让图片从顶部往下偏 1em 的距离；当然，因为垂直方向上图片的高度是固定的，所以给图片留白也是行的。

大功告成！

处理多余的连线

等一下！最后一行的叶子结点怎么还有多余的连线？

理论上这也不过分，因为叶子结点实际上就是左右子树为空的二叉树，这么画出来，没毛病！

不过做为强迫症患者，我是无法接受这种效果的，再说，也从来没人会这么画二叉树。

于是乎前面我们设计的 HTML 结构派上用场了，对于叶子结点来说，它不再有两个 div 的兄弟结点，所以使用 span:only-child 选中它然后把它的背景图片隐藏就可以了！这也为什么我要把用于表示连线的背景图片设置到 span 元素上的原因。

/* 选中做为其父元素唯一子结点的 span 元素 */
div.tree span:only-child {
  background-image: none;

  /* 由于不需要背景，最后一行其实不需要多余的高度了，这样也可以在一些情况下节省空间 */
  padding-bottom: 0;
}

显示效果如下：

只有单边子树的情况

你们以为这样就又大功告成了吗？

如下这颗树的展示就有问题了：

          _1_
         /   \
        2     3
       / \     \
      4   5     7
     / 
    8

首先，7 是 3 的右子树，但它却展示在 3 的左边，原因也很明显，因为表示 7 这个颗的 div 是从左往右展示的，这时我开始怀念 float 了，如果布局是使用 float 实现的，那么给用于表示左子树的元素一个左浮动，给表示右子树的元素一个右浮动就可以了，这样即使只有单边的子树，它们也会自动显示在一边。然而我们使用的是 flex 布局。不过 flex 布局一样有办法实现这种效果，比如说 align-self，不过遗憾的是它是在侧轴方向控制位置的。

想要实现让左子树往左偏的效果，我们可以让表示右子树的 div 元素的 margin-left 为 auto（同理让表示左子树的 div 元素的 margin-right 为 auto），在 flex 布局中，如果一个 flex 子元素的在主轴方向上的 margin 为 auto 且该方向还有空间，而且元素自身没有 flex-grow 的话，这个 margin 会尽量的大，可以方便的用这个特性来实现元素的居左或者居右，也可以实现居中。

div.tree > div:nth-child(2) {
  width: 50%;
  margin-right: auto;
}
div.tree > div:nth-child(3) {
  width: 50%;
  margin-right: left;
}

其次，在页面的展示中，因为【4】所在的 span 元素总是有一个倒 V 型的背景图片，所以它总是会展示它与其左右子树的连线，即使它并没有右子树，同样的情况也发生在【3】这个结点上，它展示了与其不存在的左子树的连线。

这当然也是不能接受的，要怎么办呢？

如何选择【只有左子树】或者【只有右子树】的树中的 span 元素呢？

比较奇技淫巧的做法是给表示左子树与表示右子树的元素分别加上相应的类，比如 div.tree.left，div.tree.right，然后把 span 元素放在 div 的后面，然后当一颗树只有左子树时，其结构就是这样：

<div>
  <div class="tree left"></div>
  <span></span>
</div>

然后使用 order 属性把 span 调到前面，通过 div.left:first-child + span 选中只有左子树的 span 元素，然后把它的背景图片调整成相应的只有向左方连线的图片即可，右子树也类似。

但这样总感觉怪怪的，而且如果要实现交互功能的话可能会有些问题，毕竟 DOM 顺序不大对劲。

更简单的做法是，如果一颗树只有左子树或者只有右子树，我们给它加上额外的一个类比如 only-has-left，only-has-right，这样就可以很容易的选中不同情况的 span 了：

div.only-has-left > span {
  background-image: url(left-link.png);
}
div.only-has-right > span {
  background-image: url(right-link.png);
}

这样一来，总算离大功告成又进一步了！！！

自动生成二叉树的 HTML 代码

最后，我们不可能手写出上面的 HTML 结构，而是用程序生成出上面的嵌套 HTML 结构：给定一颗树，程序自动构建出上面说到的 HTML 结构，看起来好像很复杂，其实熟悉树的相关算法的话，这个小函数是很好写的：

function tree2html(root) {
  if (root) {
    let onlyLeft  = (root.left && !root.right)
    let onlyRight = (!root.left && root.right)
    let both = root.left && root.right
    let noSubTree = !root.left && !root.right
    return `
      <div class="
        tree 
        ${both?'both':''}
        ${noSubTree?'no-sub-tree':''}
        ${onlyLeft?'only-has-left':''}
        ${onlyRight?'only-has-right':''}
      ">
        <span>${root.val}</span>
        ${tree2html(root.left)}
        ${tree2html(root.right)}
      </div>
    `
  } else {return''}
}

解释一下，我们根据一颗树是否有左子树、右子树、或者两颗子树都有或都没有，来为它加上相应的 class，以方便我们选择其内的 span 元素：

div.only-has-left > span {
  background-image: url(left-link.png);
}
div.only-has-right > span {
  background-image: url(right-link.png);
}

但是，这样并没有大功告成，很多细节上还是不够完美。

小问题比如说，树中各层之间的连线会随着层次的加深而变的更粗（从前面的示图中是可以看出来的），原因也是很明显的，越往下层，展示的空间越小，而背景图片总是被压缩的显示到那个空间中，线就会显得比较粗。

大的问题比如说，如果给定的一颗树非常的不平衡（平衡树的意思就是一颗树的根结点及任意子树的两颗子树的高度之差都不超过 1），那么我们的展示效果也非常差，会一直往一边挤。类似下面这样的效果。而 LeetCode 的展示中，能够很好的适应这种情况。

这两个问题看起来都不太好解决。

先说第一个，使用可能被压缩的图片当做背景图片肯定是行不通了，使用边框或者变幻来模拟我们也不考虑。要是有一张图片设置为背景后不会被压缩，而其中的线条可以按图片大小的百分比显示就好了。

很容易想到使用 SVG 图片来做为背景图片，然后使用 <line/> 标签来生成结点间的连线，然后我写出了如下简单的 SVG 代码：

<svg width="1000"height="200"version="1.1"xmlns="http://www.w3.org/2000/svg">

  <line x1="50%"y1="1.5em"x2="25%"y2="95%"stroke-linecap="round"stroke-linejoin="round"style="stroke:rgb(99,99,99);stroke-width:3"/>
  <line x1="50%"y1="1.5em"x2="75%"y2="95%"stroke-linecap="round"stroke-linejoin="round"style="stroke:rgb(99,99,99);stroke-width:3"/>

</svg>

然后把它展示为 span 元素的背景图片，但是得到的效果并不能让我们满意，线条还是会随着层次的往下而变的粗起来（图就不贴了）。也就是说 SVG 图像还是被拉伸了。

而实际上我们想要的是 SVG 的不位伸大小就与 background-size 所设置的大小一样，盲目的试了几下后我发现好像并不太容易调成功，甚至不确实能否实现我们想要的效果；最终我找到了这个文档：Scaling of SVG backgrounds，里面详细讲述了 SVG 在做背景图片时，其是被变形拉伸还是会让自身尺寸变为 background-size 所设置的大小。情况比较多，我就不在这里解释了，有必要的话各位可以自行阅读该文档。

最终的结果是只要不给 SVG 图片设置明确的宽高，它的大小就将是 background-size 的大小，于是 SVG 图片的源代码如下（与上面的区别就是去掉了 svg 标签的 width 与 height 属性）：

<svg version="1.1"xmlns="http://www.w3.org/2000/svg">

  <line x1="50%"y1="1.5em"x2="25%"y2="95%"stroke-linecap="round"stroke-linejoin="round"style="stroke:rgb(99,99,99);stroke-width:3"/>
  <line x1="50%"y1="1.5em"x2="75%"y2="95%"stroke-linecap="round"stroke-linejoin="round"style="stroke:rgb(99,99,99);stroke-width:3"/>

</svg>

这样一来，解决了不同层级连线粗细不一样的问题，最终的效果就是前面的某张非常对称的截图。

下一个问题，树过于不平衡时的展示问题。

如果某一个结点没有左/右子树，那么按照目前的展示方法，不存的子树还是会占用下方整整一半的空间，最终会导致不平衡的树展示效果较差。

其实这个也不难办，当一个结点只有一颗子树时，让这颗子树占用下方几乎所有的空间就可以了（之所以不是所有的是为了呈现出一种向一边偏的效果），比方说对于一个只有左子树的结点来说，其内部只有表示左子树的 div 结点，让这个结点的宽度为 90% 即可，剩余的 10% 留白，可以简单的使用 margin-right: 10% 来实现（此时 10% 取的也是父元素的内容宽度），其实不写或者写成 auto 也可以。

但这样一来如果继续使用之前的连线，就对不齐了，这个好办，换一种连线就可以了，可以算出，线的起点在上方 50% 处，而终点在下方的 45% 处（即左边 90% 空间的中点），对于只有右子树的情况来说，终点则是在下方 55% 处（右边 90% 空间的中点）。

最终上面那颗非常不平衡的树会展示成如下效果：