streamalism.org

1. Úvod

V tomto článku sa budeme venovať implementácii binárneho stromu v prostredí Java.

V záujme tohto článku použijeme triedený binárny strom, ktorý bude obsahovať int hodnoty.

2. Binárny strom

Binárny strom je rekurzívna dátová štruktúra, kde každý uzol môže mať najviac 2 deti.

Bežným typom binárneho stromu je binárny vyhľadávací strom, v ktorom má každý uzol hodnotu, ktorá je väčšia alebo rovná hodnotám uzla v ľavom pod strome a menšia alebo rovná hodnotám uzla v pravom pod strome strom.

Tu je rýchle vizuálne znázornenie tohto typu binárneho stromu:

Na implementáciu použijeme pomocný program Uzol trieda, ktorá bude skladovať int hodnoty a udržiavať odkaz na každé dieťa:

trieda Uzol {int hodnota; Uzol vľavo; Uzol vpravo; Uzol (int hodnota) {this.value = value; right = null; dolava = null; }}

Potom pridajme počiatočný uzol nášho stromu, ktorý sa zvyčajne nazýva koreň:

verejná trieda BinaryTree {root uzla; // ...}

3. Spoločné operácie

Teraz sa pozrime na najbežnejšie operácie, ktoré môžeme vykonať na binárnom strome.

3.1. Vkladanie prvkov

Prvou operáciou, ktorú sa budeme zaoberať, je vkladanie nových uzlov.

Najprv, musíme nájsť miesto, kam chceme pridať nový uzol, aby bol strom zoradený. Budeme sa riadiť týmito pravidlami od koreňového uzla:

• ak je hodnota nového uzla nižšia ako hodnota aktuálneho uzla, ideme k ľavému dieťaťu
• ak je hodnota nového uzla väčšia ako hodnota aktuálneho uzla, ideme na správne dieťa
• keď je aktuálny uzol nulový, dosiahli sme listový uzol a môžeme vložiť nový uzol na túto pozíciu

Najskôr vytvoríme rekurzívnu metódu vloženia:

private Node addRecursive (Node current, int value) {if (current == null) {return new Node (value); } if (hodnota current.value) {current.right = addRecursive (current.right, value); } else {// hodnota uz existuje vratit aktualne; } vratny prud; }

Ďalej vytvoríme verejnú metódu, ktorá spustí rekurziu z koreň uzol:

public void add (int hodnota) {root = addRecursive (root, value); }

Teraz sa pozrime, ako môžeme pomocou tejto metódy vytvoriť strom z nášho príkladu:

private BinaryTree createBinaryTree () {BinaryTree bt = nový BinaryTree (); bt.add (6); bt.add (4); bt.add (8); bt.add (3); bt.add (5); bt.add (7); bt.add (9); návrat bt; }

3.2. Nájdenie prvku

Teraz pridajme metódu na kontrolu, či strom obsahuje konkrétnu hodnotu.

Rovnako ako predtým, najskôr vytvoríme rekurzívnu metódu, ktorá prechádza stromom:

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

Tu hľadáme hodnotu tak, že ju porovnáme s hodnotou v aktuálnom uzle. Potom podľa toho pokračujeme v ľavom alebo pravom potomku.

Ďalej vytvoríme verejnú metódu, ktorá začína od koreň:

public boolean containsNode (int value) {return containsNodeRecursive (root, value); }

Teraz vytvorme jednoduchý test na overenie, či strom obsahuje vložené prvky:

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

Všetky pridané uzly by mali byť obsiahnuté v strome.

3.3. Odstraňuje sa prvok

Ďalšou bežnou operáciou je odstránenie uzla zo stromu.

Najskôr musíme nájsť uzol, ktorý sa má vymazať, podobným spôsobom ako predtým:

private Node deleteRecursive (Node current, int value) {if (current == null) {return null; } if (hodnota == current.value) {// Uzol na odstránenie nájdeného // ... kód na odstránenie uzla sa presunie sem} if (value <current.value) {current.left = deleteRecursive (current.left, hodnota); spätný prúd; } current.right = deleteRecursive (current.right, value); spätný prúd; }

Keď nájdeme uzol, ktorý sa má odstrániť, existujú 3 hlavné rôzne prípady:

• uzol nemá deti - toto je najjednoduchší prípad; tento uzol musíme nahradiť nulový v jeho nadradenom uzle
• uzol má presne jedno dieťa - v nadradenom uzle nahradíme tento uzol jeho jediným potomkom.
• uzol má dve deti - toto je najkomplexnejší prípad, pretože vyžaduje reorganizáciu stromu

Pozrime sa, ako môžeme implementovať prvý prípad, keď je uzol listový uzol:

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

Teraz pokračujme v prípade, keď má uzol jedno dieťa:

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

Tu vraciame nenulový dieťa, aby ho bolo možné priradiť k nadradenému uzlu.

Nakoniec musíme zvládnuť prípad, keď má uzol dve deti.

Najprv musíme nájsť uzol, ktorý nahradí vymazaný uzol. Použijeme najmenší uzol uzla, ktorý sa má vymazať, pravý podstrom:

private int findSmallestValue (koreň uzla) {návrat root.left == null? root.value: findSmallestValue (root.left); }

Potom priradíme uzlu najmenšiu hodnotu na odstránenie a potom ju odstránime z pravého podstromu:

int najmenšiaHodnota = findSmallestValue (current.right); current.value = najmenšiaHodnota; current.right = deleteRecursive (current.right, smallerValue); spätný prúd;

Na záver vytvoríme verejnú metódu, ktorá spustí mazanie z koreň:

public void delete (int hodnota) {root = deleteRecursive (root, value); }

Teraz skontrolujeme, či odstránenie funguje podľa očakávaní:

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

4. Traverzovanie po strome

V tejto časti uvidíme rôzne spôsoby prechádzania stromom, ktoré podrobne pokrývajú vyhľadávania v hĺbke a šírke.

Použijeme rovnaký strom, aký sme použili predtým, a pre každý prípad ukážeme poradie prechodu.

4.1. Vyhľadávanie do hĺbky

Vyhľadávanie do hĺbky je typ prechodu, ktorý ide u každého dieťaťa čo najhlbšie, než preskúmate ďalšieho súrodenca.

Existuje niekoľko spôsobov, ako vykonať hĺbkové vyhľadávanie: v poradí, predobjednávka a poobjednávka.

Traverz v poradí pozostáva z prvej návštevy ľavého podstromu, potom koreňového uzla a nakoniec pravého podstromu:

public void traverseInOrder (uzol uzla) {if (uzol! = null) {traverseInOrder (node.left); System.out.print ("" + hodnota uzla); traverseInOrder (node.right); }}

Ak zavoláme túto metódu, výstup z konzoly zobrazí prechod v poradí:

3 4 5 6 7 8 9

Traverzia predobjednávky najskôr navštívi koreňový uzol, potom ľavý podstrom a nakoniec pravý podstrom:

public void traversePreOrder (uzol uzla) {if (uzol! = null) {System.out.print ("" + uzol.hodnota); traversePreOrder (node.left); traversePreOrder (node.right); }}

Poďme skontrolovať predobjednávku vo výstupe z konzoly:

6 4 3 5 8 7 9

Traverzálna objednávka navštívi ľavý podstrom, pravý podstrom a koreňový uzol na konci:

public void traversePostOrder (uzol uzla) {if (uzol! = null) {traversePostOrder (node.left); traversePostOrder (node.right); System.out.print ("" + hodnota uzla); }}

Tu sú uzly v objednávke:

3 5 4 7 9 8 6

4.2. Šírka - prvé vyhľadávanie

Toto je ďalší bežný typ prechodu, ktorý navštívi všetky uzly úrovne pred prechodom na ďalšiu úroveň.

Tento druh prechodu sa tiež nazýva usporiadanie úrovní a navštevuje všetky úrovne stromu počnúc od koreňa a zľava doprava.

Na implementáciu použijeme a Fronta aby boli uzly z každej úrovne v poriadku. Extrahujeme každý uzol zo zoznamu, vytlačíme jeho hodnoty a potom do fronty pridáme jeho deti:

public void traverseLevelOrder () {if (root == null) {return; } Uzly frontu = nový LinkedList (); node.add (root); 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); }}}

V takom prípade bude poradie uzlov:

6 4 8 3 5 7 9

5. Záver

V tomto článku sme videli, ako implementovať triedený binárny strom v prostredí Java a jeho najbežnejšie operácie.

Celý zdrojový kód príkladov je k dispozícii na GitHub.