Comment imprimer un diagramme d'arbre binaire

1. Introduction

L'impression est une technique de visualisation très courante pour les structures de données. Cela peut être délicat en ce qui concerne les arbres, en raison de leur nature hiérarchique.

Dans ce didacticiel, nous allons apprendre quelques techniques d'impression pour les arbres binaires en Java.

2. Diagrammes arborescents

Malgré les limites du dessin avec uniquement des caractères sur la console, il existe de nombreuses formes de diagramme différentes pour représenter les structures arborescentes. Le choix de l'un d'eux dépend principalement de la taille et de l'équilibre de l'arbre.

Jetons un coup d'œil à certains des types de diagrammes possibles que nous pouvons imprimer:

Mais, nous en expliquerons une pratique qui est également plus facile à mettre en œuvre. En prenant en compte le sens de croissance de l'arbre, on peut l'appeler un arbre horizontal :

Étant donné que l'arborescence horizontale coule toujours dans la même direction que le texte , nous avons certains avantages à choisir un diagramme horizontal par rapport aux autres:

  1. Nous pouvons également visualiser de grands arbres déséquilibrés
  2. La longueur des valeurs de nœud n'affecte pas la structure d'affichage
  3. C'est beaucoup plus simple à mettre en œuvre

Par conséquent, nous allons utiliser le diagramme horizontal et implémenter une simple classe d'imprimante d'arbre binaire dans les sections suivantes.

3. Modèle d'arbre binaire

Tout d'abord, nous devons modéliser un arbre binaire de base que nous pouvons faire avec seulement quelques lignes de code.

Définissons une classe BinaryTreeModel simple :

public class BinaryTreeModel { private Object value; private BinaryTreeModel left; private BinaryTreeModel right; public BinaryTreeModel(Object value) { this.value = value; } // standard getters and setters } 

4. Exemple de données de test

Avant de commencer à implémenter notre imprimante d'arborescence binaire, nous devons créer des exemples de données pour tester de manière incrémentielle notre visualisation:

BinaryTreeModel root = new BinaryTreeModel("root"); BinaryTreeModel node1 = new BinaryTreeModel("node1"); BinaryTreeModel node2 = new BinaryTreeModel("node2"); root.setLeft(node1); root.setRight(node2); BinaryTreeModel node3 = new BinaryTreeModel("node3"); BinaryTreeModel node4 = new BinaryTreeModel("node4"); node1.setLeft(node3); node1.setRight(node4); node2.setLeft(new BinaryTreeModel("node5")); node2.setRight(new BinaryTreeModel("node6")); BinaryTreeModel node7 = new BinaryTreeModel("node7"); node3.setLeft(node7); node7.setLeft(new BinaryTreeModel("node8")); node7.setRight(new BinaryTreeModel("node9"));

5. Imprimante d'arbre binaire

Certes, nous avons besoin d'une classe distincte pour garder notre BinaryTreeModel propre dans l'intérêt du principe de responsabilité unique.

Maintenant, nous pourrions utiliser le modèle de visiteur pour que l'arborescence gère la hiérarchie et que notre imprimante gère simplement l'impression. Mais pour ce didacticiel, nous les garderons ensemble afin de rester simple.

Ainsi, nous définissons une classe nommée BinaryTreePrinter et commençons à l'implémenter.

5.1. Pré-commande Traversal

Compte tenu de notre diagramme horizontal, pour l'imprimer correctement, nous pouvons faire un début simple en utilisant le parcours de pré-commande .

Par conséquent, pour effectuer un parcours de pré-commande, nous devons implémenter une méthode récursive qui visite d'abord le nœud racine, puis le sous-arbre gauche et enfin le sous-arbre droit.

Définissons une méthode pour parcourir notre arbre:

public void traversePreOrder(StringBuilder sb, BinaryTreeModel node) { if (node != null) { sb.append(node.getValue()); sb.append("\n"); traversePreOrder(sb, node.getLeft()); traversePreOrder(sb, node.getRight()); } } 

Ensuite, définissons notre méthode d'impression:

public void print(PrintStream os) { StringBuilder sb = new StringBuilder(); traversePreOrder(sb, this.tree); os.print(sb.toString()); } 

Ainsi, nous pouvons simplement imprimer notre arbre de test:

new BinaryTreePrinter(root).print(System.out); 

La sortie sera la liste des nœuds d'arbre dans l'ordre parcouru:

root node1 node3 node7 node8 node9 node4 node2 node5 node6 

5.2. Ajout d'arêtes d'arbre

Pour configurer correctement notre diagramme, nous utilisons trois types de caractères «├──», «└──» et «│» pour visualiser les nœuds. Les deux premiers d'entre eux sont pour les pointeurs et le dernier est de remplir les bords et de connecter les pointeurs.

Mettons à jour notre méthode traversePreOrder , ajoutons deux paramètres comme remplissage et pointeur , et utilisons respectivement les caractères:

public void traversePreOrder(StringBuilder sb, String padding, String pointer, BinaryTreeModel node) { if (node != null) { sb.append(padding); sb.append(pointer); sb.append(node.getValue()); sb.append("\n"); StringBuilder paddingBuilder = new StringBuilder(padding); paddingBuilder.append("│ "); String paddingForBoth = paddingBuilder.toString(); String pointerForRight = "└──"; String pointerForLeft = (node.getRight() != null) ? "├──" : "└──"; traversePreOrder(sb, paddingForBoth, pointerForLeft, node.getLeft()); traversePreOrder(sb, paddingForBoth, pointerForRight, node.getRight()); } } 

Nous mettons également à jour la méthode d' impression :

public void print(PrintStream os) { StringBuilder sb = new StringBuilder(); traversePreOrder(sb, "", "", this.tree); os.print(sb.toString()); } 

Alors, testons à nouveau notre BinaryTreePrinter :

Ainsi, avec tous les rembourrages et pointeurs, notre diagramme s'est bien formé.

However, we still have some extra lines to get rid of:

As we look over on diagram, there are still characters in three wrong places:

