streamalism.org

1. Uvod

Ispis je vrlo uobičajena tehnika vizualizacije za strukture podataka. Ipak, drveće može biti nezgodno zbog njihove hijerarhijske prirode.

U ovom uputstvu naučit ćemo neke tehnike ispisa za binarno drveće na Javi.

2. Dijagrami stabla

Unatoč ograničenjima crtanja sa samo znakovima na konzoli, postoji mnogo različitih oblika dijagrama koji predstavljaju strukture stabala. Odabir jednog od njih najviše ovisi o veličini i ravnoteži stabla.

Pogledajmo neke od mogućih vrsta dijagrama koje možemo ispisati:

Ali, objasnit ćemo jedan praktični, koji je također lakše implementirati. Uzimajući u obzir smjer u kojem drvo raste, možemo ga nazvati a vodoravno stablo:

Jer vodoravno stablo teče uvijek u istom smjeru kao i tekst, imamo neke prednosti odabira vodoravnog dijagrama u odnosu na druge:

1. Možemo vizualizirati i velika i neuravnotežena stabla
2. Duljina vrijednosti čvora ne utječe na strukturu prikaza
3. Puno je jednostavnije za provedbu

Stoga ćemo ići s vodoravnim dijagramom i u sljedećim odjeljcima implementirati jednostavnu klasu binarnih stabala.

3. Binarni model stabla

Prije svega, trebali bismo modelirati osnovno binarno stablo što možemo učiniti sa samo nekoliko redaka koda.

Definirajmo jednostavan BinaryTreeModel razred:

