streamalism.org

1. Inleiding

Afdrukken is een veel voorkomende visualisatietechniek voor datastructuren. Het kan echter lastig zijn als het om bomen gaat, vanwege hun hiërarchische aard.

In deze tutorial leren we enkele afdruktechnieken voor binaire bomen in Java.

2. Boomdiagrammen

Ondanks de beperkingen van het tekenen met alleen tekens op de console, zijn er veel verschillende diagramvormen om boomstructuren weer te geven. Het kiezen van een van hen hangt meestal af van de grootte en de balans van de boom.

Laten we eens kijken naar enkele van de mogelijke soorten diagrammen die we kunnen afdrukken:

Maar we zullen een praktische uitleggen die ook gemakkelijker te implementeren is. Door rekening te houden met de richting waarin de boom groeit, kunnen we het een horizontale boom:

Omdat de horizontale boom loopt altijd in dezelfde richting als de tekst, hebben we enkele voordelen om een ​​horizontaal diagram te kiezen boven andere:

1. We kunnen ook grote en ongebalanceerde bomen visualiseren
2. De lengte van knooppuntwaarden heeft geen invloed op de weergavestructuur
3. Het is veel gemakkelijker te implementeren

Daarom gaan we met het horizontale diagram en implementeren we een eenvoudige binaire boomprinterklasse in de volgende secties.

3. Binair boommodel

Allereerst moeten we een eenvoudige binaire structuur modelleren die we kunnen doen met slechts een paar regels code.

Laten we een simpele definiëren BinaryTreeModel klasse:

openbare klasse BinaryTreeModel {waarde van privéobject; privé BinaryTreeModel links; privé BinaryTreeModel rechts; openbare BinaryTreeModel (waarde van het object) {this.value = waarde; } // standaard getters en setters} 

4. Voorbeeld testgegevens

Voordat we beginnen met het implementeren van onze binaire boomprinter, moeten we enkele voorbeeldgegevens maken om onze visualisatie stapsgewijs te testen:

BinaryTreeModel root = nieuw BinaryTreeModel ("root"); BinaryTreeModel node1 = nieuw BinaryTreeModel ("node1"); BinaryTreeModel node2 = nieuw BinaryTreeModel ("node2"); root.setLeft (node1); root.setRight (node2); BinaryTreeModel node3 = nieuw BinaryTreeModel ("node3"); BinaryTreeModel node4 = nieuw BinaryTreeModel ("node4"); knooppunt1.setLeft (knooppunt3); node1.setRight (node4); node2.setLeft (nieuw BinaryTreeModel ("node5")); node2.setRight (nieuw BinaryTreeModel ("node6")); BinaryTreeModel node7 = nieuw BinaryTreeModel ("node7"); knooppunt3.setLeft (knooppunt7); node7.setLeft (nieuw BinaryTreeModel ("node8")); node7.setRight (nieuw BinaryTreeModel ("node9"));

5. Binaire structuurprinter

Zeker, we hebben een aparte klas nodig om onze te behouden BinaryTreeModel schoon in het belang van Single Responsibility Principle.

Nu zouden we het bezoekerspatroon kunnen gebruiken zodat de boom de hiërarchie afhandelt en onze printer alleen het afdrukken afhandelt. Maar voor deze tutorial houden we ze bij elkaar om het simpel te houden.

We definiëren dus een klasse met de naam BinaryTreePrinter en begin met de implementatie ervan.

5.1. Traversal vooraf bestellen

Gezien ons horizontale diagram kunnen we, om het correct af te drukken, een eenvoudige start maken door te gebruiken voorafgaande bestelling traversal.

Bijgevolg, om pre-order traversal uit te voeren, moeten we een recursieve methode implementeren die eerst het hoofdknooppunt bezoekt, dan de linker substructuur en tenslotte de rechter substructuur.

Laten we een methode definiëren om onze boom te doorkruisen:

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

Laten we vervolgens onze afdrukmethode definiëren:

openbare ongeldige print (PrintStream os) {StringBuilder sb = nieuwe StringBuilder (); traversePreOrder (sb, this.tree); os.print (sb.toString ()); } 

We kunnen dus eenvoudig onze testboom afdrukken:

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

De uitvoer is de lijst met boomknooppunten in doorlopende volgorde:

hoofdknooppunt1 knooppunt3 knooppunt7 knooppunt8 knooppunt9 knooppunt4 knooppunt2 knooppunt5 knooppunt6 

5.2. Boomranden toevoegen

Om ons diagram correct op te zetten, gebruiken we drie soorten karakters “├──”, “└──” en “│” om knooppunten te visualiseren. De eerste twee zijn voor pointers en de laatste is om de randen te vullen en de pointers te verbinden.

Laten we onze traversePreOrder methode, voeg twee parameters toe als opvulling en wijzer, en gebruik de karakters respectievelijk:

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 = nieuwe StringBuilder (opvulling); 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 ()); }} 

We updaten ook afdrukken methode ook:

openbare ongeldige print (PrintStream os) {StringBuilder sb = nieuwe StringBuilder (); traversePreOrder (sb, "", "", this.tree); os.print (sb.toString ()); } 

Dus laten we onze testen BinaryTreePrinter opnieuw:

Dus, met alle vullingen en aanwijzingen, heeft ons diagram een ​​mooie vorm gekregen.

We hebben echter nog enkele extra regels om van af te komen:

Als we het diagram bekijken, zijn er nog steeds tekens op drie verkeerde plaatsen:

1. De kolom met extra regels onder het hoofdknooppunt
2. De extra regels onder de rechter substructuur
3. De extra regels onder de linker substructuur die geen rechter broer of zus heeft

5.3. Verschillende implementaties voor root- en child-knooppunten

Om extra lijnen te repareren, kunnen we onze traverse-methode opsplitsen. We passen het ene gedrag toe op het hoofdknooppunt en het andere op onderliggende knooppunten.

Laten we aanpassen traversePreOrder voor alleen het hoofdknooppunt:

openbare String traversePreOrder (BinaryTreeModel root) {if (root == null) {return ""; } StringBuilder sb = nieuwe 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); retourneer sb.toString (); } 

Vervolgens maken we een andere methode voor onderliggende knooppunten als traverseNodes. EENDaarnaast zullen we een nieuwe parameter toevoegen hasRightSibling om de voorgaande regels correct te implementeren:

public void traverseNodes (StringBuilder sb, String padding, String pointer, BinaryTreeModel node, boolean hasRightSibling) {if (node! = null) {sb.append ("\ n"); sb.append (opvulling); sb.append (pointer); sb.append (node.getValue ()); StringBuilder paddingBuilder = nieuwe StringBuilder (opvulling); 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); }} 

We hebben ook een kleine verandering nodig in onze afdrukken methode:

openbare void print (PrintStream os) {os.print (traversePreOrder (boom)); } 

Eindelijk heeft ons diagram een ​​mooie vorm gekregen met een schone output:

6. Conclusie

In dit artikel, we hebben een eenvoudige en praktische manier geleerd om een ​​binaire boom in Java af te drukken.

Alle voorbeelden van dit artikel en aanvullende testcases zijn beschikbaar op GitHub.