树的布局算法

Feb. 06 2023算法

之前在公司 hackday 中需要渲染一个树形结构的数据，需要对树的布局进行计算，最后当然是使用现成的库。之前开发 regex-vis 也渲染了类似树形结构的数据，因为特定的呈现效果，regex-vis 的图形渲染比较简单，就直接手写了

这两次经历促使我想更深入了解树的布局算法，于是阅读了几篇相关的论文，这里记录一下。下文每个小标题即是论文的标题，关于论文具体可见文末的参考文献

为了便于理解，文中树的每个节点都是边长为单位 1 的正方形

Aesthetic layout of generalized tree

首先，绘制一棵树，我们当然希望它尽可能的美观，那怎样才算美观呢？

这里列出文中提到的 7 条美观要求，我们在下面的布局算法也会对照这 7 条：

兄弟节点的顶部边缘在同一水平线上
按顺序从左到右渲染兄弟节点
父节点在最左子节点和最右子节点的中间
一个树和它的镜像结构树所绘制的图应互为镜像；一个子树无论处在树的哪个位置，都应该是相同的形状
连接节点底部中心和节点顶部中心的边不与其他边或节点交叉
同一级的节点之间至少有 p(p> 0) 的间距
每个节点和它的父节点在垂直方向至少有 q(q>0) 的间距

当然，除了美学的要求，我们还要考虑其他的因素，比如算法生成的图的宽度应尽可能的小，便于展示

由于第一条的存在，计算节点的 y 坐标非常简单，y 坐标只与节点的层级有关，因此接下来的算法主要关注的是如何计算节点的 x 坐标

Tidy drawings of trees

论文中主要提出了三种算法，前两种都比较简单

The First Algorithm

第一种算法的思想是：对于每个节点，x 坐标 = 同级左节点的 x 坐标 + 节点宽度 + 最小水平间距

import { renderMaryTree } from './utils'
import { maryRoot, maryLevel } from './root'
const NODE_WIDTH = 1
const NODE_HEIGHT = 1
const LEVEL_SEPARATION = 1
const SIBLING_SEPARATION = 1

const layout = (root, maxLevel) => {
  const nextPos = new Array(maxLevel).fill(0)
  const walk = (node, level) => {
    const { children = [] } = node
    children.forEach((child) => {
      walk(child, level + 1)
    })
    node.x = nextPos[level]
    node.y = level * (LEVEL_SEPARATION + NODE_HEIGHT)
    nextPos[level] += SIBLING_SEPARATION + NODE_WIDTH
  }
  walk(root, 0)
  return root
}

const laidoutRoot = layout(maryRoot, maryLevel)
export default function APP() {
  return renderMaryTree(laidoutRoot)
}

Open Sandbox

这种算法很简单，当然效果也不会很好，不符合第 3、4 条美观要求，看上去很乱，很难看出树的结构

The Second Algorithm

第二种算法的思想：对于每个节点，x 坐标 = 上个节点的 x 坐标 + 节点宽度 + 最小水平间距

import { renderBinaryTree } from './utils'
import { binaryRoot, binaryLevel } from './root'
const NODE_WIDTH = 1
const NODE_HEIGHT = 1
const LEVEL_SEPARATION = 1
const SIBLING_SEPARATION = 1

const layout = (root) => {
  let nextPos = 0
  const walk = (node, level) => {
    const { left, right } = node
    if (left) {
      walk(left, level + 1)
    }
    node.x = nextPos
    nextPos += NODE_WIDTH + SIBLING_SEPARATION
    node.y = level * (LEVEL_SEPARATION + NODE_HEIGHT)
    if (right) {
      walk(right, level + 1)
    }
  }
  walk(root, 0)
  return root
}

const laidoutRoot = layout(binaryRoot, binaryLevel)
export default function APP() {
  return renderBinaryTree(laidoutRoot)
}

Open Sandbox

从结果可以看出，这种算法虽然比上一种更容易看出树的结构，仍不符合第 3、4 条美观要求。并且这种算法生成的图宽度很大，不便于展示

The Third Algorithm

前两种算法都只用了一次后序遍历，而第三种算法在后序遍历的基础上，再进行了一次前序遍历

