用Canvas画一棵二叉树

摘要：如何得到树的深度这样父节点与子结点在轴上最长的距离即为父节点与子结点在轴上最长的距离为正方形的长度，如何确定，假设的宽度为，由深度可知，树的最大宽度为，最底层的正方形占据个。

var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");
// 然后便可以挥毫泼墨了

const root = {
      value: "A",
      label: "100",
      left: {
        value: "B",
        label: "70",
        left: {
          value: "D",
          label: "40",
          left: {
            value: "H",
            label: "20",
            left: null,
            right: null
          },
          right: {
            value: "I",
            label: "20",
            left: null,
            right: null
          }
        },
        right: {
          value: "E",
          label: "30",
          left: null,
          right: null
        }
      },
      right: {
        value: "C",
        label: "30",
        left: {
          value: "F",
          label: "15",
          left: null,
          right: null
        },
        right: {
          value: "G",
          label: "15",
          left: null,
          right: null
        }
      }
    }

这样一幅大作，无非就是由黑色的正方形+线段构成
这正方形怎么画

function drawRect(text, x, y, unit) {
  ctx.fillRect(x, y, unit, unit)
  // fillRect(x, y, width, height) 
  // x与y指定了在canvas画布上所绘制的矩形的左上角（相对于原点）的坐标
  // width和height设置矩形的尺寸。
  ctx.font = "14px serif"
  ctx.fillText(text, x + unit, y + unit) // 再给每个正方形加个名字
}

这直线怎么画

function drawLine(x1, y1, x2, y2) {
  ctx.moveTo(x1, y1)
  ctx.lineTo(x2, y2)
  ctx.stroke()
}

这关系怎么画

// 前序遍历二叉树
function preOrderTraverse(root, x, y){
  drawRect(root.value, x, y)
  if(root.left){
    drawLine(x, y, ...)
    preOrderTraverse(root.left, ...)
  }
  if(root.right){
    drawLine(x, y, ...)
    preOrderTraverse(root.right, ...)
  }
}

现在遇到个小问题，如何确定节点的子节的位置？

父节点与子结点在y轴上的距离固定，为正方形长度unit的两倍；父节点与子结点在x轴上的距离满足n2=(n1+2)*2-2，其中设父节点与子结点在x轴上最短的距离n0=1，即unit，而父节点与子结点在x轴上最长的距离取决于该树的层数。
如何得到树的深度？

function getDeepOfTree(root) {
  if (!root) {
    return 0
  }
  let left = getDeepOfTree(root.left)
  let right = getDeepOfTree(root.right)
  return (left > right) ? left + 1 : right + 1
}

这样父节点与子结点在x轴上最长的距离

let distance = 1
const deep = getDeepOfTree(root)
for (let i = 2; i < deep; i++) {
  distance = (distance + 2) * 2 - 2
}
// distance*unit 即为父节点与子结点在x轴上最长的距离

unit为正方形的长度，如何确定，假设canvas的宽度为1000，由深度deep可知，树的最大宽度为Math.pow(2, deep - 1)，最底层的正方形占据4个unit。

所以unit是如此计算，const unit = 1000 / (Math.pow(2, deep - 1) * 4 + 8)，+8是个备用空间。

实现移动至节点出现tooltip

首先要有tooltip

...
const tooltip = document.getElementById("tooltip")

由于canvas是一个整体元素，所以只能给canvas绑定事件，根据鼠标的坐标，判断是否落在某个正方形区域内
这里有个关健个函数

ctx.rect(0, 0, 100, 100)
ctx.isPointInPath(x, y)
// 判断x，y是否落在刚刚由path绘制出的区域内

所以在绘制正方形时还要将其path记下来

let pathArr = []
function preOrderTraverse(root, x, y, distance) {
  pathArr.push({
    x,
    y,
    value: root.value,
    label: root.label
  })
  // 记录正方形左上角的位置，就可以重绘路径
  drawRect(root.value, x, y) // 绘制节点
  if (root.left) {
    drawLeftLine(x, y + unit, distance)
    preOrderTraverse(root.left, x - (distance + 1) * unit, y + 3 * unit, distance / 2 - 1)
  }
  if (root.right) {
    drawRightLine(x + unit, y + unit, distance)
    preOrderTraverse(root.right, x + (distance + 1) * unit, y + 3 * unit, distance / 2 - 1)
  }
}

绑定事件

// 模拟鼠标hover效果
canvas.addEventListener("mousemove", (e) => {
  let i = 0
  while (i < pathArr.length) {
    ctx.beginPath()
    ctx.rect(pathArr[i].x, pathArr[i].y, unit, unit)
    if (ctx.isPointInPath(e.offsetX, e.offsetY)) {
      canvas.style.cursor = "pointer"
      tooltip.innerHTML = `${pathArr[i].label}`
      tooltip.style.top = `${pathArr[i].y + unit + 4}px`
      tooltip.style.left = `${pathArr[i].x + unit}px`
      break
    } else {
      i++
    }
  }
  if (i === pathArr.length) {
    canvas.style.cursor = "default"
    tooltip.innerHTML = ``
  }
})

JSBin地址