So drucken Sie ein Binärbaumdiagramm

1. Einleitung

Das Drucken ist eine sehr verbreitete Visualisierungstechnik für Datenstrukturen. Bei Bäumen kann es jedoch aufgrund ihrer hierarchischen Natur schwierig sein.

In diesem Tutorial lernen wir einige Drucktechniken für Binärbäume in Java kennen.

2. Baumdiagramme

Trotz der Einschränkungen beim Zeichnen mit nur Zeichen auf der Konsole gibt es viele verschiedene Diagrammformen zur Darstellung von Baumstrukturen. Die Wahl eines davon hängt hauptsächlich von der Größe und dem Gleichgewicht des Baumes ab.

Schauen wir uns einige der möglichen Diagrammtypen an, die wir drucken können:

Wir werden jedoch eine praktische erläutern, die auch einfacher zu implementieren ist. Wenn wir die Richtung berücksichtigen, in der der Baum wächst, können wir ihn als horizontalen Baum bezeichnen :

Da der horizontale Baum immer in die gleiche Richtung fließt wie der Text , haben wir einige Vorteile bei der Auswahl eines horizontalen Diagramms gegenüber anderen:

  1. Wir können uns auch große und unausgeglichene Bäume vorstellen
  2. Die Länge der Knotenwerte hat keinen Einfluss auf die Anzeigestruktur
  3. Es ist viel einfacher zu implementieren

Daher werden wir in den nächsten Abschnitten mit dem horizontalen Diagramm eine einfache Klasse von Binärbaumdruckern implementieren.

3. Binäres Baummodell

Zunächst sollten wir einen einfachen Binärbaum modellieren, den wir mit nur wenigen Codezeilen erstellen können.

Definieren wir eine einfache BinaryTreeModel- Klasse:

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

4. Beispieltestdaten

Bevor wir mit der Implementierung unseres Binärbaumdruckers beginnen, müssen wir einige Beispieldaten erstellen, um unsere Visualisierung schrittweise zu testen:

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. Binärbaumdrucker

Natürlich benötigen wir eine separate Klasse, um unser BinaryTreeModel aus Gründen des Einzelverantwortungsprinzips sauber zu halten .

Jetzt können wir das Besuchermuster verwenden, sodass der Baum die Hierarchie und unser Drucker nur den Druck übernimmt. Aber für dieses Tutorial werden wir sie zusammenhalten, um es einfach zu halten.

Daher definieren wir eine Klasse mit dem Namen BinaryTreePrinter und beginnen mit der Implementierung.

5.1. Traversal vorbestellen

Wenn wir unser horizontales Diagramm betrachten, um es richtig zu drucken, können wir einen einfachen Anfang machen, indem wir die Durchquerung vorbestellen .

Folglich vorbestellbarer traversal durchzuführen, müssen wir eine rekursive Methode , dass die ersten Besuche den Wurzelknoten, dann linker Teilbaum und schließlich der rechte Teilbaum implementieren.

Definieren wir eine Methode zum Durchlaufen unseres Baums:

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

Als nächstes definieren wir unsere Druckmethode:

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

So können wir einfach unseren Testbaum drucken:

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

Die Ausgabe ist die Liste der Baumknoten in durchlaufender Reihenfolge:

root node1 node3 node7 node8 node9 node4 node2 node5 node6 

5.2. Baumkanten hinzufügen

Um unser Diagramm korrekt einzurichten, verwenden wir drei Arten von Zeichen: "├──", "└──" und "│", um Knoten zu visualisieren. Die ersten beiden sind für Zeiger und die letzte dient zum Füllen der Kanten und zum Verbinden der Zeiger.

Aktualisieren wir unsere traversePreOrder- Methode, fügen zwei Parameter als Auffüllung und Zeiger hinzu und verwenden die folgenden Zeichen:

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

Auch wir aktualisieren Druckverfahren auch:

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

Testen wir also unseren BinaryTreePrinter erneut:

Somit hat sich unser Diagramm mit all den Polstern und Zeigern gut geformt.

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

Außerdem müssen wir unsere Druckmethode geringfügig ändern :

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

Schließlich hat sich unser Diagramm zu einer schönen Form mit einer sauberen Ausgabe geformt:

6. Fazit

In diesem Artikel haben wir eine einfache und praktische Methode zum Ausdrucken eines Binärbaums in Java kennengelernt .

Alle Beispiele dieses Artikels und zusätzliche Testfälle sind auf GitHub verfügbar.