import { renderBinaryTree } from './utils'
import { binaryRoot, binaryLevel } from './root'
const NODE_WIDTH = 1
const NODE_HEIGHT = 1
const LEVEL_SEPARATION = 1
const SIBLING_SEPARATION = 1

const layout = (root, maxLevel) => {
  const modifier = new Array(maxLevel).fill(0)
  const nextPos = new Array(maxLevel).fill(0)
  let modifierSum = 0
  const firstWalk = (node, level) => {
    const { left, right } = node
    if (left) {
      firstWalk(left, level + 1)
    }
    if (right) {
      firstWalk(right, level + 1)
    }
    const isLeaf = !left && !right
    let place
    if (isLeaf) {
      place = nextPos[level]
    } else if (!left) {
      place = right.x - (NODE_WIDTH + SIBLING_SEPARATION) / 2
    } else if (!right) {
      place = left.x + (NODE_WIDTH + SIBLING_SEPARATION) / 2
    } else {
      place = (left.x + right.x) / 2
    }
    modifier[level] = Math.max(modifier[level], nextPos[level] - place)
    if (isLeaf) {
      node.x = place
    } else {
      node.x = place + modifier[level]
    }
    nextPos[level] = node.x + NODE_WIDTH + SIBLING_SEPARATION
    node.modifier = modifier[level]
  }

  const secondWalk = (node, level) => {
    const { left, right } = node
    node.x += modifierSum
    modifierSum += node.modifier
    node.y = level * (LEVEL_SEPARATION + NODE_HEIGHT)
    if (left) {
      secondWalk(left, level + 1)
    }
    if (right) {
      secondWalk(right, level + 1)
    }
    modifierSum -= node.modifier
  }

  firstWalk(root, 0)
  secondWalk(root, 0)
  return root
}

const laidoutRoot = layout(binaryRoot, binaryLevel)
export default function APP() {
  return renderBinaryTree(laidoutRoot)
}

Open Sandbox

算法中引入了一个新变量 modifier，这在后面的算法也有用到，modifier 的含义是子树相对于父节点的偏移量。

节点的 modifier = max(同级左节点的 modifier, 同级左节点的 x + 节点宽度 + 最小水平间距 - place)

而对于 place：

如果节点是叶子结点，place = 同级左节点的 x + 节点宽度 + 最小水平间距
如果节点只有右子节点，place = 右子节点的 x - (节点宽度 + 最小水平间距) / 2
如果节点只有左子节点，place = 左子节点的 x + (节点宽度 + 最小水平间距) / 2
如果节点有左右子节点，place = (左子节点的 x + 右子节点的 x) / 2

在最后的前序遍历中，节点最终的 x 坐标 = 后序遍历得到的 x 坐标 + 所有父节点的 modifier 之和

这种算法的效果比前两种算法好很多，但是还是不符合第 4 条美观要求，这里展示了一种情况，可以看出，根节点的左子树和右子树结构上互为镜像，但渲染出的图形却不是镜像的

import { renderBinaryTree } from './utils'
import { tidierRoot, tidierLevel } from './root'
const NODE_WIDTH = 1
const NODE_HEIGHT = 1
const LEVEL_SEPARATION = 1
const SIBLING_SEPARATION = 1

const layout = (root, maxLevel) => {
  const modifier = new Array(maxLevel).fill(0)
  const nextPos = new Array(maxLevel).fill(0)
  let modifierSum = 0
  const firstWalk = (node, level) => {
    const { left, right } = node
    if (left) {
      firstWalk(left, level + 1)
    }
    if (right) {
      firstWalk(right, level + 1)
    }
    const isLeaf = !left && !right
    let place
    if (isLeaf) {
      place = nextPos[level]
    } else if (!left) {
      place = right.x - (NODE_WIDTH + SIBLING_SEPARATION) / 2
    } else if (!right) {
      place = left.x + (NODE_WIDTH + SIBLING_SEPARATION) / 2
    } else {
      place = (left.x + right.x) / 2
    }
    modifier[level] = Math.max(modifier[level], nextPos[level] - place)
    if (isLeaf) {
      node.x = place
    } else {
      node.x = place + modifier[level]
    }
    nextPos[level] = node.x + NODE_WIDTH + SIBLING_SEPARATION
    node.modifier = modifier[level]
  }

  const secondWalk = (node, level) => {
    const { left, right } = node
    node.x += modifierSum
    modifierSum += node.modifier
    node.y = level * (LEVEL_SEPARATION + NODE_HEIGHT)
    if (left) {
      secondWalk(left, level + 1)
    }
    if (right) {
      secondWalk(right, level + 1)
    }
    modifierSum -= node.modifier
  }

  firstWalk(root, 0)
  secondWalk(root, 0)
  return root
}

