streamalism.org

1. Bemutatkozás

Ebben a cikkben egy bináris fa implementálását ismertetjük a Java-ban.

E cikk kedvéért egy rendezett bináris fát fogunk használni, amely tartalmazza int értékek.

2. bináris fa

A bináris fa egy rekurzív adatszerkezet, ahol minden csomópont legfeljebb 2 gyermeket vállalhat.

A bináris fa általános típusa a bináris keresőfa, amelyben minden csomópont értéke nagyobb vagy egyenlő a bal alfa csomópontértékeivel, és kisebb vagy egyenlő a jobb oldali alcsomópont csomópontértékeivel. fa.

Az alábbiakban bemutatunk egy ilyen típusú bináris fát:

A megvalósításhoz egy segédprogramot fogunk használni Csomópont osztály, amely tárolni fog int értékeket, és tartson hivatkozást minden gyermekre:

class Node {int érték; Csomópont maradt; Csomópont jobbra; Csomópont (int érték) {this.value = érték; right = null; bal = null; }}

Ezután tegyük hozzá a fánk kezdő csomópontját, amelyet általában úgy hívnak gyökér:

public class BinaryTree {Csomópont gyökere; // ...}

3. Közös műveletek

Most nézzük meg a leggyakoribb műveleteket, amelyeket egy bináris fán elvégezhetünk.

3.1. Elemek beszúrása

Az első művelet, amelyre kiterjedünk, új csomópontok beillesztése.

Első, meg kell találnunk azt a helyet, ahová új csomópontot szeretnénk felvenni, hogy a fa rendezve legyen. Ezeket a szabályokat a gyökércsomóponttól kezdve követjük:

• ha az új csomópont értéke alacsonyabb, mint a jelenlegi csomópont értéke, akkor a bal gyermekhez megyünk
• ha az új csomópont értéke nagyobb, mint a jelenlegi csomópont értéke, akkor a megfelelő gyermekhez megyünk
• amikor az aktuális csomópont nulla, elértünk egy levélcsomópontot, és ebbe a helyzetbe helyezhetjük be az új csomópontot

Először létrehozunk egy rekurzív módszert a beszúrás elvégzésére:

private Node addRecursive (Node current, int value) {if (current == null) {return new Node (value); } if (value current.value) {current.right = addRecursive (current.right, value); } else {// érték már létezik visszatérő áram; } visszatérő áram; }

Ezután létrehozzuk a nyilvános módszert, amely a rekurziót a gyökér csomópont:

public void add (int érték) {root = addRecursive (root, érték); }

Most nézzük meg, hogyan használhatjuk ezt a módszert a fa létrehozására a példánkból:

privát BinaryTree createBinaryTree () {BinaryTree bt = new BinaryTree (); bt. (6); bt.add (4); bt. (8); bt.add (3); bt. (5); bt. (7); bt.add (9); return bt; }

3.2. Elem megtalálása

Most adjunk hozzá egy módszert annak ellenőrzésére, hogy a fa tartalmaz-e meghatározott értéket.

Mint korábban, először létrehozunk egy rekurzív módszert, amely bejárja a fát:

privát logikai érték tartalmazzaNodeRecursive (Node current, int value) {if (current == null) {return false; } if (érték == aktuális.érték) {return true; } return value <aktuális.érték? containsNodeRecursive (current.lft, value): tartalmazzaNodeRecursive (current.right, value); }

Itt az értéket úgy keressük, hogy összehasonlítjuk az aktuális csomópont értékével, majd ennek függvényében folytatjuk a bal vagy a jobb gyermekben.

Ezután hozzuk létre a nyilvános módszert, amely a gyökér:

nyilvános logikai érték tartalmazzaNode (int érték) {return tartalmazNodeRecursive (gyökér, érték); }

Most hozzunk létre egy egyszerű tesztet annak ellenőrzésére, hogy a fa valóban tartalmazza-e a beillesztett elemeket:

@Test public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.containNode (6)); assertTrue (bt.containNode (4)); assertFalse (bt.containNode (1)); }

Az összes hozzáadott csomópontnak tartalmaznia kell a fát.

3.3. Elem törlése

Egy másik gyakori művelet egy csomópont törlése a fáról.

Először is meg kell találnunk a törlendő csomópontot hasonló módon, mint korábban:

privát csomópont deleteRecursive (Node current, int value) {if (current == null) {return null; } if (érték == aktuális.érték) {// Csomópont a megtalált törléséhez // ... a csomópont törléséhez szükséges kód ide kerül} érték); visszatérő áram; } current.right = deleteRecursive (current.right, value); visszatérő áram; }

Miután megtaláljuk a törölni kívánt csomópontot, három fő különbség van:

• egy csomópontnak nincs gyermeke - ez a legegyszerűbb eset; csak le kell cserélnünk ezt a csomópontot nulla szülőcsomópontjában
• egy csomópontnak pontosan egy gyermeke van - a szülőcsomópontban ezt a csomópontot kicseréljük egyetlen gyermekére.
• egy csomópontnak két gyermeke van - ez a legösszetettebb eset, mert egy fa átszervezését igényli

Lássuk, hogyan tudjuk megvalósítani az első esetet, amikor a csomópont levélcsomópont:

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

Most folytassuk azt az esetet, amikor a csomópontnak egy gyermeke van:

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

Itt adjuk vissza a nem semleges gyermek, így hozzárendelhető a szülőcsomóponthoz.

Végül kezelnünk kell azt az esetet, amikor a csomópontnak két gyermeke van.

Először meg kell találnunk azt a csomópontot, amely felváltja a törölt csomópontot. A törlendő csomópont legkisebb csomópontját fogjuk használni a jobb alfában:

private int findSmallestValue (Node root) {return root.left == null? root.value: findSmallestValue (root.bal); }

Ezután hozzárendeljük a legkisebb értéket a törlendő csomóponthoz, majd ezt követően töröljük a jobb alfáról:

int legkisebb érték = findSmallestValue (jelenlegi.jobb); current.value = legkisebb érték; current.right = deleteRecursive (current.right, legkisebbValue); visszatérő áram;

Végül hozzuk létre a nyilvános módszert, amely elindítja a törlést a gyökér:

public void törlés (int érték) {root = deleteRecursive (root, érték); }

Most ellenőrizzük, hogy a törlés a várt módon működik-e:

@Test public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.containNode (9)); bt.delete (9); assertFalse (bt.containsNode (9)); }

4. A fa bejárása

Ebben a szakaszban a fa áthaladásának különböző módjait fogjuk megismerni, részletesen bemutatva a mélység és az első szélesség kereséseket.

Ugyanazt a fát fogjuk használni, amelyet korábban használtunk, és minden esetben megmutatjuk a bejárási sorrendet.

4.1. Mélység-első keresés

A mélység-első keresés egyfajta bejárás, amely a lehető legnagyobb mértékben elmélyül minden gyermekben, mielőtt felfedezné a következő testvért.

A mélységi keresés végrehajtásának több módja van: megrendelés, előrendelés és utólagos megrendelés.

A rendezett bejárás abból áll, hogy először meglátogatja a bal alfa, majd a gyökércsomópontot, végül a jobb alfát:

public void traverseInOrder (Csomópont csomópont) {if (csomópont! = null) {traverseInOrder (csomópont.balra); System.out.print ("" + csomópont.érték); traverseInOrder (node.right); }}

Ha ezt a módszert hívjuk, a konzol kimenete a sorrendben történő bejárást mutatja:

3 4 5 6 7 8 9

Az előrendelés bejárása először a gyökércsomópontot, majd a bal és végül a jobb alfát keresi fel:

public void traversePreOrder (Csomópont csomópont) {if (csomópont! = null) {System.out.print ("" + csomópont.érték); traversePreOrder (node.balra); traversePreOrder (csomópont.jobb); }}

Ellenőrizzük az előrendelés bejárását a konzol kimenetében:

6 4 3 5 8 7 9

A megrendelés utáni bejárás meglátogatja a bal alfát, a jobb alfát és a gyökércsomópontot a végén:

public void traversePostOrder (Node node) {if (csomópont! = null) {traversePostOrder (node.left); traversePostOrder (csomópont.jobb); System.out.print ("" + csomópont.érték); }}

Íme a csomópontok utólagos sorrendben:

3 5 4 7 9 8 6

4.2. Szélesség-első keresés

Ez egy másik gyakori bejárási típus, amely meglátogatja a szint összes csomópontját, mielőtt a következő szintre lépne.

Ezt a fajta bejárást szint-sorrendnek is nevezik, és meglátogatja a fa minden szintjét a gyökértől kezdve, és balról jobbra.

A megvalósításhoz a Sor hogy az egyes szintek csomópontjai rendben legyenek. Minden csomópontot kivonunk a listából, kinyomtatjuk az értékeket, majd hozzáadjuk gyermekeit a sorhoz:

public void traverseLevelOrder () {if (root == null) {return; } Várakozási csomópontok = új LinkedList (); csomópontok.add (gyökér); while (! csomópontok.isEmpty ()) {Csomópont csomópont = csomópontok.eltávolítás (); System.out.print ("" + csomópont.érték); if (csomópont.balon! = null) {csomópontok.add (csomópont.balra); } if (csomópont.jobb! = null) {csomópontok.add (csomópont.jobb); }}}

Ebben az esetben a csomópontok sorrendje a következő lesz:

6 4 8 3 5 7 9

5. Következtetés

Ebben a cikkben azt láttuk, hogyan lehet egy rendezett bináris fát megvalósítani a Java-ban és annak leggyakoribb műveleteiben.

A példák teljes forráskódja elérhető a GitHub oldalon.