使用javascript+canvas显示二叉树

1  创建二叉树节点类

首先，需要一个TreeNode类表示二叉树节点：

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

2. 生成二叉树

lass FullBinaryTree {
  constructor(level) {
    const _Root = this.getFullBinaryTree(level);
    this.getRoot = () => {
      return _Root;
    };
  }
  getFullBinaryTree(level) {
    let index = 0;
    function fullTree(n) {
      if (n === 0) return null;
      let root = new TreeNode(index++);
      root.left = fullTree((n - 1) / 2);
      root.right = fullTree((n - 1) / 2);
      return root;
    }
    // 2的level次方 -1 = 总节点数
    return fullTree(Math.pow(2, level) - 1);
  }
}

3.  计算二叉树深度

const getTreeDepth = (root) => {
  				let depth = 0; // 当前深度
  				let max = 0; // 当前最大深度
  				const solve = (node) => {
    			if (!node) {
      				if (depth >= max) {
        					max = depth;
     				}
      				return 0;
    			}
    			depth++;
    			solve(node.left);
    			solve(node.right);
    			depth--; // 回到当前节点，深度减回来
    			return max;
  				};
  			return solve(root);
		}

4   Canvas 渲染器

//render
		class CanvasRender {
  			constructor(container) {
    			this.canvas = document.createElement('canvas');
    			this.container = container;
    			this.ctx = this.canvas.getContext('2d');
  			}
  			initSize(w, h) {
    			this.canvas.width = w;
    			this.canvas.height = h;
    			this.container.appendChild(this.canvas);
 			}
  			setStyle(ctx) {
    			ctx.font = "20px serif";
    			ctx.textAlign = "center";
    			ctx.textBaseline = "middle";
  			}
  			renderNode(x, y, r, text) {
  				this.ctx.strokeStyle="#000000"
  				this.ctx.fillStyle='#ff00ff'
    			this.ctx.beginPath();
    			this.ctx.arc(x, y, r, 0, Math.PI * 2); // 绘制圆
    			this.ctx.stroke();
    			this.setStyle(this.ctx); // 设置样式
    			this.ctx.fillText(text, x, y); // 填充节点的value
  			}
  			renderLine(x1, y1, x2, y2) {
    			this.ctx.moveTo(x1, y1);
    			this.ctx.lineTo(x2, y2);
    			this.ctx.stroke();
  			}
		}

5   树的绘制器

树的绘制器使用draw绘制二叉树的节点drawNode和连线linkNode。

//drawer
		class TreeDrawer {
 			constructor(render) {
    			this.render = render;
  			}

 		    layout(root, nodeW, nodeH) {
    			function computeWidth(root) {
      				if (!root) return 0;
      				if (!(root.left || root.right)) {
        				root.width = nodeW;
        				return root.width;
      				}
      				root.width = computeWidth(root.left) + computeWidth(root.right) + nodeW;
      				return root.width;
    				}
    				function computePosition(root, left, right, curY = nodeH) {
      					if (!root) return;
      				let x;
      				if (root.left) {
        			x = left + root.left.width + nodeW;
      				} else {
        			x = left + nodeW;
      				}
      				root.position = [x, curY];
      				computePosition(root.left, left, x, curY + nodeH);
      				computePosition(root.right, x, right, curY + nodeH);
    			}
    			computeWidth(root);
    			computePosition(root, 0, root.width);
    			return root.width;
  			}
  			

  			draw(root, nodeW = 40, nodeH = 40) {
    			let depth = getTreeDepth(root); // 获取深度
    			let width = this.layout(root, nodeW, nodeH);// canvas宽度
    			let height = depth * nodeH + nodeH; 
    			// canvas高度
    			this.render.initSize(width + nodeW, height);
    			
    			const getVector = (x, y, x1, y1) => {
      			let dis = Math.sqrt((x - x1) ** 2 + (y - y1) ** 2);
      			return [
        			(x1 - x) / dis,
        			(y1 - y) / dis
      				]
    			}
    			const linkNode = (root, child) => {
      			let [px, py] = root.position;
      			let [cx, cy] = child.position;
      			let [dx, dy] = getVector(px, py, cx, cy);
      			this.render.renderLine(px + (nodeW / 2) * dx, py + (nodeW / 2) * dy,
        		cx - (nodeW / 2) * dx, cy - (nodeW / 2) * dy)
    			}
    			
    			const drawNode = (root) => {
      				let [x, y] = root.position;
      				this.render.renderNode(x, y, nodeW / 2, root.val);
    			}
    			      
    		function draw(root) {
      			if (!root) return;
     			drawNode(root);
     			if (root.left) linkNode(root, root.left);
      			if (root.right) linkNode(root, root.right);
      			draw(root.left);
      			draw(root.right);
    		}
    		draw(root);
  			} 			                                                                       
		}

6   使用示例

// 创建一个深度为3的二叉树
const root = new FullBinaryTree(4).getRoot();
// 创建Canvas渲染器
const render = new CanvasRender(document.body);
// 创建树的绘制器
const drawer = new TreeDrawer(render);
// 绘制二叉树
drawer.draw(root);
		

此示例创建一个深度为3 的完全二叉树，并使用canvas将其绘制 。