const laidoutRoot = layout(tidierRoot, tidierLevel)
export default function APP() {
  return renderBinaryTree(laidoutRoot)
}

Open Sandbox

论文中还对第三种算法进行了修改，使生成的图宽度更小，但无论改进与否，都会违反上述的第 4 条要求，所以这里不再赘述

Tidier drawings of trees

很快就有人发现上篇论文算法的不足，提出了一种新的算法，算法同样由后序遍历和前序遍历两部分组成

import { useState } from "react"
import { renderBinaryTree } from './utils'
import { tidierRoot, tidierLevel } from './root'
const NODE_WIDTH = 1
const NODE_HEIGHT = 1
const LEVEL_SEPARATION = 1
const SIBLING_SEPARATION = 1

const layout = (root) => {
  const firstWalk = (node, level, leftmost, rightmost) => {
    let { left, right } = node
    const ll = { addr: null, offset: 0, level: 0 }
    const lr = { addr: null, offset: 0, level: 0 }
    const rl = { addr: null, offset: 0, level: 0 }
    const rr = { addr: null, offset: 0, level: 0 }
    if (left) {
      firstWalk(left, level + 1, ll, lr)
    }
    if (right) {
      firstWalk(right, level + 1, rl, rr)
    }
    node.y = level * (NODE_HEIGHT + LEVEL_SEPARATION)
    // leaf node
    if (!left && !right) {
      leftmost.addr = node
      rightmost.addr = node
      leftmost.level = level
      rightmost.level = level
      leftmost.offset = 0
      rightmost.offset = 0
      node.offset = 0
    } else {
      let curSep = SIBLING_SEPARATION
      let rootSep = SIBLING_SEPARATION
      let leftOffsetSum = 0
      let rightOffsetSum = 0
      while (left && right) {
        if (curSep < SIBLING_SEPARATION) {
          rootSep += SIBLING_SEPARATION - curSep
          curSep = SIBLING_SEPARATION
        }
        if (left.right) {
          leftOffsetSum += left.offset
          curSep -= left.offset
          left = left.right
        } else {
          leftOffsetSum -= left.offset
          curSep += left.offset
          left = left.left
        }
        if (right.left) {
          rightOffsetSum -= right.offset
          curSep -= right.offset
          right = right.left
        } else {
          rightOffsetSum += right.offset
          curSep += right.offset
          right = right.right
        }
      }

      node.offset = (rootSep + NODE_WIDTH) / 2
      leftOffsetSum -= node.offset
      rightOffsetSum += node.offset

      if (rl.level > ll.level || !node.left) {
        leftmost.addr = rl.addr
        leftmost.level = rl.level
        leftmost.offset = rl.offset + node.offset
      } else {
        leftmost.addr = ll.addr
        leftmost.level = ll.level
        leftmost.offset = ll.offset - node.offset
      }
      if (lr.level > rr.level || !node.right) {
        rightmost.addr = lr.addr
        rightmost.level = lr.level
        rightmost.offset = lr.offset - node.offset
      } else {
        rightmost.addr = rr.addr
        rightmost.level = rr.level
        rightmost.offset = rr.offset + node.offset
      }

      if (left && left !== node.left) {
        rr.addr.thread = true
        rr.addr.offset = Math.abs(rr.offset + node.offset - rightOffsetSum)
        if (leftOffsetSum - node.offset <= rr.offset) {
          rr.addr.left = left
        } else {
          rr.addr.right = left
        }
      } else if (right && right !== node.right) {
        ll.addr.thread = true
        ll.addr.offset = Math.abs(ll.offset - node.offset - rightOffsetSum)
        if (rightOffsetSum + node.offset >= ll.offset) {
          ll.addr.right = right
        } else {
          ll.addr.left = right
        }
      }
    }
  }

  const secondWalk = (node, x) => {
    node.x = x
    if (node.thread) {
      return
    }
    const { left, right } = node
    if (left) {
      secondWalk(left, x - node.offset)
    }
    if (right) {
      secondWalk(right, x + node.offset)
    }
  }
  firstWalk(
    root,
    0,
    { addr: null, offset: 0, level: 0 },
    { addr: null, offset: 0, level: 0 }
  )
  secondWalk(root, 0)
  return root
}

