Ako tlačiť binárny stromový diagram

1. Úvod

Tlač je veľmi častou vizualizačnou technikou pre dátové štruktúry. Môže to byť zložité, pokiaľ ide o stromy, vzhľadom na ich hierarchickú povahu.

V tomto výučbe sa naučíme niektoré techniky tlače pre binárne stromy v Jave.

2. Stromové diagramy

Napriek obmedzeniam kreslenia iba pomocou znakov na konzole existuje veľa rôznych tvarov diagramov, ktoré reprezentujú stromové štruktúry. Výber jedného z nich väčšinou závisí od veľkosti a vyváženia stromu.

Pozrime sa na niektoré z možných typov diagramov, ktoré môžeme vytlačiť:

Vysvetlíme však praktický, ktorý sa tiež ľahšie implementuje. Ak vezmeme do úvahy smer, v ktorom strom rastie, môžeme ho nazvať a vodorovný strom:

Pretože vodorovný strom tečie vždy rovnakým smerom ako text, výber horizontálneho diagramu oproti iným má určité výhody:

  1. Vieme tiež vizualizovať veľké a nevyvážené stromy
  2. Dĺžka hodnôt uzlov nemá vplyv na štruktúru displeja
  3. Je to oveľa jednoduchšie implementovať

Preto pôjdeme s horizontálnym diagramom a v ďalších častiach implementujeme jednoduchú triedu tlačiarní binárnych stromov.

3. Model binárneho stromu

Najskôr by sme mali vymodelovať základný binárny strom, ktorý môžeme robiť iba s niekoľkými riadkami kódu.

Definujme jednoduchý BinaryTreeModel trieda:

public class BinaryTreeModel {private Object value; súkromný BinaryTreeModel vľavo; súkromné ​​právo BinaryTreeModel; public BinaryTreeModel (hodnota objektu) {this.value = hodnota; } // štandardní zakladatelia a zakladatelia} 

4. Vzorové údaje o teste

Predtým, ako začneme implementovať našu tlačiareň s binárnymi stromami, musíme vytvoriť niekoľko vzorových údajov na postupné testovanie našej vizualizácie:

BinaryTreeModel root = nový BinaryTreeModel ("root"); BinaryTreeModel node1 = nový BinaryTreeModel ("node1"); BinaryTreeModel node2 = nový BinaryTreeModel ("node2"); root.setLeft (uzol1); root.setRight (uzol2); BinaryTreeModel node3 = nový BinaryTreeModel ("node3"); BinaryTreeModel node4 = nový BinaryTreeModel ("node4"); node1.setLeft (node3); node1.setRight (node4); node2.setLeft (nový BinaryTreeModel ("node5")); node2.setRight (nový BinaryTreeModel ("node6")); BinaryTreeModel node7 = nový BinaryTreeModel ("node7"); node3.setLeft (node7); node7.setLeft (nový BinaryTreeModel ("node8")); node7.setRight (nový BinaryTreeModel ("node9"));

5. Tlačiareň binárnych stromov

Iste, potrebujeme samostatnú triedu, aby sme si udržali svoje BinaryTreeModel čisté kvôli zásade jedinej zodpovednosti.

Teraz by sme mohli použiť vzor návštevníka, aby strom spracovával hierarchiu a naša tlačiareň iba tlač. Ale pre tento tutoriál ich budeme držať pohromade, aby to bolo jednoduché.

Definujeme teda triedu s názvom BinaryTreePrinter a začať to implementovať.

5.1. Predobjednávka Traversal

Ak vezmeme do úvahy náš horizontálny diagram, aby sme ho správne vytlačili, môžeme urobiť jednoduchý začiatok použitím predobjednať traverz.

V dôsledku toho na vykonanie pre-order traversal, musíme implementovať rekurzívnu metódu, ktorá najskôr navštívi koreňový uzol, potom ľavý podstrom a nakoniec pravý podstrom.

Definujme metódu prechodu nášho stromu:

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

Ďalej definujeme našu metódu tlače:

public void print (PrintStream os) {StringBuilder sb = nový StringBuilder (); traversePreOrder (sb, tento.strom); os.print (sb.toString ()); } 

Takto môžeme jednoducho vytlačiť náš testovací strom:

nový BinaryTreePrinter (root) .print (System.out); 

Výstupom bude zoznam uzlov stromu v poradí prechádzania:

koreňový uzol1 uzol3 uzol7 uzol8 uzol9 uzol4 uzol2 uzol5 uzol6 

5.2. Pridávanie hrán stromov

Aby sme náš diagram nastavili správne, na vizualizáciu uzlov používame tri typy znakov „├──“, „└──“ a „│“. Prvé dva z nich sú pre ukazovatele a posledný je vyplnenie okrajov a spojenie ukazovateľov.

Aktualizujme naše traversePreOrder metóda, pridajte dva parametre ako vypchávka a ukazovateľa použite príslušné znaky:

public void traversePreOrder (StringBuilder sb, výplň reťazca, ukazovateľ reťazca, uzol BinaryTreeModel) {if (uzol! = null) {sb.append (výplň); sb.append (ukazovateľ); sb.append (node.getValue ()); sb.append ("\ n"); StringBuilder paddingBuilder = nový StringBuilder (výplň); paddingBuilder.append ("│"); Reťazec paddingForBoth = paddingBuilder.toString (); Reťazec pointerForRight = "└──"; Reťazec pointerForLeft = (node.getRight ()! = Null)? "├──": "└──"; traversePreOrder (sb, paddingForBoth, pointerForLeft, node.getLeft ()); traversePreOrder (sb, paddingForBoth, pointerForRight, node.getRight ()); }} 

Aktualizujeme tiež tlačiť metóda tiež:

public void print (PrintStream os) {StringBuilder sb = nový StringBuilder (); traversePreOrder (sb, "", "", tento.strom); os.print (sb.toString ()); } 

Poďme si teda otestovať našu BinaryTreePrinter ešte raz:

Takže so všetkými výplňami a ukazovateľmi sa náš diagram pekne tvaroval.

Stále však máme niekoľko ďalších riadkov, ktorých sa môžeme zbaviť:

Keď sa pozrieme na diagram, stále existujú znaky na troch nesprávnych miestach:

