Hvordan skrive ut et diagram over binært tre

1. Introduksjon

Utskrift er en veldig vanlig visualiseringsteknikk for datastrukturer. Det kan imidlertid være vanskelig når det kommer til trær på grunn av deres hierarkiske natur.

I denne veiledningen lærer vi noen utskriftsteknikker for binære trær i Java.

2. Trediagrammer

Til tross for begrensningene ved å tegne med bare tegn over på konsollen, er det mange forskjellige diagramformer som representerer trestrukturer. Å velge en av dem avhenger hovedsakelig av størrelsen og balansen på treet.

La oss ta en titt på noen av de mulige typer diagrammer som vi kan skrive ut:

Men vi vil forklare en praktisk som også er enklere å implementere. Ved å ta hensyn til retningen der treet vokser, kan vi kalle det a horisontalt tre:

Fordi det horisontale treet flyter alltid i samme retning som teksten flyter, vi har noen fordeler ved å velge et horisontalt diagram fremfor andre:

  1. Vi kan også visualisere store og ubalanserte trær
  2. Lengden på nodeverdiene påvirker ikke skjermstrukturen
  3. Det er mye lettere å implementere

Derfor vil vi gå med det horisontale diagrammet og implementere en enkel binær treskriverklasse i de neste avsnittene.

3. Binary Tree Model

Først og fremst bør vi modellere et grunnleggende binært tre som vi kan gjøre med bare noen få kodelinjer.

La oss definere en enkel BinaryTreeModel klasse:

offentlig klasse BinaryTreeModel {private Object-verdi; privat BinaryTreeModel igjen; privat BinaryTreeModel høyre; public BinaryTreeModel (Object value) {this.value = value; } // standard getters and setters} 

4. Eksempel på testdata

Før vi begynner å implementere vår binære treskriver, må vi lage noen eksempeldata for å teste trinnvis visualiseringen vår:

BinaryTreeModel root = ny BinaryTreeModel ("root"); 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. Binary Tree Printer

Vi trenger absolutt en egen klasse for å beholde vår BinaryTreeModel rengjør av hensyn til prinsippet om enkelt ansvar.

Nå kan vi bruke besøksmønsteret slik at treet håndterer hierarkiet og skriveren vår bare håndterer utskriften. Men for denne opplæringen holder vi dem sammen for å holde det enkelt.

Dermed definerer vi en klasse som heter BinaryTreePrinter og begynn å implementere den.

5.1. Forhåndsbestill traversal

Tatt i betraktning det horisontale diagrammet vårt, for å skrive det riktig, kan vi gjøre en enkel start ved å bruke forhåndsbestille traversal.

Følgelig for å utføre forhåndsbestilling av traversal, må vi implementere en rekursiv metode som først besøker rotnoden, deretter venstre undertre og til slutt høyre undertre.

La oss definere en metode for å krysse treet vårt:

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

Deretter la oss definere utskriftsmetoden vår:

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

Dermed kan vi bare skrive ut testtreet vårt:

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

Utgangen vil være listen over treknuter i krysset rekkefølge:

root node1 node3 node7 node8 node9 node4 node2 node5 node6 

5.2. Legge til trekant

For å sette opp diagrammet vårt riktig, bruker vi tre typer tegn “├──”, “└──” og “│” for å visualisere noder. De to første av dem er for pekere, og den siste er å fylle kantene og koble pekerne.

La oss oppdatere vår traversePreOrder metode, legg til to parametere som polstring og pekeren, og bruk tegnene henholdsvis:

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

Vi oppdaterer også skrive ut metode også:

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

Så la oss teste vår BinaryTreePrinter en gang til:

Dermed, med alle polstringer og pekere, har diagrammet vårt formet seg pent.

Imidlertid har vi fortsatt noen ekstra linjer å bli kvitt:

Når vi ser over på diagrammet, er det fortsatt tegn på tre feil steder:

  1. Kolonnen med ekstra linjer under rotnoden
  2. De ekstra linjene under riktig undertreet
  3. De ekstra linjene under venstre undertre som ikke har noe høyre søsken

5.3. Ulike implementeringer for rot- og barnekoder

For å fikse ekstra linjer kan vi dele opp vår traversemetode. Vi bruker en oppførsel til rotnoden og en annen for underordnede noder.

La oss tilpasse traversePreOrder for bare rotnoden:

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

Deretter oppretter vi en annen metode for barnekoder som traverseNodes. ENI tillegg vil vi legge til en ny parameter hasRightSibling for å implementere de foregående linjene riktig:

public void traverseNodes (StringBuilder sb, String padding, String pointer, BinaryTreeModel node, boolean hasRightSibling) {if (node! = null) {sb.append ("\ n"); sb.append (polstring); sb.append (peker); sb.append (node.getValue ()); StringBuilder paddingBuilder = ny StringBuilder (polstring); hvis (hasRightSibling) {paddingBuilder.append ("│"); } annet {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 trenger også en liten endring i vår skrive ut metode:

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

Endelig har diagrammet vårt blitt til en fin form med en ren utgang:

6. Konklusjon

I denne artikkelen, vi lærte en enkel og praktisk måte å skrive ut et binært tre på Java.

Alle eksemplene i denne artikkelen og flere testtilfeller er tilgjengelig på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found