const laidoutRoot = layout(tidierRoot, tidierLevel)
export default function APP() {
  return renderBinaryTree(laidoutRoot)
}

Open Sandbox

因为需要满足父节点在左右子节点的正中间，算法为每个节点定义了变量 offset，左子节点 x = 父节点 x - offset，右子节点 x = 父节点 x + offset

为了保证各个节点的左子树和右子树不重叠，我们需要对比左子树的右轮廓和右子树的左轮廓，这里就需要对二叉树进行线索化。

对于每个节点，如果它的左子树和右子树均存在，并且左子树比右子树高，那么就在右子树的最底层的最右侧节点上添加一个线索，指向左子树的下一层的最右侧节点

如上图，实线为正常连接父节点和子节点的边，而虚线代表则是线索边。

打个比方，我们要对比根节点 s 的左右子树

在第 2 级，我们对比节点 s 的左子节点 i 和节点 s 的右子节点 r；
在第 3 级，我们对比节点 i 的右子节点 h 和节点 r 的左子节点 j；
在第 4 级，因为节点 h 和节点 j 都是叶子节点，无法再深入对比，需要返回第 2 级，从 i 的左子节点和 r 的右子节点再开始，这样无疑会提升时间复杂度；而在将二叉树线索化后，节点 h 可以直接找到下一级的右轮廓即节点 f

A node-positioning algorithm for general trees

上面的算法对于二叉树来说，已经可以满足开头提到的 7 条美学要求，这篇论文则是将其拓展为一般树，即树的每个节点可以有多个子节点

import { maryRoot, maryLevel } from './root'
import { renderMaryTree } from './utils'
const NODE_WIDTH = 1
const NODE_HEIGHT = 1
const LEVEL_SEPARATION = 1
const SIBLING_SEPARATION = 1

const isLeaf = (node) => !node.children || node.children.length === 0

const hasLeftSibling = (node) => node.parent?.children.indexOf(node) > 0

const hasRightSibling = (node) =>
  node.parent.children.indexOf(node) < node.parent.children.length - 1

const getLeftSibling = (node) =>
  node.parent.children[node.parent.children.indexOf(node) - 1]

const getRightSibling = (node) =>
  node.parent.children[node.parent.children.indexOf(node) + 1]

const getLeftNeighbor = (node) => node.neighbor

const getLeftmost = (node, level, depth) => {
  if (level >= depth) {
    return node
  } else if (isLeaf(node)) {
    return null
  } else {
    let rightmost = node.children[0]
    let leftmost = getLeftmost(rightmost, level + 1, depth)
    while (!leftmost && hasRightSibling(rightmost)) {
      rightmost = getRightSibling(rightmost)
      leftmost = getLeftmost(rightmost, level + 1, depth)
    }
    return leftmost
  }
}