  1. The column of extra lines under the root node
  2. The extra lines under the right subtree
  3. The extra lines under the left subtree which has no right sibling

5.3. Different Implementations for Root and Child Nodes

In order to fix extra lines, we can split up our traverse method. We'll apply one behavior to the root node and another for child nodes.

Let's customize traversePreOrder for only the root node:

public String traversePreOrder(BinaryTreeModel root) { if (root == null) { return ""; } StringBuilder sb = new StringBuilder(); sb.append(root.getValue()); String pointerRight = "└──"; String pointerLeft = (root.getRight() != null) ? "├──" : "└──"; traverseNodes(sb, "", pointerLeft, root.getLeft(), root.getRight() != null); traverseNodes(sb, "", pointerRight, root.getRight(), false); return sb.toString(); } 

Next, we'll create another method for child nodes as traverseNodes. Additionally, we will add a new parameter hasRightSibling to implement the preceding lines correctly:

public void traverseNodes(StringBuilder sb, String padding, String pointer, BinaryTreeModel node, boolean hasRightSibling) { if (node != null) { sb.append("\n"); sb.append(padding); sb.append(pointer); sb.append(node.getValue()); StringBuilder paddingBuilder = new StringBuilder(padding); if (hasRightSibling) { paddingBuilder.append("│ "); } else { paddingBuilder.append(" "); } String paddingForBoth = paddingBuilder.toString(); String pointerRight = "└──"; String pointerLeft = (node.getRight() != null) ? "├──" : "└──"; traverseNodes(sb, paddingForBoth, pointerLeft, node.getLeft(), node.getRight() != null); traverseNodes(sb, paddingForBoth, pointerRight, node.getRight(), false); } } 

De plus, nous avons besoin d'un petit changement dans notre méthode d' impression :

public void print(PrintStream os) { os.print(traversePreOrder(tree)); } 

Enfin, notre diagramme a pris une belle forme avec une sortie propre:

6. Conclusion

Dans cet article, nous avons appris un moyen simple et pratique d'imprimer un arbre binaire en Java .

Tous les exemples de cet article et des cas de test supplémentaires sont disponibles à l'adresse over sur GitHub.