streamalism.org

1. Introduktion

Udskrivning er en meget almindelig visualiseringsteknik til datastrukturer. Det kan dog være vanskeligt, når det kommer til træer på grund af deres hierarkiske natur.

I denne vejledning lærer vi nogle udskrivningsteknikker til binære træer i Java.

2. Trædiagrammer

På trods af begrænsningerne ved at tegne med kun tegn over på konsollen, er der mange forskellige diagramformer, der repræsenterer træstrukturer. At vælge en af ​​dem afhænger for det meste af træets størrelse og balance.

Lad os se på nogle af de mulige typer diagrammer, som vi kan udskrive:

Men vi vil forklare en praktisk, som også er lettere at implementere. Ved at tage den retning i betragtning, hvor træet vokser, kan vi kalde det a vandret træ:

Fordi det vandrette træ flyder altid i samme retning som teksten flyder, vi har nogle fordele ved at vælge et vandret diagram frem for andre:

1. Vi kan også visualisere store og ubalancerede træer
2. Længden af ​​nodeværdier påvirker ikke skærmstrukturen
3. Det er meget lettere at implementere

Derfor vil vi gå med det vandrette diagram og implementere en simpel binær træprinterklasse i de næste sektioner.

3. Binærtræmodel

Først og fremmest skal vi modellere et grundlæggende binært træ, som vi kan gøre med blot nogle få linjer kode.

Lad os definere en simpel BinaryTreeModel klasse:

offentlig klasse BinaryTreeModel {værdi for private objekter; privat BinaryTreeModel tilbage; privat BinaryTreeModel højre; public BinaryTreeModel (Object value) {this.value = værdi; } // standard getters og setters} 

4. Eksempel på testdata

Inden vi begynder at implementere vores binære træprinter, skal vi oprette nogle eksempeldata for trinvist at teste vores visualisering:

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

5. Binærtræprinter

Bestemt har vi brug for en separat klasse for at holde vores BinaryTreeModel rengør af hensyn til princippet om et enkelt ansvar.

Nu kunne vi bruge besøgende mønster, så træet håndterer hierarkiet, og vores printer håndterer udskrivningen. Men til denne vejledning holder vi dem sammen for at holde det simpelt.

Således definerer vi en klasse med navnet BinaryTreePrinter og begynd at implementere det.

5.1. Forudbestil gennemgang

I betragtning af vores vandrette diagram, for at udskrive det ordentligt, kan vi starte en simpel start ved hjælp af forudbestille gennemkørsel.

Følgelig, for at udføre forudbestillingsgennemgang er vi nødt til at implementere en rekursiv metode, der først besøger rodknudepunktet, derefter venstre undertræ og til sidst det højre undertræ.

Lad os definere en metode til at krydse vores træ:

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

Lad os derefter definere vores udskrivningsmetode:

offentlig ugyldig udskrivning (PrintStream os) {StringBuilder sb = ny StringBuilder (); traversePreOrder (sb, this.tree); os.print (sb.toString ()); } 

Således kan vi blot udskrive vores testtræ:

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

Outputtet vil være listen over træknudepunkter i gennemkørt rækkefølge:

rodnode1 node3 node7 node8 node9 node4 node2 node5 node6 

5.2. Tilføjelse af trækanter

For at oprette vores diagram korrekt bruger vi tre typer tegn "├──", "└──" og "│" til at visualisere noder. De to første af dem er til markører, og den sidste er at fylde kanterne og forbinde markørerne.

Lad os opdatere vores traversePreOrder metode, tilføj to parametre som polstring og markør, og brug tegnene henholdsvis:

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 = ny StringBuilder (polstring); 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 ()); }} 

Vi opdaterer også Print metode også:

offentlig ugyldig udskrivning (PrintStream os) {StringBuilder sb = ny StringBuilder (); traversePreOrder (sb, "", "", this.tree); os.print (sb.toString ()); } 

Så lad os teste vores BinaryTreePrinter igen:

Således, med alle polstringer og markører, har vores diagram formet sig pænt.

Vi har dog stadig nogle ekstra linjer at slippe af med:

Når vi ser over på diagrammet, er der stadig tegn på tre forkerte steder:

1. Kolonnen med ekstra linjer under rodnoden
2. De ekstra linjer under det rigtige undertræ
3. De ekstra linjer under venstre undertræ, som ikke har noget højre søskende

5.3. Forskellige implementeringer for rod- og underknudepunkter

For at rette ekstra linjer kan vi opdele vores traversmetode. Vi anvender en adfærd til rodnoden og en anden for undernoder.

Lad os tilpasse traversePreOrder kun for rodnoden:

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

Derefter opretter vi en anden metode til underordnede noder som traverseNodes. ENdditionelt tilføjer vi en ny parameter hasRightSibling for at implementere de foregående linjer korrekt:

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

Vi har også brug for en lille ændring i vores Print metode:

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

Endelig har vores diagram dannet sig i en flot form med et rent output:

6. Konklusion

I denne artikel vi lærte en enkel og praktisk måde at udskrive et binært træ på Java.

Alle eksempler på denne artikel og yderligere testtilfælde findes på GitHub.