const layout = (root) => {
  const neighbors = []
  let maxDepth = 0

  const apportion = (node, level) => {
    let leftmost = node.children[0]
    let neighbor = getLeftNeighbor(leftmost)
    if (!neighbor) {
      return
    }
    let compareDepth = 1
    const depthToStop = maxDepth - level
    while (leftmost && neighbor && compareDepth <= depthToStop) {
      let leftModSum = 0
      let rightModSum = 0
      let ancestorLeftmost = leftmost
      let ancestorNeighbor = neighbor
      for (let i = 0; i < compareDepth; i++) {
        ancestorLeftmost = ancestorLeftmost.parent
        ancestorNeighbor = ancestorNeighbor.parent
        rightModSum += ancestorLeftmost.modifier
        leftModSum += ancestorNeighbor.modifier
      }
      let moveDistance =
        neighbor.prelim +
        leftModSum +
        SIBLING_SEPARATION +
        NODE_WIDTH -
        (leftmost.prelim + rightModSum)
      if (moveDistance > 0) {
        let tempPtr = node
        let leftSiblings = 0
        while (tempPtr && tempPtr !== ancestorNeighbor) {
          leftSiblings++
          tempPtr = getLeftSibling(tempPtr)
        }
        if (tempPtr) {
          const portion = moveDistance / leftSiblings
          tempPtr = node
          while (tempPtr !== ancestorNeighbor) {
            tempPtr.prelim += moveDistance
            tempPtr.modifier += moveDistance
            moveDistance -= portion
            tempPtr = getLeftSibling(tempPtr)
          }
        } else {
          return
        }
      }

      compareDepth++
      if (isLeaf(leftmost)) {
        leftmost = getLeftmost(node, 0, compareDepth)
      } else {
        leftmost = leftmost.children[0]
      }
      if (leftmost) {
        neighbor = getLeftNeighbor(leftmost)
      }
    }
  }

  const firstWalk = (node, level) => {
    node.neighbor = neighbors[level]
    neighbors[level] = node
    node.modifier = 0
    maxDepth = Math.max(level, maxDepth)

    if (isLeaf(node)) {
      if (hasLeftSibling(node)) {
        node.prelim =
          getLeftSibling(node).prelim + SIBLING_SEPARATION + NODE_WIDTH
      } else {
        node.prelim = 0
      }
    } else {
      const { children = [] } = node
      const leftmost = children[0]
      const rightmost = children[children.length - 1]
      children.forEach((child) => {
        child.parent = node
        firstWalk(child, level + 1)
      })
      const midPoint = (leftmost.prelim + rightmost.prelim) / 2
      if (hasLeftSibling(node)) {
        const leftSibling = getLeftSibling(node)
        node.prelim = leftSibling.prelim + SIBLING_SEPARATION + NODE_WIDTH
        node.modifier = node.prelim - midPoint
        apportion(node, level)
      } else {
        node.prelim = midPoint
      }
    }
  }

  const secondWalk = (node, level, modSum) => {
    node.x = node.prelim + modSum
    node.y = level * (LEVEL_SEPARATION + NODE_HEIGHT)
    node.children?.forEach((child) =>
      secondWalk(child, level + 1, modSum + node.modifier)
    )
  }

  firstWalk(root, 0)
  secondWalk(root, 0, 0)
  return root
}

const laidoutRoot = layout(maryRoot, maryLevel)
export default function App() {
  return renderMaryTree(laidoutRoot)
}

Open Sandbox

有了前几条算法，这个算法的思路不难理解，这里讲一下算法几个特殊的点：

算法中 prelim 是指第一次遍历后 x 坐标的值；modifier 与之前的算法相同，是子树相对于父节点的偏移量
在拓展为一般树后，会有一个问题：较大子树之间的小子树们会比较靠左。所以在后面需要重新调整一下
这里的遍历子树轮廓时，没有使用线索树，而是采用了时间复杂度高的方法，这点会在下篇论文中优化

Improving Walker’s algorithm to run in linear time

上篇论文中的算法渲染出的图形已经打到目标了，但是算法的时间复杂度并不是最优的，这篇论文会在几个地方优化，最终实现线性的时间复杂度

Traversing the coutours

遍历子树轮廓时可以使用 Tidier drawings of trees 中提到的线索树，具体可以看上文

Finding the ancestors

这部分我看得不是很懂。后面可能会补充

Counting the smaller subtrees

要计算同一父节点下两个子节点之间需要移动的树的数量，可以在遍历时记住每个节点在父节点 children 中的 index，计算时，用右侧节点的 index 减去左侧节点的 index 即可

Shifting the smaller subtrees

移动两个子节点的小子树时，不需要遍历所有小子树，如下面的代码所示

