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:
- Vieme tiež vizualizovať veľké a nevyvážené stromy
- Dĺžka hodnôt uzlov nemá vplyv na štruktúru displeja
- 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:
- Stĺpec ďalších riadkov pod koreňovým uzlom
- Čiary navyše pod pravým podstromom
- Č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.