streamalism.org

1. Uvod

U ovom ćemo članku pokriti provedbu binarnog stabla u Javi.

Radi ovog članka, koristit ćemo sortirano binarno stablo koje će sadržavati int vrijednosti.

2. Binarno stablo

Binarno stablo je rekurzivna struktura podataka u kojoj svaki čvor može imati najviše 2 djece.

Uobičajena vrsta binarnog stabla je binarno stablo pretraživanja, u kojem svaki čvor ima vrijednost koja je veća ili jednaka vrijednostima čvorova u lijevom podstablu, a manja ili jednaka vrijednostima čvora u desnom pod-stablu. stablo.

Evo kratkog vizualnog prikaza ove vrste binarnog stabla:

Za provedbu ćemo upotrijebiti pomoćni uređaj Čvor razred koji će pohraniti int vrijednosti i vodite računa o svakom djetetu:

class Node {int vrijednost; Čvor lijevo; Čvor desno; Čvor (int vrijednost) {this.value = vrijednost; desno = null; lijevo = null; }}

Zatim, dodajmo početni čvor našeg stabla, koji se obično naziva korijen:

javna klasa BinaryTree {Node root; // ...}

3. Zajedničke operacije

Sada, pogledajmo najčešće operacije koje možemo izvesti na binarnom stablu.

3.1. Umetanje elemenata

Prva operacija koju ćemo pokriti je umetanje novih čvorova.

Prvi, moramo pronaći mjesto na kojem želimo dodati novi čvor kako bi drvo bilo sortirano. Slijedit ćemo ova pravila počevši od korijenskog čvora:

• ako je vrijednost novog čvora niža od vrijednosti trenutnog čvora, idemo na lijevo podređeno mjesto
• ako je vrijednost novog čvora veća od trenutnog čvora, idemo na pravo dijete
• kada je trenutni čvor null, dospjeli smo do čvora lista i u taj položaj možemo umetnuti novi čvor

Prvo ćemo stvoriti rekurzivnu metodu za umetanje:

private Node addRecursive (Node current, int value) {if (current == null) {return new Node (value); } if (vrijednost current.value) {current.right = addRecursive (current.right, value); } else {// vrijednost već postoji return current; } povratna struja; }

Zatim ćemo stvoriti javnu metodu koja započinje rekurziju iz korijen čvor:

javna void add (int vrijednost) {root = addRecursive (root, value); }

Sada da vidimo kako možemo koristiti ovu metodu za stvaranje stabla iz našeg primjera:

privatno BinaryTree createBinaryTree () {BinaryTree bt = novo BinaryTree (); bt.add (6); bt.add (4); bt.add (8); bt.add (3); bt.add (5); bt.add (7); bt.add (9); povrat bt; }

3.2. Pronalaženje elementa

Dodajmo sada metodu za provjeru sadrži li stablo određenu vrijednost.

Kao i prije, prvo ćemo stvoriti rekurzivnu metodu koja prelazi stablo:

private boolean containsNodeRecursive (Node current, int value) {if (current == null) {return false; } if (value == current.value) {return true; } povratna vrijednost <current.value? containsNodeRecursive (current.left, value): containsNodeRecursive (current.right, value); }

Ovdje tražimo vrijednost uspoređujući je s vrijednošću u trenutnom čvoru, a zatim nastavljamo u lijevom ili desnom podređenom ovisno o tome.

Dalje, kreirajmo javnu metodu koja započinje s korijen:

javna logička vrijednost sadržiNode (int vrijednost) {return containsNodeRecursive (korijen, vrijednost); }

Sada, kreirajmo jednostavan test kako bismo provjerili sadrži li stablo stvarno umetnute elemente:

@Test javna praznina danaABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.contensNode (6)); assertTrue (bt.contensNode (4)); assertFalse (bt.contensNode (1)); }

Svi dodani čvorovi trebaju biti sadržani u stablu.

3.3. Brisanje elementa

Sljedeća uobičajena operacija je brisanje čvora sa stabla.

Prvo, moramo pronaći čvor za brisanje na sličan način kao i prije:

private Node deleteRecursive (Node current, int value) {if (current == null) {return null; } if (value == current.value) {// Čvor za brisanje pronađeno // ... ovdje će ići kod za brisanje čvora} if (value <current.value) {current.left = deleteRecursive (current.left, vrijednost); povratna struja; } current.right = deleteRecursive (current.right, vrijednost); povratna struja; }

Jednom kada pronađemo čvor za brisanje, postoje 3 glavna različita slučaja:

• čvor nema djece - ovo je najjednostavniji slučaj; samo moramo zamijeniti ovaj čvor s null u svom nadređenom čvoru
• čvor ima točno jedno dijete - u nadređenom čvoru zamjenjujemo ovaj čvor s jedinim djetetom.
• čvor ima dvoje djece - ovo je najsloženiji slučaj jer zahtijeva reorganizaciju stabla

Pogledajmo kako možemo implementirati prvi slučaj kada je čvor lisni čvor:

if (current.left == null && current.right == null) {return null; }

Sada nastavimo sa slučajem kada čvor ima jedno dijete:

if (current.right == null) {return current.left; } if (current.left == null) {return current.right; }

Evo, vraćamo ne-null dijete kako bi se mogao dodijeliti nadređenom čvoru.

Konačno, moramo riješiti slučaj kada čvor ima dvoje djece.

Prvo, moramo pronaći čvor koji će zamijeniti izbrisani čvor. Upotrijebit ćemo najmanji čvor čvora za brisanje desnog podstabla za brisanje:

private int findSmallestValue (korijen čvora) {return root.left == null? root.value: findSmallestValue (root.left); }

Zatim čvoru dodijelimo najmanju vrijednost za brisanje, a nakon toga ćemo je izbrisati iz desnog podstabla:

int najmanja vrijednost = pronađi najmanju vrijednost (trenutno.desno); current.value = najmanjaVrijednost; current.right = deleteRecursive (current.right, najmanja vrijednost); povratna struja;

Na kraju, kreirajmo javnu metodu koja započinje brisanje iz datoteke korijen:

javna void delete (int vrijednost) {root = deleteRecursive (root, value); }

Sada provjerimo radi li brisanje prema očekivanjima:

@Test javna praznina danaABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.contensNode (9)); bt.brisati (9); assertFalse (bt.contensNode (9)); }

4. Prelazak stablom

U ovom ćemo odjeljku vidjeti različite načine obilaženja stabla, detaljno pokrivajući pretraživanja u dubinu i u širinu.

Upotrijebit ćemo isto stablo kao i prije, a za svaki slučaj pokazat ćemo redoslijed prelaska.

4.1. Dubina-prvo pretraživanje

Dubinsko traženje je vrsta prijelaza koja ulazi što je moguće dublje u svako dijete prije istraživanja sljedećeg brata ili sestre.

Postoji nekoliko načina za dubinsko pretraživanje: redoslijedom, predbilježbom i naknadnim redoslijedom.

Prijelaz po redoslijedu sastoji se od najprije posjećivanja lijevog podstabla, zatim korijenskog čvora i na kraju desnog podstabla:

javna praznina traverseInOrder (čvor čvora) {if (čvor! = null) {traverseInOrder (node.left); System.out.print ("" + node.value); traverseInOrder (node.desno); }}

Ako pozovemo ovu metodu, izlaz konzole prikazat će redoslijed obilaženja:

3 4 5 6 7 8 9

Preokret s narudžbom prvo posjeti korijenski čvor, zatim lijevo podstablo i na kraju desno podstablo:

javna praznina traversePreOrder (čvor čvora) {if (čvor! = null) {System.out.print ("" + node.value); traversePreOrder (node.left); traversePreOrder (node.desno); }}

I provjerimo zaokret predbilježbe u izlazu konzole:

6 4 3 5 8 7 9

Prijelaz nakon narudžbe posjećuje lijevo podstablo, desno podstablo i korijenski čvor na kraju:

javna praznina traversePostOrder (čvor čvora) {if (čvor! = null) {traversePostOrder (node.left); traversePostOrder (node.desno); System.out.print ("" + node.value); }}

Evo čvorova u post-redoslijedu:

3 5 4 7 9 8 6

4.2. Širina-prvo pretraživanje

Ovo je još jedna uobičajena vrsta prijelaza koja posjeti sve čvorove razine prije prelaska na sljedeću razinu.

Ova vrsta prelaska naziva se i poredak po razini i obilazi sve razine stabla počevši od korijena i slijeva udesno.

Za provedbu ćemo upotrijebiti a Red držati čvorove sa svake razine redom. Izdvojit ćemo svaki čvor s popisa, ispisati njegove vrijednosti, a zatim u redoslijed dodati njegove podređene dijelove:

javna praznina traverseLevelOrder () {if (root == null) {return; } Čvorovi u redu = novi LinkedList (); nodes.add (korijen); while (! nodes.isEmpty ()) {Node node = nodes.remove (); System.out.print ("" + node.value); if (node.left! = null) {nodes.add (node.left); } if (node.right! = null) {nodes.add (node.right); }}}

U tom će slučaju redoslijed čvorova biti:

6 4 8 3 5 7 9

5. Zaključak

U ovom smo članku vidjeli kako implementirati razvrstano binarno stablo u Javi i njegove najčešće operacije.

Potpuni izvorni kod za primjere dostupan je na GitHubu.