const moveSubTree = (leftNode, rightNode, shift) => {
  // 先是用 index(num) 计算出 subtrees，即需要移动的子树的数量；
  const subtrees = rightNode.num - leftNode.num
  rightNode.change -= shift / subtrees
  rightNode.shift += shift
  // 最右侧节点的 prelim 需要增加 shift，即是将最右侧节点向右移动 shift
  rightNode.prelim += shift
  // 最右侧节点的 mod 需要增加 shift，即是将最右侧节点的子树向右移动 shift
  rightNode.mod += shift
  leftNode.change += shift / subtrees
}

在所有孩子节点都移动完毕后，再统一利用节点的 shift 和 change 值，修改节点的 prelim 和 mod 值：

const executeShifts = (node) => {
  let shift = 0
  let change = 0
  const { children = [] } = node
  for (let i = children.length - 1; i >= 0; i--) {
    const child = children[i]
    child.prelim += shift
    child.mod += shift
    change += child.change
    shift += child.shift + change
  }
}

因为在 moveSubTree 中 rightNode 的 prelim 和 mod 都增加了 shift，所以也不会影响后续节点的 leftSibling 节点位置

下面是 executeShifts 的一个示例：

node	a	b	c	d	e	f
node.shift	0	0	0	1	0	1
node.change	1/3 + 1/5	0	0	-1/3	0	-1/5
prelim diff	0	1/5 + 1/3	2/5 + 2/3	3/5	4/5	0
mod diff	0	1/5 + 1/3	2/5 + 2/3	3/5	4/5	0
shift	0	0	1/5+1/3	2/5+2/3	3/5	4/5
change	0	-1/5-1/3	-1/5-1/3	-1/5-1/3	-1/5	-1/5

可以看出各个节点的 prelim 和 mod 都正确地修改了。rightNode 的 prelim 和 mod 在 moveSubTree 函数中已经修改过了，所以在上表没有体现

下面是最终的布局算法和渲染效果：

import { maryRoot, maryLevel } from './root'
import { renderMaryTree } from './utils'
const NODE_WIDTH = 1
const NODE_HEIGHT = 1
const LEVEL_SEPARATION = 1
const SIBLING_SEPARATION = 1

const getLeftmost = (node) => node.children?.[0] ?? node.thread
const getRightmost = (node) =>
  node.children?.[node.children.length - 1] ?? node.thread

const getPreviousSibling = (node) => node.previousSibling

const getAncestor = (leftTreeRightmost, node, defaultAncestor) =>
  node.parent === leftTreeRightmost.ancestor?.parent
    ? leftTreeRightmost.ancestor
    : defaultAncestor

const moveSubTree = (ancestor, node, shift) => {
  const subtrees = node.num - ancestor.num
  node.change -= shift / subtrees
  node.shift += shift
  node.prelim += shift
  node.mod += shift
  ancestor.change += shift / subtrees
}

const apportion = (node, defaultAncestor) => {
  const sibling = getPreviousSibling(node)
  if (sibling) {
    let rightTreeLeftmost = node
    let rightTreeRightmost = node
    let leftTreeRightmost = sibling
    let parentFirstChildLeftmost = node.parent?.children[0]

    let rightTreeLeftmostModSum = rightTreeLeftmost.mod
    let rightTreeRightmostModSum = rightTreeRightmost.mod
    let leftTreeRightmostModSum = leftTreeRightmost.mod
    let parentFirstChildLeftmostModSum = parentFirstChildLeftmost.mod

    let nextRightmost = getRightmost(leftTreeRightmost)
    let nextLeftmost = getLeftmost(rightTreeLeftmost)

    while (nextRightmost && nextLeftmost) {
      leftTreeRightmost = nextRightmost
      rightTreeLeftmost = nextLeftmost
      parentFirstChildLeftmost = getLeftmost(parentFirstChildLeftmost)
      rightTreeRightmost = getRightmost(rightTreeRightmost)

      rightTreeRightmost.ancestor = node
      const shift =
        leftTreeRightmost.prelim +
        leftTreeRightmostModSum -
        (rightTreeLeftmost.prelim + rightTreeLeftmostModSum) +
        SIBLING_SEPARATION +
        NODE_WIDTH
      if (shift > 0) {
        moveSubTree(
          getAncestor(leftTreeRightmost, node, defaultAncestor),
          node,
          shift
        )
        rightTreeLeftmostModSum += shift
        rightTreeRightmostModSum += shift
      }
      rightTreeLeftmostModSum += rightTreeLeftmost.mod
      rightTreeRightmostModSum += rightTreeRightmost.mod
      parentFirstChildLeftmostModSum += parentFirstChildLeftmost.mod
      leftTreeRightmostModSum += leftTreeRightmost.mod

      nextRightmost = getRightmost(leftTreeRightmost)
      nextLeftmost = getLeftmost(rightTreeLeftmost)
    }

    if (nextRightmost && !getRightmost(rightTreeRightmost)) {
      rightTreeRightmost.thread = nextRightmost
      rightTreeRightmost.mod +=
        leftTreeRightmostModSum - rightTreeRightmostModSum
    }
    if (nextLeftmost && !getLeftmost(parentFirstChildLeftmost)) {
      parentFirstChildLeftmost.thread = nextLeftmost
      parentFirstChildLeftmost.mod +=
        rightTreeLeftmostModSum - parentFirstChildLeftmostModSum
      defaultAncestor = node
    }
  }
  return defaultAncestor
}

