三指针 · 五种给行策略

分支树的网格布局

一棵树用 first-child / next-sibling / parent 三指针存储，绘制时摊到整数网格 $(col, row)$ 上：列号 $col$ 恒等于节点到根的距离，布局要决定的只有行号。五个策略各自实现同一个函数 findAvailableRow(col, preferredRow, node, parent)，公共骨架负责深度优先递归与占位登记。树形状由一小段脚本写成，画布上的树也能反过来导出成脚本。

1 · 三指针模型与网格坐标

节点持有 first（首子）、next（下一兄弟）、parent 三个指针，外加两项冗余：last 指向末子，depth 存以本节点为根的子树高度。last 只为让追加子节点是常数时间。没有它，每次追加都要从 first 顺 next 走到链尾，建一条 $n$ 元长链就退化成 $O(n^2)$ 。depth 由追加操作沿祖先链向上增量维护，相等即停：高度没变就不必继续上溯。

插入的语义固定为「作为当前选中节点的子节点追加，并把选中移到新节点」。连续插入长出一条链，中途改选中就长出分支。脚本 DSL 的执行模型与此相同。

图 1-1 · 分支树画布。可拖动平移、按住 ctrl 或 cmd 滚轮缩放，单击节点选中它并高亮它的祖先链与首子链，切换布局策略看同一棵树的行号如何重排，展开脚本面板改写树形状。

注 · 树是普通对象图，没有包进 Vue 的响应式代理。上千个节点各自带四个互指指针，包成 Proxy 后每次遍历都在穿代理层，且指针成环。改动后手动递增一个计数器让派生 computed 失效，是这份实现里唯一的响应式入口。

2 · 五种给行策略

basic 从 preferredRow 起向下找第一个空行，preferredRow 由骨架给出：首子取父节点所在行，其后每个兄弟取前一个兄弟的行加一。compact 一律从第 0 行起找，每列尽量填满。max 让兄弟节点让开前一个兄弟的整棵子树，任意两棵兄弟子树的行区间不相交。balanced 在 preferredRow 附近上下交替试 $\pm 1$ 到 $\pm 4$ ，取第一个既空闲又不与已放置的边交叉的行。

leveled 做前瞻：节点的子树高度 depth 已知，它的后代最多铺到 $col + depth$ 列。先取这段列区间里已用的最大行 $r$ 及其所在列 $c$ ，令起始行不小于 $r + 1 - (c - col)$ ，即按列距回折，相当于假设这条链会斜着往下走。落定前再逐行验证斜线上每一格都空。

图 2-1 · 同一棵树的五种布局并排，右上角标出各自占用的行数与列数，最高者标红。可切换四种树形状：多重分支、同一节点岔出四条、逐级右下的阶梯、一条长链。

compact 的高度必然是理论下界，即最拥挤那一列的节点数减一，代价是父子行差可以任意大，边被拉得很长。max 的高度最大，换来子树互不交错。示例那棵 37 节点的树上，compact 与 leveled 同为 5 行，max 要 8 行。

警示 · balanced 的交叉判据在这棵树上从未触发：它与 basic 的输出逐格相同。原因是候选行的首选与 basic 同为 preferredRow，而只要没有节点被放到父节点上方，同列的边就全是「平或向下」，反向包夹的条件无从满足。实测 40 节点、35% 分叉概率的随机树 300 棵，两者全同，且无一例上行放置；加密到 200 节点、60% 分叉后 205 棵出现差异，「有差异」与「出现上行放置」逐棵同现。判据本身没错，是触发它的前提在稀疏树上不出现。

前瞻还有一处名实不符：它验证的是从 $(col, row)$ 起的一条斜线，而首子实际取的 preferredRow 是父节点所在行，链保持水平的情形占多数。示例树的根节点 depth 为 13，落定前检查了 14 格斜线，而它那条链最终整条躺在第 0 行。被检查的格子与被占用的格子不是同一批，多出来的检查只会把节点推得更低；在这棵树上没有推低（leveled 与 compact 同高），但这是巧合而非保证。

3 · 分支配色的两档口径

一串没有分叉的节点应当同色，视觉上读作一条分支。配色键取「本节点所在独子链的链头 id」：从本节点往上走，直到父节点不再只有一个子节点为止。

判据必须落在 parent 身上。另一种写法是从本节点起，遇到「有且仅有一个子节点」的节点就记下，直到遇到分叉点才停；这样会漏掉叶子。叶子自身没有子节点，不满足记录条件，于是径直越过头上的分叉点，拿到主干那条链的键。表现是单节点分支的圆圈染成主干色，而它的边不受影响，因为边另有一档口径。

边的着色分两档：分叉点引出的边取分叉点自己的 linkColor，其余取所在独子链的配色键。缺了第一档，同一分叉引出的几条边会各染成目标链的颜色，分叉点本身反倒读不出来。两档口径不同，上面那个漏洞才会让一条边与它连着的节点颜色对不上。示例脚本里的 branch: 7, E -> 8 就是这样一条单节点分支。

4 · 视口裁剪

节点数可达数千，全量画进 SVG 会让每次拖动都重排几千个元素。画布不改 SVG 的 viewBox，而是给内层 <g> 挂 translate 与 scale，视口是纯数据：把屏幕四角反算回世界坐标得到一个矩形，只有落在矩形内的节点与边进 DOM。图 1-1 的读数里「进 DOM 的节点」与「树上共」两个数字即此。

裁剪边界额外放宽一圈：快速拖动时一帧可能跨过几十像素，边界贴太紧会看到节点在边缘一个个长出来。放宽量取节点半径的八倍与 200 像素中的较大者。

平移用 Pointer Events 加 setPointerCapture，指针拖出画布也不丢事件。滚轮缩放只在按住 ctrl 或 cmd 时生效，触控板的双指捏合正是这种事件。裸滚轮一律让给页面：画布嵌在正文里，吞掉滚轮会让读者滑到此处就卡住。原实现无条件 preventDefault，那是整页应用的写法，嵌进文章就不合适了。

5 · 脚本 DSL 与往返

树形状写成几行文本，main 给主干编号区间，branch 从某个基点引出一条新链：

main: 0, 12
branch: 7, A -> 8, 12
branch: A, 9, B -> 10, 14

编号是显示值而非节点 id：它表达该节点在自己那条链上的层号，同层的分支节点与主干节点编号相同，读起来像版本号。语法不成立的行整行跳过而不报错，因为编辑器里逐字敲出的中间状态占绝大多数；引用了不存在的基点才抛错，由画布转成可见提示。多段 main 会接在编号相邻的已有主干节点之后，能分段续写而不是各自另起一棵树。

反向是 treeToScript：分支头即「不是父节点首子的节点」，按 id 顺序重新分配成从 A 起的字母键。节点 id 单调递增，id 顺序即创建顺序，键的分配因此稳定。原实现另存了一个 createdAt: Date.now() 用来排序，而一次脚本执行里全部节点同在一个毫秒内创建，时间戳全相等。排序结果实际由 Array.prototype.sort 的稳定性和 Map 的插入序兜住，换个不稳定的排序就会变。改成比 id 后这层隐含依赖消失。