  1. Stĺpec ďalších riadkov pod koreňovým uzlom
  2. Čiary navyše pod pravým podstromom
  3. Čiary navyše pod ľavým podstromom, ktorý nemá pravého súrodenca

5.3. Rôzne implementácie pre koreňové a podradené uzly

Na opravu ďalších čiar môžeme rozdeliť našu metódu posuvu. Jedno správanie použijeme na koreňový uzol a druhé na podradené uzly.

Poďme sa prispôsobiť traversePreOrder iba pre koreňový uzol:

public String traversePreOrder (root BinaryTreeModel) {if (root == null) {return ""; } StringBuilder sb = nový StringBuilder (); sb.append (root.getValue ()); Reťazec pointerRight = "└──"; Reťazec pointerLeft = (root.getRight ()! = Null)? "├──": "└──"; traverseNodes (sb, "", pointerLeft, root.getLeft (), root.getRight ()! = null); traverseNodes (sb, "", pointerRight, root.getRight (), false); vrátiť sb.toString (); } 

Ďalej vytvoríme ďalšiu metódu pre podradené uzly ako traverseNodes. Adodatočne pridáme nový parameter hasRightSibling správne implementovať predchádzajúce riadky:

public void traverseNodes (StringBuilder sb, vyplnenie reťazca, ukazovateľ reťazca, uzol BinaryTreeModel, boolean hasRightSibling) {if (node! = null) {sb.append ("\ n"); sb.append (polstrovanie); sb.append (ukazovateľ); sb.append (node.getValue ()); StringBuilder paddingBuilder = nový StringBuilder (výplň); if (hasRightSibling) {paddingBuilder.append ("│"); } else {paddingBuilder.append (""); } Reťazec paddingForBoth = paddingBuilder.toString (); Reťazec pointerRight = "└──"; Reťazec pointerLeft = (node.getRight ()! = Null)? "├──": "└──"; traverseNodes (sb, paddingForBoth, pointerLeft, node.getLeft (), node.getRight ()! = null); traverseNodes (sb, paddingForBoth, pointerRight, node.getRight (), false); }} 

Potrebujeme tiež malú zmenu v našom tlačiť metóda:

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

Nakoniec sa náš diagram sformoval do pekného tvaru s čistým výstupom:

6. Záver

V tomto článku sme sa naučili jednoduchý a praktický spôsob, ako vytlačiť Binárny strom v Jave.

Všetky príklady tohto článku a ďalších testovacích prípadov sú k dispozícii na GitHub.


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