const executeShifts = (node) => {
  let shift = 0
  let change = 0
  const { children = [] } = node
  for (let i = children.length - 1; i >= 0; i--) {
    const child = children[i]
    child.prelim += shift
    child.mod += shift
    change += child.change
    shift += child.shift + change
  }
}

const firstWalk = (node) => {
  const { children = [], previousSibling } = node
  node.prelim = 0
  node.mod = 0
  node.change = 0
  node.shift = 0

  if (children.length > 0) {
    let defaultAncestor = children[0]
    children.forEach((child, index) => {
      child.num = index
      child.parent = node
      if (index > 0) {
        child.previousSibling = children[index - 1]
      }
      firstWalk(child)
      defaultAncestor = apportion(child, defaultAncestor)
    })
    executeShifts(node)
    const leftmost = children[0]
    const rightmost = children[children.length - 1]
    const midpoint = (leftmost.prelim + rightmost.prelim) / 2
    if (previousSibling) {
      node.prelim = previousSibling.prelim + SIBLING_SEPARATION + NODE_WIDTH
      node.mod = node.prelim - midpoint
    } else {
      node.prelim = midpoint
    }
  } else {
    if (previousSibling) {
      node.prelim = previousSibling.prelim + SIBLING_SEPARATION + NODE_WIDTH
    }
  }
}

const secondWalk = (node, mod, level) => {
  node.x = node.prelim + mod
  node.y = level * (LEVEL_SEPARATION + NODE_HEIGHT)
  node.children?.forEach((child) =>
    secondWalk(child, mod + node.mod, level + 1)
  )
}

const layout = (root) => {
  firstWalk(root)
  secondWalk(root, 0, 0)
  return root
}

const laidoutRoot = layout(maryRoot, maryLevel)
export default function App() {
  return renderMaryTree(laidoutRoot)
}

Open Sandbox

参考文献 & 资料

Bloesch A. Aesthetic layout of generalized trees[J]. Software: Practice and Experience, 1993, 23(8): 817-827.
Wetherell C, Shannon A. Tidy drawings of trees[J]. IEEE Transactions on software Engineering, 1979 (5): 514-520.
Reingold E M, Tilford J S. Tidier drawings of trees[J]. IEEE Transactions on software Engineering, 1981 (2): 223-228.
Walker J Q. A node‐positioning algorithm for general trees[J]. Software: Practice and Experience, 1990, 20(7): 685-705.
Buchheim C, Jünger M, Leipert S. Improving Walker’s algorithm to run in linear time[C]//Graph Drawing: 10th International Symposium, GD 2002 Irvine, CA, USA, August 26–28, 2002 Revised Papers 10. Springer Berlin Heidelberg, 2002: 344-353.
https://rachel53461.wordpress.com/2014/04/20/algorithm-for-drawing-trees/
https://github.com/prefuse/Prefuse
https://github.com/cvzi/py_treedraw