javna klasa BinaryTreeModel {vrijednost privatnog objekta; privatni BinaryTreeModel lijevo; privatni BinaryTreeModel desno; javni BinaryTreeModel (vrijednost objekta) {this.value = value; } // standardni getteri i postavljači} 

4. Uzorci podataka o ispitivanju

Prije nego što započnemo s implementacijom našeg binarnog stabla, moramo stvoriti neke uzorke podataka kako bismo postupno testirali našu vizualizaciju:

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

5. Binarni printer za stabla

Svakako, potreban nam je zaseban razred da bismo zadržali svoje BinaryTreeModel čisto zbog principa jedinstvene odgovornosti.

Sada bismo mogli koristiti obrazac posjetitelja tako da stablo obrađuje hijerarhiju, a naš pisač samo upravlja ispisom. Ali u ovom ćemo ih priručniku držati na okupu kako bi bilo jednostavnije.

Dakle, definiramo klasu nazvanu BinaryTreePrinter i počnite ga provoditi.

5.1. Prelazak s narudžbe unaprijed

Uzimajući u obzir naš vodoravni dijagram, da bismo ga ispravno ispisali, možemo jednostavno započeti pomoću predbilježba prijelaz.

Slijedom toga, da bismo izvršili prevrtanje unaprijed narudžbe, moramo implementirati rekurzivnu metodu koja prvo posjeti korijenski čvor, zatim lijevo podstablo i na kraju desno podstablo.

Definirajmo metodu za prelazak našeg stabla:

javna praznina traversePreOrder (StringBuilder sb, čvor BinaryTreeModel) {if (čvor! = null) {sb.append (node.getValue ()); sb.append ("\ n"); traversePreOrder (sb, node.getLeft ()); traversePreOrder (sb, node.getRight ()); }} 

Dalje, definirajmo našu metodu ispisa:

javni void ispis (PrintStream os) {StringBuilder sb = novi StringBuilder (); traversePreOrder (sb, this.tree); os.print (sb.toString ()); } 

Stoga možemo jednostavno ispisati naše testno stablo:

novi BinaryTreePrinter (korijen) .print (System.out); 

Rezultat će biti popis čvorova stabla u obrnutom redoslijedu:

korijenski čvor1 čvor3 čvor7 čvor8 čvor9 čvor4 čvor2 čvor5 čvor6 

5.2. Dodavanje rubova stabla

Da bismo pravilno postavili naš dijagram, koristimo tri vrste znakova "├──", "└──" i "│" za vizualizaciju čvorova. Prva dva su za pokazivače, a posljednji je ispuniti rubove i povezati pokazivače.

Ažurirajmo naš traversePreOrder metoda, dodajte dva parametra kao podmetanje i pokazivač, i upotrijebite znakove:

javna praznina traversePreOrder (StringBuilder sb, dodavanje niza, pokazivač niza, čvor BinaryTreeModel) {if (čvor! = null) {sb.append (padding); sb.append (pokazivač); sb.append (node.getValue ()); sb.append ("\ n"); StringBuilder paddingBuilder = novi StringBuilder (padding); paddingBuilder.append ("│"); Niz paddingForBoth = paddingBuilder.toString (); String pointerForRight = "└──"; String pointerForLeft = (node.getRight ()! = Null)? "├──": "└──"; traversePreOrder (sb, paddingForBoth, pointerForLeft, node.getLeft ()); traversePreOrder (sb, paddingForBoth, pointerForRight, node.getRight ()); }} 

Također, ažuriramo ispis metoda također:

javni void ispis (PrintStream os) {StringBuilder sb = novi StringBuilder (); traversePreOrder (sb, "", "", this.tree); os.print (sb.toString ()); } 

Pa, testirajmo naše BinaryTreePrinter opet:

Dakle, sa svim ulošcima i pokazivačima, naš se dijagram lijepo oblikovao.

Međutim, još uvijek imamo nekoliko dodatnih linija kojih se možemo riješiti:

Dok pregledamo dijagram, još uvijek ima likova na tri pogrešna mjesta:

1. Stupac dodatnih crta ispod korijenskog čvora
2. Dodatne crte ispod desnog podstabla
3. Dodatne crte ispod lijevog podstabla koje nema desnog brata ili sestru

5.3. Različite implementacije za korijenske i podređene čvorove

Kako bismo popravili dodatne crte, možemo podijeliti našu metodu prijelaza. Primijenit ćemo jedno ponašanje na korijenski čvor, a drugo na podređene čvorove.

Prilagodimo traversePreOrder samo za korijenski čvor:

javni niz traversePreOrder (korijen BinaryTreeModel) {if (root == null) {return ""; } StringBuilder sb = novi StringBuilder (); sb.append (root.getValue ()); String pointerRight = "└──"; Niz pointerLeft = (root.getRight ()! = Null)? "├──": "└──"; traverseNodes (sb, "", pointerLeft, root.getLeft (), root.getRight ()! = null); traverseNodes (sb, "", pointerRight, root.getRight (), false); vratiti sb.toString (); } 

Zatim ćemo stvoriti drugu metodu za podređene čvorove kao poprečni čvorovi. Adodatno ćemo dodati novi parametar hasRightSibling kako bismo pravilno implementirali prethodne retke:

javni void traverseNodes (StringBuilder sb, Padding, String pointer, BinaryTreeModel čvor, boolean hasRightSibling) {if (node! = null) {sb.append ("\ n"); sb.append (podmetač); sb.append (pokazivač); sb.append (node.getValue ()); StringBuilder paddingBuilder = novi StringBuilder (padding); if (hasRightSibling) {paddingBuilder.append ("│"); } else {paddingBuilder.append (""); } Niz paddingForBoth = paddingBuilder.toString (); String pointerRight = "└──"; Niz pointerLeft = (node.getRight ()! = Null)? "├──": "└──"; traverseNodes (sb, paddingForBoth, pointerLeft, node.getLeft (), node.getRight ()! = null); traverseNodes (sb, paddingForBoth, pointerRight, node.getRight (), false); }} 

Također, trebamo malu promjenu u našem ispis metoda:

javni void ispis (PrintStream os) {os.print (traversePreOrder (stablo)); } 

Napokon, naš se dijagram oblikovao u lijep oblik s čistim izlazom:

6. Zaključak

U ovom članku, naučili smo jednostavan i praktičan način ispisa binarnog stabla na Javi.

Svi primjeri ovog članka i dodatni testovi dostupni su na GitHubu.