streamalism.org

1. Bemutatkozás

A nyomtatás az adatstruktúrák nagyon gyakori megjelenítési technikája. Hierarchikus jellegük miatt bonyolult lehet a fák esetében.

Ebben az oktatóanyagban megtanulunk néhány nyomtatási technikát a Java bináris fák számára.

2. Fa diagramok

Annak ellenére, hogy a konzolon csak karaktereket kell rajzolni, sokféle diagram alakzat képviseli a fa struktúrákat. Az egyik kiválasztása leginkább a fa méretétől és egyensúlyától függ.

Vessen egy pillantást néhány lehetséges diagramtípusra, amelyeket kinyomtathatunk:

De elmagyarázunk egy gyakorlati megoldást, amelyet szintén könnyebb megvalósítani. Figyelembe véve a fa növekedési irányát, a-nak nevezhetjük vízszintes fa:

Mivel a vízszintes fa mindig ugyanabban az irányban folyik, mint a szöveg, van néhány előnyünk, ha a horizontális diagramot választjuk másokhoz képest:

1. Megjeleníthetjük a nagy és kiegyensúlyozatlan fákat is
2. A csomópontértékek hossza nem befolyásolja a kijelző szerkezetét
3. Sokkal könnyebb megvalósítani

Ezért folytatjuk a vízszintes diagramot, és a következő szakaszokban egy egyszerű bináris fa nyomtató osztályt valósítunk meg.

3. Bináris fa modell

Mindenekelőtt meg kell modelleznünk egy alap bináris fát, amelyet csak néhány kódsorral tehetünk meg.

Határozzunk meg egy egyszerűt BinaryTreeModel osztály:

public class BinaryTreeModel {private Object value; private BinaryTreeModel left; privát BinaryTreeModel jog; public BinaryTreeModel (Object value) {this.érték = érték; } // szokásos mérőeszközök és beállítók} 

4. Minta tesztadatok

Mielőtt elkezdenénk a bináris fa nyomtatónkat bevezetni, létre kell hoznunk néhány mintaadatot a vizualizáció fokozatos teszteléséhez:

BinaryTreeModel root = új BinaryTreeModel ("root"); BinaryTreeModel node1 = új BinaryTreeModel ("node1"); BinaryTreeModel node2 = új BinaryTreeModel ("node2"); root.setLeft (csomópont1); root.setRight (csomópont2); BinaryTreeModel node3 = új BinaryTreeModel ("node3"); BinaryTreeModel node4 = új BinaryTreeModel ("node4"); node1.setLeft (node3); node1.setRight (4. csomópont); node2.setLeft (új BinaryTreeModel ("node5")); node2.setRight (új BinaryTreeModel ("node6")); BinaryTreeModel node7 = új BinaryTreeModel ("node7"); node3.setLeft (csomópont7); node7.setLeft (új BinaryTreeModel ("node8")); node7.setRight (új BinaryTreeModel ("node9"));

5. Bináris fa nyomtató

Minden bizonnyal külön osztályra van szükségünk, hogy megtartsuk a sajátunkat BinaryTreeModel tiszta az Egységes Felelősség Elve érdekében.

Most használhatnánk a Látogató mintát, hogy a fa kezelje a hierarchiát, a nyomtatónk pedig csak a nyomtatást. De ehhez az oktatóanyaghoz összetartjuk őket az egyszerűség érdekében.

Így definiálunk egy nevű osztályt BinaryTreePrinter és kezdje el végrehajtani.

5.1. Pre-Order Traversal

Figyelembe véve a vízszintes diagramunkat, annak megfelelő nyomtatásához egyszerű kezdést tehetünk a használatával előrendelés bejárása.

Következésképpen, az előrendelés bejárásához végre kell hajtanunk egy rekurzív módszert, amely először meglátogatja a gyökércsomópontot, majd a bal alfa, végül a jobb alfa.

Határozzunk meg egy módszert a fánk bejárására:

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

Ezután határozzuk meg a nyomtatási módszerünket:

public void print (PrintStream os) {StringBuilder sb = new StringBuilder (); traversePreOrder (sb, ez a fa); os.print (sb.toString ()); } 

Így egyszerűen kinyomtathatjuk a tesztfánkat:

új BinaryTreePrinter (root) .print (System.out); 

A kimenet a fák csomópontjainak listája lesz áthaladó sorrendben:

gyökércsomó1 csomópont3 csomópont7 csomópont8 csomópont9 csomópont4 csomópont2 csomópont5 csomópont6 

5.2. Fa szélek hozzáadása

Diagramunk megfelelő beállításához háromféle karaktert használunk: „├──”, „└──” és „│” a csomópontok megjelenítéséhez. Az első kettő a mutatókra vonatkozik, az utolsó pedig az élek kitöltésére és a mutatók összekapcsolására szolgál.

Frissítsük a traversePreOrder módszerrel adjunk hozzá két paramétert párnázás és mutató, és használja a következő karaktereket:

public void traversePreOrder (StringBuilder sb, String padding, String pointer, BinaryTreeModel node) {if (csomópont! = null) {sb.append (kitöltés); sb.append (mutató); sb.append (node.getValue ()); sb.append ("\ n"); StringBuilder paddingBuilder = new StringBuilder (padding); 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 ()); }} 

Továbbá frissítjük nyomtatás módszer is:

public void print (PrintStream os) {StringBuilder sb = new StringBuilder (); traversePreOrder (sb, "", "", ez a fa); os.print (sb.toString ()); } 

Tehát, teszteljük BinaryTreePrinter újra:

Így az összes párnázással és mutatóval az ábra jól formálódott.

Van azonban még néhány extra sorunk, amelyektől megszabadulhatunk:

Ahogy áttekintjük a diagramot, még mindig vannak karakterek három rossz helyen:

1. Az extra sorok oszlopa a gyökércsomópont alatt
2. Az extra sorok a jobb alfa alatt
3. Az extra sorok a bal alfa alatt, amelynek nincs jobb testvére

5.3. Különböző megvalósítások a gyökér és a gyermek csomópontokhoz

Az extra vonalak rögzítése érdekében fel tudjuk osztani a travers módszerünket. Az egyik viselkedést a gyökércsomópontra, a másikat pedig a gyermekcsomópontokra alkalmazzuk.

Testre szabjuk traversePreOrder csak a gyökércsomópont esetében:

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

Ezután létrehozunk egy másik módszert a gyermek csomópontok számára traverseNodes. AEzenkívül hozzáadunk egy új paramétert hasRightSibling az előző sorok helyes végrehajtása:

public void traverseNodes (StringBuilder sb, String kitöltés, String pointer, BinaryTreeModel csomópont, logikai hasRightSibling) {if (csomópont! = null) {sb.append ("\ n"); sb.append (párnázás); sb.append (mutató); sb.append (node.getValue ()); StringBuilder paddingBuilder = new StringBuilder (padding); 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 (), hamis); }} 

Emellett szükségünk van egy kis változásra is nyomtatás módszer:

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

Végül diagramunk szép alakúra formálódott, tiszta kimenettel:

6. Következtetés

Ebben a cikkben, megtanultunk egy egyszerű és praktikus módszert a Java bináris fa kinyomtatására.

A cikk és a további tesztesetek összes példája elérhető a GitHub oldalon.