J'essaie d'afficher une structure arborescente dans une table, et je n'arrive pas à comprendre le dernier bit.
J'ai une classe de nœuds assez standard (avec les méthodes et les constructeurs supprimés pour plus de clarté),
[["Root", "Child 1", "Grandchild 1"], ["Root", "Child 1", "Grandchild 2"], ["Root", "Child 2", "Grandchild 3"]]
qui pourrait être rempli quelque chose comme ceci:
public List<List<String>> getData(TreeNode<?> root) {
List<List<String>> data = new ArrayList<>();
getData(data, root);
return data;
}
private void getData(List<List<String>> data, TreeNode<?> node) {
if (!node.isLeaf()) {
for (TreeNode<?> child : node.getChildren()) {
getData(data, child);
}
} else {
data.add(getRow(currentNode));
}
}
private List<String> getRow(TreeNode<?> node) {
Deque<String> row = new LinkedList<>();
TreeNode<?> currentNode = node;
while (!currentNode.isRoot()) {
row.addFirst(String.valueOf(currentNode.getData()));
currentNode = currentNode.getParent();
}
return new ArrayList<>(row);
}
Afin d'imprimer ces données dans un tableau, je voudrais pour remplir une structure de liste imbriquée comme suit,
| Root | Child 1 | Grandchild 1 | | | | Grandchild 2 | | | Child 2 | Grandchild 3 |
afin que les données soient 'aplaties', et non répétées, donc je pourrai plus tard l'imprimer dans un tableau comme ceci:
[["Root", "Child 1", "Grandchild 1"], ["", "", "Grandchild 2"], ["", "Child 2", "Grandchild 3"]]
Voici ce que j'ai essayé jusqu'à présent:
TreeNode<String> grandchild1 = new TreeNode<>("Grandchild 1");
TreeNode<String> grandchild2 = new TreeNode<>("Grandchild 2");
TreeNode<String> grandchild3 = new TreeNode<>("Grandchild 3");
TreeNode<String> child1 = new TreeNode<>("Child 1");
child1.addChild(grandchild1);
child1.addChild(grandchild2);
TreeNode<String> child2 = new TreeNode<>("Child 2");
child2.addChild(grandchild3);
TreeNode<String> root = new TreeNode<>("Root");
root.add(child1);
root.add(child2);
Bien que cela collecte récursivement les données à afficher, évidemment, les données seront répétées car pour chaque ligne, la valeur parente est imprimée, et je finirai avec ceci:
public class TreeNode<T> {
private TreeNode<?> parent;
private T data;
private List<TreeNode<?>> children = new ArrayList<>();
}
Ce avec quoi j'ai du mal, c'est un moyen de décider si une certaine valeur doit être imprimée (répétée) ou non, car je suis sûr qu'il doit y avoir une solution élégante.
Il n'y a aucune garantie sur la taille ou la structure de l'arbre donc les plus génériques La solution c serait la meilleure. Toute aide serait grandement appréciée!
3 Réponses :
Vous pouvez probablement y parvenir en utilisant une simple exploration DFS de l'arbre. Vous gardez une trace de la profondeur actuelle de l'arbre, puis à chaque nœud vous imprimez la profondeur multipliée par une colonne blanche, suivie d'une colonne avec la valeur du nœud.
public void printTree(TreeNode<T> node, int depth) {
// Print leaf
if(node.children.size() == 0) {
System.out.print(node.data);
System.out.print("\n");
return;
} else {
// Print current node
System.out.print(node.data);
// Print next nodes at this level
printTree(node.children.get(0), depth + 1);
// Print remaining nodes with leading white columns
for (int i = 1; i < node.children.size(); i++) {
for (int j = 0; j < depth; j++) {
System.out.print(" |");
}
System.out.print(node.children.get(i);
System.out.print("\n");
}
}
}
Je ne pense pas que ce soit correct. La profondeur n'est pas nécessairement synonyme de la quantité d'espaces blancs à imprimer. Un exemple simple: 'Racine -> Enfant 1 -> Petit-enfant 1', doit être imprimé sur 1 ligne: '["Racine", "Enfant 1", "Petit-enfant 1"]', alors que votre solution produirait (si c'était stocké sous forme de tableau et non imprimé) la structure hiérarchique la plus typique: '[["Root", "", ""], ["", "Child 1", ""], ["", "", "Petit-enfant 1"]]'
J'ai modifié un peu mon exemple de code mais plus ou moins le même principe devrait s'appliquer.
Traversée de la même manière que la réponse de @Matteo Ugolotti, juste une profondeur de fin et une impression de nœud de tête différentes.
Pour chaque nœud, affichez tous les enfants sur la même ligne de manière récursive. Lorsque la ligne est imprimée, chaque enfant (le cas échéant) des nœuds qui viennent d'être imprimés est également imprimé de manière récursive.
Les colonnes ont une colonne max qui est utilisée pour afficher tous les nœuds sous forme de colonnes droites. Il devrait être au moins aussi gros que les plus grandes données de nœud.
J'ai supprimé les génériques et créé chaque nœud String pour pouvoir obtenir la longueur de chaque nœud (utilisé pour correctement imprimer des colonnes). Vous pouvez créer une méthode dans votre classe Node qui renvoie la longueur des données (génériques).
public void printTree(Node<String> node, int depth, int columnSize) {
// Print leaf
if(node.children.size() == 0) {
printNode(node, columnSize);
System.out.print("|\n");
} else {
// Print current node
printNode(node, columnSize);
// Print all nodes of this level recursively
printTree(node.children.get(0), depth + 1, columnSize);
// Print all children current node recursively
for (int i = 1; i < node.children.size(); i++) {
printLeading(depth + 1, columnSize);
printTree(node.children.get(i), depth + 1, columnSize);
}
}
}
public void printLeading(int depth, int columnSize) {
// Print the leading white spaces of column at a certain depth
// Each node (depth) takes the column size + 2 characters (= "| ")
for (int i = 0; i < depth * columnSize + depth * 2; i++) {
System.out.print(" ");
}
}
public void printNode(Node<String> node, int columnSize) {
int trailing = columnSize - node.getData().length();
System.out.print("| " + node.data);
// Print the leading white spaces in the column
for (int i = 0; i < trailing; i++) {
System.out.print(" ");
}
}
Merci pour votre réponse, mais je pense que vous avez légèrement mal compris ma question. Je n'essaye pas d'imprimer les données, j'essaie de remplir un tableau imbriqué, la «table» que j'ai montrée est juste pour illustrer le problème, vous n'avez donc pas à vous soucier de la longueur des chaînes. Je vais essayer de modifier votre réponse à ce dont j'ai besoin - clairement une première recherche en profondeur, mais la difficulté que je prévois est de savoir où `` continuer '' lorsque vous passez la liste imbriquée entre les méthodes, plutôt que d'imprimer simplement `` plus d'espace '' directement à partir de la méthode.
Merci à P. van der Laan J'ai pu trouver une solution plutôt peu élégante. S'il y a un moyen meilleur ou plus «standard» pour y parvenir, j'aimerais l'entendre!
J'ai donc créé une classe pour contenir la liste imbriquée et la position actuelle de la ligne:
private void getRowData(NodeGrid data, TreeNode<?> currentNode, int depth) {
if (currentNode.isLeaf()) {
data.addData(String.valueOf(currentNode.getData()));
data.newRow();
} else {
data.addData(String.valueOf(currentNode.getData()));
getRowData(data, currentNode.getChild(0), depth + 1);
for (int i = 1; i < currentNode.getChildren().size(); i++) {
for (int d = 0; d < depth + 1; d++) {
data.addData("");
}
getRowData(data, currentNode.getChild(i), depth + 1);
}
}
}