Come stampare un diagramma ad albero binario

1. Introduzione

La stampa è una tecnica di visualizzazione molto comune per le strutture dati. Tuttavia, può essere complicato quando si tratta di alberi, a causa della loro natura gerarchica.

In questo tutorial impareremo alcune tecniche di stampa per alberi binari in Java.

2. Diagrammi ad albero

Nonostante i limiti del disegno con solo personaggi sopra sulla console, ci sono molte forme di diagramma differenti per rappresentare le strutture ad albero. La scelta di uno di loro dipende principalmente dalle dimensioni e dall'equilibrio dell'albero.

Diamo un'occhiata ad alcuni dei possibili tipi di diagrammi che possiamo stampare:

Ma ne spiegheremo uno pratico che è anche più facile da implementare. Prendendo in considerazione la direzione in cui cresce l'albero, possiamo chiamarlo albero orizzontale :

Poiché l'albero orizzontale scorre sempre nella stessa direzione in cui scorre il testo , abbiamo alcuni vantaggi nello scegliere un diagramma orizzontale rispetto ad altri:

  1. Possiamo anche visualizzare alberi grandi e sbilanciati
  2. La lunghezza dei valori del nodo non influisce sulla struttura di visualizzazione
  3. È molto più facile da implementare

Pertanto, andremo con il diagramma orizzontale e implementeremo una semplice classe di stampanti ad albero binario nelle sezioni successive.

3. Modello di albero binario

Prima di tutto, dovremmo modellare un albero binario di base che possiamo fare con poche righe di codice.

Definiamo una semplice classe BinaryTreeModel :

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

4. Dati del test di esempio

Prima di iniziare a implementare la nostra stampante ad albero binario, dobbiamo creare alcuni dati di esempio per testare in modo incrementale la nostra visualizzazione:

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. Stampante ad albero binario

Certamente, abbiamo bisogno di una classe separata per mantenere pulito il nostro BinaryTreeModel per il bene del principio di responsabilità unica.

Ora, potremmo usare il Visitor Pattern in modo che l'albero gestisca la gerarchia e la nostra stampante gestisca solo la stampa. Ma per questo tutorial, li terremo insieme per renderlo semplice.

Pertanto, definiamo una classe denominata BinaryTreePrinter e iniziamo a implementarla.

5.1. Traversal pre-ordine

Considerando il nostro diagramma orizzontale, per stamparlo correttamente, possiamo fare un semplice inizio utilizzando il preordine traversal.

Di conseguenza, per eseguire l'attraversamento del preordine, è necessario implementare un metodo ricorsivo che visiti prima il nodo radice, quindi la sottostruttura sinistra e infine la sottostruttura destra.

Definiamo un metodo per attraversare il nostro albero:

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()); } } 

Successivamente, definiamo il nostro metodo di stampa:

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

Quindi, possiamo semplicemente stampare il nostro albero di prova:

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

L'output sarà l'elenco dei nodi dell'albero in ordine attraversato:

root node1 node3 node7 node8 node9 node4 node2 node5 node6 

5.2. Aggiunta di bordi ad albero

Per impostare correttamente il nostro diagramma, utilizziamo tre tipi di caratteri "├──", "└──" e "│" per visualizzare i nodi. I primi due sono per i puntatori e l'ultimo serve per riempire i bordi e collegare i puntatori.

Aggiorniamo il nostro metodo traversePreOrder , aggiungiamo due parametri come padding e pointer e usiamo i caratteri rispettivamente:

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()); } } 

Inoltre, aggiorniamo anche il metodo di stampa :

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

Quindi, testiamo di nuovo il nostro BinaryTreePrinter :

Quindi, con tutte le imbottiture e i puntatori, il nostro diagramma si è modellato bene.

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); } } 

Inoltre, abbiamo bisogno di una piccola modifica nel nostro metodo di stampa :

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

Infine, il nostro diagramma si è formato in una bella forma con un output pulito:

6. Conclusione

In questo articolo, abbiamo imparato un modo semplice e pratico per stampare un albero binario in Java .

Tutti gli esempi di questo articolo e casi di test aggiuntivi sono disponibili su GitHub.