いつものように、問題を注意深く説明することは助けになったようです。私はそれを理解したと思います。重要なアイデアは、ツリーを再帰的にトラバースし、（他のいくつかのことの中でも）各ステップのすべてのサブツリーの深さの最小公倍数を計算することです。
答えはJavaで書かれていますが、PHP、C＃、またはwhat-have-youに書き直すのは簡単なはずです。次の2つの補助クラスを参照し、HTMLテーブルを対象としています。
class Tree {
String val;
Tree[] children;
...
}
class Cell {
String val;
int row, col, rowspan, colspan;
...
}
ソリューションは2つの部分に分かれています。
Treeからへの変換List<Cell>。
List<Cell>適切なレイアウト<table>...</table>。
（たとえば、スプレッドシートをターゲットにする場合は、おそらく必要ありません。）
Treeからへの変換List<Cell>
これは、以下に定義されているメソッドrowsToUseを使用して行われます。getCells前者は特定のツリーをレイアウトするために必要な行の総数を計算し、後者は実際Cellのsを生成します。引数は次のことを示します。
tCellsが生成されるツリーのルートです。rowcol最上位（ルート）のセルの現在の行と列を示します。rowsLeft現在のツリーを分散する行数を指定します。
2つの方法は次のとおりです。
public static int rowsToUse(Tree t) {
int childrenRows = t.children.length == 0 ? 0 : 1;
for (Tree child : t.children)
childrenRows = lcm(childrenRows, rowsToUse(child));
return 1 + childrenRows;
}
public static List<Cell> getCells(Tree t, int row, int col, int rowsLeft) {
// Add top-most cell corresponding to the root of the current tree.
int rootRows = rowsLeft / rowsToUse(t);
List<Cell> cells = new ArrayList<Cell>();
cells.add(new Cell(t.val, row, col, rootRows, width(t)));
// Generate cells for subtrees.
for (Tree child : t.children) {
cells.addAll(getCells(child, row+rootRows, col, rowsLeft-rootRows));
col += width(child);
}
return cells;
}
メソッドdepth、widthおよびlcmは簡単です。必要に応じて、下部にある完全なソースを参照してください。
List<Cell>適切なレイアウト<table>...</table>
public static String getHtmlTable(List<Cell> cells) {
// Sort the cells primarily on row, secondarily on column.
Collections.sort(cells, new Comparator<Cell>() {
public int compare(Cell c1, Cell c2) {
int pri = Integer.valueOf(c1.row).compareTo(c2.row);
int sec = Integer.valueOf(c1.col).compareTo(c2.col);
return pri != 0 ? pri : sec;
}
});
// Lay out the cells row by row.
StringBuilder result = new StringBuilder("<table><tbody>");
for (int row = 0, i = 0; i < cells.size(); row++) {
result.append("<tr>\n");
for (; i < cells.size() && cells.get(i).row == row; i++)
result.append(cells.get(i).asTdTag());
result.append("</tr>\n");
}
return result.append("</tbody></table>").toString();
}
完全なソースとデモ。
これが完全なソースです。与えられた木
Tree t = new Tree("1",
new Tree("2",
new Tree("4"),
new Tree("5",
new Tree("8"),
new Tree("9"))),
new Tree("3",
new Tree("6"),
new Tree("7")));
次のテーブル本体を生成します。
<tr><td colspan='5'>1</td></tr>
<tr><td colspan='3' rowspan='2'>2</td><td colspan='2' rowspan='3'>3</td></tr>
<tr></tr>
<tr><td rowspan='4'>4</td><td colspan='2' rowspan='2'>5</td></tr>
<tr><td rowspan='3'>6</td><td rowspan='3'>7</td></tr>
<tr><td rowspan='2'>8</td><td rowspan='2'>9</td></tr>
のように見えます
完全なソース：
import java.io.*;
import java.util.*;
class Tree {
String val;
Tree[] children;
public Tree(String val, Tree... children) {
this.val = val;
this.children = children;
}
}
class Cell {
String val;
int row, col, rowspan, colspan;
public Cell(String val, int row, int col, int rowspan, int colspan) {
this.val = val;
this.row = row;
this.col = col;
this.rowspan = rowspan;
this.colspan = colspan;
}
public String asTdTag() {
String cs = colspan == 1 ? "" : " colspan='" + colspan + "'";
String rs = rowspan == 1 ? "" : " rowspan='" + rowspan + "'";
return "<td" + cs + rs + ">" + val + "</td>";
}
}
public class TreeTest {
public static int rowsToUse(Tree t) {
int childrenRows = t.children.length == 0 ? 0 : 1;
for (Tree child : t.children)
childrenRows = lcm(childrenRows, rowsToUse(child));
return 1 + childrenRows;
}
public static List<Cell> getCells(Tree t, int row, int col, int rowsLeft) {
// Add top-most cell corresponding to the root of the current tree.
int rootRows = rowsLeft / rowsToUse(t);
List<Cell> cells = new ArrayList<Cell>();
cells.add(new Cell(t.val, row, col, rootRows, width(t)));
// Generate cells for subtrees.
for (Tree child : t.children) {
cells.addAll(getCells(child, row+rootRows, col, rowsLeft-rootRows));
col += width(child);
}
return cells;
}
public static int width(Tree t) {
if (t.children.length == 0)
return 1;
int w = 0;
for (Tree child : t.children)
w += width(child);
return w;
}
public static int lcm(int a, int b) {
int c = a * b;
while (b > 0) {
int t = b;
b = a % b;
a = t;
}
return c / a;
}
public static String getHtmlTable(List<Cell> cells) {
// Sort the cells primarily on row, secondarily on column.
Collections.sort(cells, new Comparator<Cell>() {
public int compare(Cell c1, Cell c2) {
int pri = Integer.valueOf(c1.row).compareTo(c2.row);
int sec = Integer.valueOf(c1.col).compareTo(c2.col);
return pri != 0 ? pri : sec;
}
});
// Lay out the cells row by row.
StringBuilder result = new StringBuilder("<table><tbody>");
for (int row = 0, i = 0; i < cells.size(); row++) {
result.append("<tr>\n");
for (; i < cells.size() && cells.get(i).row == row; i++)
result.append(" " + cells.get(i).asTdTag() + "\n");
result.append("</tr>\n");
}
return result.append("</tbody></table>").toString();
}
public static void main(String[] args) throws IOException {
Tree t = new Tree("1",
new Tree("2",
new Tree("4"),
new Tree("5",
new Tree("8"),
new Tree("9"))),
new Tree("3",
new Tree("6"),
new Tree("7")));
FileWriter fw = new FileWriter("tree.html");
List<Cell> cells = getCells(t, 0, 0, rowsToUse(t));
fw.write("<html><head><style>table, td { border-style: solid; } " +
"table { border-spacing: 0px; border-width: 0 0 1px 5px; } " +
"td { padding: 15px; text-align: center; " +
"border-width: 1px 5px 0 0;} </style></head><body>");
fw.write(getHtmlTable(cells));
fw.write("</body></html>");
fw.close();
}
}
