streamalism.org

1. Introduktion

I denne artikel dækker vi implementeringen af ​​et binært træ i Java.

Af hensyn til denne artikel, vi bruger et sorteret binært træ, der indeholder int værdier.

2. Binært træ

Et binært træ er en rekursiv datastruktur, hvor hver node højst kan have 2 børn.

En almindelig type binært træ er et binært søgetræ, hvor hvert knudepunkt har en værdi, der er større end eller lig med knudepunktværdierne i det venstre undertræ og mindre end eller lig med knudepunktværdierne i det højre under- træ.

Her er en hurtig visuel gengivelse af denne type binært træ:

Til implementeringen bruger vi en hjælpestøtte Node klasse, der gemmer int værdier og hold en henvisning til hvert barn:

klasse Node {int værdi; Node til venstre; Knude til højre; Node (int-værdi) {this.value = værdi; højre = null; venstre = null; }}

Lad os derefter tilføje startknudepunktet for vores træ, der normalt kaldes rod:

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

3. Fælles operationer

Lad os nu se de mest almindelige operationer, vi kan udføre på et binært træ.

3.1. Indsættelse af elementer

Den første operation, vi skal dække, er indsættelse af nye noder.

Først, vi er nødt til at finde det sted, hvor vi vil tilføje en ny knude for at holde træet sorteret. Vi følger disse regler startende fra rodnoden:

• hvis den nye nodes værdi er lavere end den aktuelle nodes, går vi til det venstre barn
• hvis den nye nodes værdi er større end den aktuelle nodes, går vi til det rigtige barn
• når den aktuelle node er nul, vi har nået en bladknude, og vi kan indsætte den nye knude i den position

Først opretter vi en rekursiv metode til at udføre indsættelsen:

privat Node addRecursive (Node nuværende, int-værdi) {if (nuværende == null) {returner ny Node (værdi); } hvis (værdi current.value) {current.right = addRecursive (current.right, værdi); } andet {// værdi findes allerede returstrøm; } returstrøm; }

Derefter opretter vi den offentlige metode, der starter rekursion fra rod knude:

public void add (int værdi) {root = addRecursive (root, værdi); }

Lad os nu se, hvordan vi kan bruge denne metode til at oprette træet fra vores 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. At finde et element

Lad os nu tilføje en metode til at kontrollere, om træet indeholder en bestemt værdi.

Som før opretter vi først en rekursiv metode, der krydser træet:

privat boolsk containNodeRecursive (Node nuværende, int-værdi) {hvis (nuværende == null) {returner falsk; } hvis (værdi == nuværende.værdi) {returner sand; } returværdi <aktuelle.værdi? indeholderNodeRecursive (current.left, værdi): containNodeRecursive (current.right, værdi); }

Her søger vi efter værdien ved at sammenligne den med værdien i den aktuelle node, og fortsæt derefter i venstre eller højre barn afhængigt af det.

Lad os derefter oprette den offentlige metode, der starter fra rod:

offentlig boolsk containNode (int-værdi) {return indeholderNodeRecursive (rod, værdi); }

Lad os nu oprette en simpel test for at kontrollere, at træet virkelig indeholder de indsatte elementer:

@Test offentligt ugyldigt givetABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.containsNode (6)); assertTrue (bt.containsNode (4)); assertFalse (bt.containsNode (1)); }

Alle tilføjede noder skal være indeholdt i træet.

3.3. Sletning af et element

En anden almindelig handling er sletning af en node fra træet.

Først skal vi finde noden, der skal slettes, på en lignende måde, som vi gjorde før:

privat Node deleteRecursive (Node nuværende, int-værdi) {if (nuværende == null) {return null; } hvis (værdi == nuværende.værdi) {// Knude for at slette fundet // ... kode for at slette noden vil gå her} hvis (værdi <nuværende.værdi) {nuværende.left = deleteRecursive (nuværende.left, værdi); returstrøm; } current.right = deleteRecursive (current.right, værdi); returstrøm; }

Når vi først har fundet noden, der skal slettes, er der 3 hovedtilfælde:

• en knude har ingen børn - dette er den enkleste sag; vi skal bare erstatte denne node med nul i dets overordnede knude
• en knude har nøjagtigt et barn - i den overordnede knude erstatter vi denne knude med dens eneste barn.
• en knude har to børn - dette er den mest komplekse sag, fordi det kræver en reorganisering af træet

Lad os se, hvordan vi kan implementere den første sag, når noden er en bladnode:

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

Lad os fortsætte med sagen, når noden har et barn:

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

Her returnerer vi ikke-nul barn, så det kan tildeles den overordnede node.

Endelig skal vi håndtere sagen, hvor knudepunktet har to børn.

Først skal vi finde den node, der skal erstatte den slettede node. Vi bruger den mindste node på noden, der skal slettes, det højre undertræ:

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

Derefter tildeler vi den mindste værdi til noden, der skal slettes, og derefter sletter vi den fra det rigtige undertræ:

int smallestValue = findSmallestValue (current.right); nuværende.værdi = mindste værdi; current.right = deleteRecursive (current.right, smallestValue); returstrøm;

Lad os endelig oprette den offentlige metode, der starter sletningen fra rod:

offentlig ugyldig sletning (int-værdi) {root = deleteRecursive (root, værdi); }

Lad os nu kontrollere, at sletningen fungerer som forventet:

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

4. Traversering af træet

I dette afsnit vil vi se forskellige måder at krydse et træ på, der i detaljer dækker dybde-første og bredde-første søgninger.

Vi bruger det samme træ, som vi brugte før, og vi viser gennemkørselsrækkefølgen for hvert tilfælde.

4.1. Dybde-første søgning

Dybde-første søgning er en type traversal, der går dybt så meget som muligt i hvert barn, før de udforsker det næste søskende.

Der er flere måder at udføre en dybde-første søgning: i rækkefølge, forudbestilling og efterbestilling.

In-order traversal består af først at besøge det venstre undertræ, derefter rodnoden og til sidst det højre undertræ:

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

Hvis vi kalder denne metode, viser konsoloutputtet i rækkefølge:

3 4 5 6 7 8 9

Forudbestil traversal besøger først rodknudepunktet, derefter venstre undertræ og til sidst det højre undertræ:

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

Og lad os kontrollere forudbestillingsgennemgangen i konsoludgangen:

6 4 3 5 8 7 9

Post-order traversal besøger venstre undertræ, højre undertræ og rodnoden i slutningen:

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

Her er noderne i postordre:

3 5 4 7 9 8 6

4.2. Bredde-første søgning

Dette er en anden almindelig form for traversal besøger alle knudepunkter på et niveau, inden de går til det næste niveau.

Denne form for traversal kaldes også niveau-orden og besøger alle træets niveauer startende fra roden og fra venstre mod højre.

Til implementeringen bruger vi en Kø at holde noder fra hvert niveau i rækkefølge. Vi udtrækker hver knude fra listen, udskriver dens værdier og tilføjer derefter sine børn i køen:

public void traverseLevelOrder () {if (root == null) {return; } Køknuder = ny LinkedList (); nodes.add (rod); 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 tilfælde vil nodernes rækkefølge være:

6 4 8 3 5 7 9

5. Konklusion

I denne artikel har vi set, hvordan man implementerer et sorteret binært træ i Java og dets mest almindelige operationer.

Den fulde kildekode til eksemplerne er tilgængelig på GitHub.