Implementering av et binært tre i Java

1. Introduksjon

I denne artikkelen vil vi dekke implementeringen av et binært tre i Java.

Av hensyn til denne artikkelen, Vi bruker et sortert binært tre som inneholder int verdier.

2. Binært tre

Et binært tre er en rekursiv datastruktur der hver node kan ha to barn på det meste.

En vanlig type binært tre er et binært søketre, der hver node har en verdi som er større enn eller lik nodeverdiene i det venstre sub-treet, og mindre enn eller lik nodeverdiene i høyre sub- tre.

Her er en rask visuell fremstilling av denne typen binære tre:

For implementeringen vil vi bruke en hjelpestøtte Node klasse som vil lagre int verdier og hold en referanse til hvert barn:

klasse Node {int-verdi; Node igjen; Node høyre; Node (int-verdi) {this.value = verdi; høyre = null; venstre = null; }}

La oss deretter legge til startnoden til treet vårt, vanligvis kalt rot:

offentlig klasse BinaryTree {Node root; // ...}

3. Vanlige operasjoner

La oss nå se de vanligste operasjonene vi kan utføre på et binært tre.

3.1. Sette inn elementer

Den første operasjonen vi skal dekke er innsetting av nye noder.

Først, vi må finne stedet der vi vil legge til en ny node for å holde treet sortert. Vi følger disse reglene fra rotnoden:

  • hvis verdien til den nye noden er lavere enn den nåværende noden, går vi til venstre barn
  • hvis verdien til den nye noden er større enn den nåværende noden, går vi til riktig barn
  • når den nåværende noden er null, vi har nådd en bladnode, og vi kan sette den nye noden i den posisjonen

Først oppretter vi en rekursiv metode for å gjøre innsettingen:

private Node addRecursive (Node gjeldende, int-verdi) {if (gjeldende == null) {returner ny Node (verdi); } if (value current.value) {current.right = addRecursive (current.right, value); } annet {// verdi eksisterer allerede returstrøm; } returstrøm; }

Deretter oppretter vi den offentlige metoden som starter rekursjonen fra rot node:

public void add (int-verdi) {root = addRecursive (root, verdi); }

La oss nå se hvordan vi kan bruke denne metoden til å lage treet fra vårt eksempel:

private BinaryTree createBinaryTree () {BinaryTree bt = ny BinaryTree (); bt.add (6); bt.add (4); bt.add (8); bt.add (3); bt.add (5); bt.add (7); bt.add (9); returnere bt; }

3.2. Finne et element

La oss nå legge til en metode for å sjekke om treet inneholder en bestemt verdi.

Som før oppretter vi først en rekursiv metode som krysser treet:

privat boolsk inneholderNodeRecursive (Node gjeldende, int-verdi) {if (gjeldende == null) {return false; } if (value == current.value) {return true; } returverdi <gjeldende.verdi? inneholderNodeRecursive (current.left, verdi): containNodeRecursive (current.right, verdi); }

Her søker vi etter verdien ved å sammenligne den med verdien i den nåværende noden, og fortsett deretter i venstre eller høyre barn, avhengig av det.

La oss deretter lage den offentlige metoden som starter fra rot:

offentlig boolsk inneholderNode (int-verdi) {retur inneholderNodeRekursiv (rot, verdi); }

La oss nå lage en enkel test for å bekrefte at treet virkelig inneholder de innsatte elementene:

@Test offentlig ugyldig gittABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.containsNode (6)); assertTrue (bt.containsNode (4)); assertFalse (bt.containsNode (1)); }

Alle nodene som legges til, skal være inneholdt i treet.

3.3. Slette et element

En annen vanlig operasjon er sletting av en node fra treet.

Først må vi finne noden som skal slettes på en lignende måte som vi gjorde før:

private Node deleteRecursive (Node gjeldende, int-verdi) {if (gjeldende == null) {return null; } hvis (verdi == gjeldende.verdi) {// Node for å slette funnet // ... kode for å slette noden vil gå hit} hvis (verdi <gjeldende.verdi) {gjeldende.left = deleteRecursive (gjeldende.left, verdi); returstrøm; } current.right = deleteRecursive (current.right, verdi); returstrøm; }

Når vi har funnet noden som skal slettes, er det tre hovedtilfeller:

  • en node har ingen barn - dette er det enkleste tilfellet; vi trenger bare å erstatte denne noden med null i foreldrenoden
  • en node har nøyaktig ett barn - i foreldrenoden erstatter vi denne noden med det eneste barnet.
  • en node har to barn - dette er det mest komplekse tilfellet fordi det krever en treomorganisering

La oss se hvordan vi kan implementere det første tilfellet når noden er en bladnode:

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

La oss nå fortsette med saken når noden har ett barn:

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

Her returnerer vi ikke-null barnet slik at det kan tilordnes foreldrenoden.

Til slutt må vi håndtere saken der noden har to barn.

Først må vi finne noden som skal erstatte den slettede noden. Vi bruker den minste noden til noden som skal slettes, det høyre undertreet:

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

Deretter tildeler vi den minste verdien til noden som skal slettes, og deretter sletter vi den fra høyre undertrær:

int smallestValue = findSmallestValue (current.right); gjeldende.verdi = minste verdi; current.right = deleteRecursive (current.right, smallestValue); returstrøm;

Til slutt, la oss lage den offentlige metoden som starter sletting fra rot:

public void delete (int-verdi) {root = deleteRecursive (root, verdi); }

La oss nå sjekke at slettingen fungerer som forventet:

@Test offentlig ugyldig gittABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.containsNode (9)); bt.delete (9); assertFalse (bt.containsNode (9)); }

4. Traversing the Tree

I denne delen ser vi forskjellige måter å krysse et tre på, og dekker detaljene dybdeførste og bredde-første-søk.

Vi bruker det samme treet som vi brukte før, og vi viser gjennomkjøringsrekkefølgen for hvert tilfelle.

4.1. Dybde-første søk

Dybde-første søk er en type traversal som går dypt så mye som mulig i hvert barn før de utforsker neste søsken.

Det er flere måter å utføre et dybde-første søk: i rekkefølge, forhåndsbestilling og etterbestilling.

Bestillingen i bestilling består av først å besøke venstre undertre, deretter rotnoden og til slutt høyre undertre:

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

Hvis vi kaller denne metoden, vil konsollutgangen vise bestillingen i rekkefølge:

3 4 5 6 7 8 9

Forhåndsbestill traversal besøker først rotnoden, så venstre undertre og til slutt høyre undertre:

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

Og la oss sjekke forhåndsbestillingsovergangen i konsollutgangen:

6 4 3 5 8 7 9

Post-order traversal besøker venstre undertre, høyre undertre og rotnoden på slutten:

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

Her er nodene etter bestilling:

3 5 4 7 9 8 6

4.2. Bredde-første søk

Dette er en annen vanlig type traversal som besøker alle noder på et nivå før du går til neste nivå.

Denne typen traversering kalles også nivåordre og besøker alle nivåene i treet fra roten, og fra venstre til høyre.

For implementeringen vil vi bruke en å holde nodene fra hvert nivå i orden. Vi trekker ut hver node fra listen, skriver ut verdiene og legger barnene til i køen:

public void traverseLevelOrder () {if (root == null) {return; } Kønoder = ny LinkedList (); nodes.add (root); mens (! nodes.isEmpty ()) {Node node = nodes.remove (); System.out.print ("" + node.value); hvis (node.left! = null) {nodes.add (node.left); } hvis (node.right! = null) {nodes.add (node.right); }}}

I dette tilfellet vil rekkefølgen på nodene være:

6 4 8 3 5 7 9

5. Konklusjon

I denne artikkelen har vi sett hvordan du implementerer et sortert binært tre i Java og dets vanligste operasjoner.

Den fullstendige kildekoden for eksemplene er tilgjengelig på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found