c++ - ツリーグラフ：爆発する可能性のある描画要素

Question

データの保存方法とツリーグラフの描画方法を決定しています。2つの要素の間に最小のスペースMが必要だとすると、幅優先探索でツリー構造全体を上から下にトラバースできると考えていました。

現在の要素の下に要素が1つしかない場合は、父親と同じX座標で描画されます。2つの要素がある場合、それらは、父のX座標に対して、1つは-M / 2に、もう1つは+ M/2に描画されます。等々..

問題は、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);
  }
}