c++ - 树形图：绘制可能爆炸的元素

Question

我正在决定如何存储数据以及如何绘制树形图。假设我想要两个元素之间的最小空间 M，我想我可以在呼吸优先搜索中从顶部到底部遍历整个树结构。

如果当前元素下方只有一个元素，它将使用与他父亲相同的 X 坐标进行绘制。如果有两个元素，它们将在 -M/2 处绘制，另一个在 +M/2 处绘制，相对于它们的父 X 坐标。等等..

问题是：如果像 C 这样的元素（见下图）有大量子元素怎么办？我应该重组整个树，因为我应该将元素 D 移到左侧并为 C 的所有 EF 子级腾出空间。将 D 移到左侧会使树弯曲，我也需要移动 B。将 B 向左移动会改变树的对称性，所以我也需要移动 C，依此类推..

如何绘制一个完美对称的树，它的元素可能有大量的孩子？

Answer 1

反过来做：计算每个节点的水平位置后，计算其子节点的水平位置。像这样的东西（警告：完全未经测试的代码；可能完全由错误组成）：

void Node::place_self(coord_t x0, coord_t y0) {
  this->y0 = y0; this->y1 = y0+height;
  if (!left && !right) {
    // This is a leaf. Put its top left corner at (x0,y0).
    this->x0 = x0; this->y0 = y0;
    this->subtree_x1 = x0+width;
  }
  else if (!left || !right) {
    // Only one child. Put this immediately above it.
    Node * child = left ? left : right;
    child->place_self(x0,y0+height+gap);
    coord_t xc = child->x0 + child->width/2;
    this->x0 = xc-width/2;
    this->subtree_x1 = max(this->x0+width, child->subtree_x1);
  }
  else {
    // Two children. Put this above their midline.
    left->place_self(x0, y0+height+gap);
    right->place_self(left->subtree_x1+gap, y0+height+gap);
    coord_t xc = (x0 + right->subtree_x1)/2;
    this->x0 = xc-width/2;
    this->subtree_x1 = max(this->x0+width, right->subtree_x1);
  }
}