二维直角坐标系下的树布局

const treeNode = {
  label: 'root',
  children: [
    // other tree nodes
  ]
}

class TreeNode {
  constructor(data, options) {
    this.data = data; // stores the orginal data
	// gets id, width, height, depth, x, y, children, etc.
  }
  isRoot(){}
  isLeaf(){}
  eachNode(callback){} // 可以是简单的递归实现
  DFTraverse(callback){} // 利用堆栈实现深度优先遍历
  BFTraverse(callback){} // 利用队列实现广度优先遍历
  getBoundingBox(){}
  translate(){}
  right2left(){} // 往右布局的树做 x 轴的镜像翻转
  bottom2top(){} // 向下布局的树做 y 轴的镜像翻转
}
function hierarchy(data, options, isolated) {
  const root = new TreeNode(data, options);
  const nodes = [ root ];
  let node;
  if (!isolated) {
    while (node = nodes.pop()) {
      const children = options.getChildren(node.data);
	  for (let i = 0; i < children.length; i ++) {
        const child = new TreeNode(children[i], options);
	    node.children.push(child);
	    child.parent = node;
	    child.depth = node.depth + 1;
	  }
    }
  }
}

function indentedLayout(roo, indent) {
  let previousNode = null;
  root.DFTraverse(node => {
    node.x += indent * node.depth;
	  node.y = previousNode ? previousNode.y + previousNode.height : 0;
	  previousNode = node;
  });
}

function xmindLayout(data, options) {
  const {left, right} = separateRoot(data, options); // 分离左右子树
  nonLayeredUntidyLayout(left);
  nonLayeredUntidyLayout(right);
  left.right2left();
  const root = combineSubTrees(left, right);
  // 思路：left 的根节点调用 translate 使得坐标和 right 的根节点一致
  return root;
}

function separateRoot(data, options) { // 分离左右树
  const left = new TreeNode(data, options, true);
  const right = new TreeNode(data, options, true);
  const root = new TreeNode(data, options);
  for (let child in root.children) {
    const side = options.getSide(child.data);
	if (side === 'left') left.children.push(child);
	if (side === 'right') right.children.push(child);
  }
  return {left, right};
}

function calcTotalHeight(node) { // 统计子树 y 轴占高
  if (node.isLeaf()) return node.totalHeight = node.height;
  let totalHeight = 0;
  node.children.forEach(c => { totalHeight += calcTotalHeight(c); });
  return node.totalHeight = Math.max(node.height, totalHeight);
}

function nonLayeredUntidyLayout(root) { // 非分层非紧凑树布局（水平向右）
  // first walk: x
  root.BFTraverse(node => {
    node.x = node.parent.x + node.parent.width;
  });
  // y
  // second walk
  calcTotalHeight(root);
  // third walk: 根据子树 y 轴占高（totalHeight）分配 y 坐标，逻辑和缩进树类似，不再赘述
  separateSubTreeYCoord(root);
}

function adjustAncestor(node) {
  if (node.isLeaf()) return;
  node.children.forEach(adjustAncestor);
  node.y = (node.children[0].y + node.children[node.children.length - 1].y) / 2
}

// 这里以水平向右为例
function nonLayeredTidyTree(root) {
  getX(root);
  const wt = WrappedTree.fromTreeNode(root);
  firstWalk(wt);
  secondWalk(wt, 0);
}

function getX(node, d = 0) {
  // 作为紧凑布局，x 坐标是可以通过层级和节点宽度直接获取的
  node.x = d;
  d += node.width;
  node.children.forEach(child => {
    getX(child, d);
  }
}

function WrappedTree(h = 0, w = 0, x = 0, c = []) {
  const me = this;
  me.w = w; me.h = h; // size
  me.x = x; me.y = 0; // coord
  me.c = c; me.cs = c.length; // children
  me.prelim = 0; me.mod = 0; me.shift = 0; me.change = 0; // modified
  me.tl = me.tr = null; // left/right tree
  me.el = me.er = null; // extreme left/right tree
  me.msel = me.mser = 0; // modified count of extreme left/right tree
}
WrappedTree.fromTreeNode = root => {
  const children = [];
  root.children.forEach(child => {
    children.push(WrappedTree.fromTreeNode(child);
  }
  return new WrappedTree(root.height, root.width, root.x, children);
}

function firstWalk(wt) {
  // 预处理
  if (wt.cs === 0) return setExtremes(wt);
  firstWalk(wt.c[0]);
  let ih = updateIYL(bottom(wt.c[0].el), 0, null);
  for (let i = 1; i < wt.cs; ++i) {
    firstWalk(wt.c[i]);
    const min = bottom(wt.c[i].er);
    separate(wt, i, ih); // 根据轮廓分离子树
    ih = updateIYL(min, i, ih);
  }
  positionRoot(wt); // 更新子树根节点的位置
  setExtremes(wt); // 更新子树极端位置节点
}

function updateIYL(low, index, ih) {
  // 这个函数是关键，维护一个相邻子树最右侧轮廓的节点的链表
  // 这样每次移动节点的时候，可以从这个链表以 `O(1)` 复杂度获取垂直边界
  while (ih !== null && low >= ih.low) ih = ih.nxt;
  return { low, index, nxt: ih };
}

function secondWalk(wt, modsum) {
  // 根据预处理结果计算 y 坐标
  modsum += wt.mod;
  wt.y = wt.prelim + modesum;
  addChildSpacing(wt);
  for (c in t.c) secondWalk(c, modsum);
}

function WrappedTree(tn, h = 0, c = []) {
  const me = this;
  me.x = me.y = 0;
  me.lc = me.rc = null;
  me.h = h;
  me.c = c;
  me.isLeaf = tn.isLeaf();
}

function dendrogramLayout(root, options) {
  const wt = WrappedTree.fromTreeNode(root); // 类似上一个算法
  getDrawingDepth(wt);
  position(wt, options, null);
}

function getDrawingDepth(t) {
  if (t.isLeaf) {
    t.drawingDepth = MAX_DEPTH;
  } else {
    const depths = t.c.map(child => getDrawingDepth(child));
    const minChildDepth = Math.min.apply(null, depths);
    t.drawingDepth = minChildDepth - 1;
  }
  return t.drawingDepth;
}

function position(t, options, prevLeaf) {
  t.x = t.drawingDepth * options.rankSep; // 横坐标由“绘制深度”和深度间隔决定
  if (t.isLeaf) {
    t.y = 0;
    if (prevLeaf) {
      t.y = prevLeaf.y + prevLeaf.height + options.nodeSep; // 叶子节点从上而下排布
    }
    prevLeaf = t;
  } else {
    t.c.forEach(child => {
      position(child, options, prevLeaf);
    });
    t.y = (t.lc.y + t.rc.y) / 2; // 父节点纵坐标为所有子节点的纵坐标中间
  }
}

class HierarchyNode {
  // the box model of the Node
  // https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_Box_Model/Introduction_to_the_CSS_box_model
  // simplified boxing model, do not differ paddingLeft and paddingRight, etc
  x = 0;
  y = 0;
  // margin
  marginX = 0;
  marginY = 0;
  // border
  borderSize = 0;
  // padding
  paddingX = 0;
  paddingY = 0;
  // size
  width = 0;
  height = 0;

  // width === contentWidth === clientWidth - 2 * paddingX === offsetWidth - 2 * borderSize === outerWidth - 2 * marginX
  get contentHeight() { return this.height; }
  get contentWidth() { return this.width; }
  get clientHeight() { return this.height + 2 * this.paddingY; }
  get clientWidth() { return this.width + 2 * this.paddingX; }
  get offsetHeight() { return this.clientHeight + 2 * this.borderSize; }
  get offsetWidth() { return this.clientWidth + 2 * this.borderSize; }
  get outerHeight() { return this.offsetHeight + 2 * this.marginY; }
  get outerWidth() { return this.offsetWidth + 2 * this.marginX; }

  get maxX() { return this.x + this.offsetWidth; }
  get maxY() { return this.x + this.offsetHeight; }

  get size() {
    let count = 0;
    this.eachNode(() => { count += 1; });
    return count;
  }

  get depth() {
    if (!this.parent) {
      return 0;
    }
    return this.parent.depth + 1;
  }

  // logical structure of the tree node
  parent = null;
  children = [];
  id = '';
  label = '';

  #data = null;
  #options = null;
  get data() { return this.#data; } // read only
  get options() { return this.#options; } // read only

  get isRoot() { return this.depth === 0; }
  get isLeaf() { return this.children.length === 0; }

  constructor(data, _options, isolated = false) {
    // override properties, methods, etc.
    // notice that if the method uses context(this), it might fail
    /* eslint-disable-next-line no-constructor-return */
    if (data instanceof Node) return data;
    this.#data = data; // storing data
    const options = mix({}, DEFAULT_OPTIONS, _options);
    this.#options = options;
    this.id = options.getId(data);
    this.label = options.getLabel(data);
    this.x = options.getX(data);
    this.y = options.getY(data);
    this.height = options.getHeight(data);
    this.width = options.getWidth(data);
    this.marginX = options.getMarginX(data);
    this.marginY = options.getMarginY(data);
    this.paddingX = options.getPaddingX(data);
    this.paddingY = options.getPaddingY(data);
    this.borderSize = options.getBorderSize(data);
    // children initializing
    if (!isolated) {
      const nodes = [this];
      let current;
      while (nodes.length) {
        current = nodes.shift();
        const childrenData = current.options.getChildren(current.data);
        const length = isArray(childrenData) ? childrenData.length : 0;
        if (childrenData && length) {
          for (let i = 0; i < length; i++) {
            const child = new Node(childrenData[i], options);
            current.children[i] = child;
            nodes.push(child);
            child.parent = current;
          }
        }
      }
    }
  }

  clone() { return new Node(this.data, this.options); }

  eachNode(callback) {
    // chainable
    // Depth First Traverse
    let nodes = [this];
    let current;
    while (nodes.length) {
      current = nodes.shift();
      callback(current);
      nodes = current.children.concat(nodes);
    }
    return this;
  }

  breadthFirstTraverse(callback) {
    // chainable
    let nodes = [this];
    let current;
    while (nodes.length) {
      current = nodes.shift();
      callback(current);
      nodes = nodes.concat(current.children);
    }
    return this;
  }

  getBoundingRect() {
    // Bounding Rectangle for the Node itself(offset size)
    return new Rectangle(this.x, this.y, this.offsetWidth, this.offsetHeight);
  }

  getTreeBoundingRect() {
    // Bounding Rectangle for the whole tree(offset size)
    let rect = this.getBoundingRect();
    this.eachNode((node) => {
      rect = Rectangle.union(rect, node.getBoundingRect());
    });
    return rect;
  }

  translate(tx = 0, ty = 0) {
    // chainable
    this.eachNode((node) => {
      node.x += tx;
      node.y += ty;
    });
    return this;
  }

  translateTo(x, y) {
    // chainable
    const dx = x - this.x;
    const dy = y - this.y;
    return this.translate(dx, dy);
  }

  horizontalFlip() {
    // chainable
    // mirror inversion by the root
    const oldX = this.x;
    const oldY = this.y;
    this.eachNode((node) => {
      node.x = 0 - node.x - node.offsetWidth;
    });
    return this.translateTo(oldX, oldY);
  }

  verticalFlip() {
    // chainable
    // mirror inversion by the root
    const oldX = this.x;
    const oldY = this.y;
    this.eachNode((node) => {
      node.y = 0 - node.y - node.offsetHeight;
    });
    return this.translateTo(oldX, oldY);
  }
}
export default Node;