streamalism.org

1. Inleiding

In dit artikel behandelen we de implementatie van een binaire boomstructuur in Java.

Omwille van dit artikel, we zullen een gesorteerde binaire boom gebruiken die int waarden.

2. Binaire boom

Een binaire boom is een recursieve datastructuur waarbij elk knooppunt maximaal 2 kinderen kan hebben.

Een veelvoorkomend type binaire boom is een binaire zoekboom, waarin elk knooppunt een waarde heeft die groter is dan of gelijk is aan de knooppuntwaarden in de linker subboom, en kleiner dan of gelijk aan de knooppuntwaarden in de rechter subboom. boom.

Hier is een snelle visuele weergave van dit type binaire boom:

Voor de implementatie gebruiken we een auxiliary Knooppunt klasse die zal worden opgeslagen int waarden en bewaar een verwijzing naar elk kind:

class Node {int waarde; Knooppunt links; Knooppunt rechts; Knooppunt (int waarde) {this.value = waarde; rechts = null; left = null; }}

Laten we vervolgens het startknooppunt van onze stamboom toevoegen, meestal genaamd wortel:

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

3. Veel voorkomende handelingen

Laten we nu eens kijken naar de meest voorkomende bewerkingen die we kunnen uitvoeren op een binaire boom.

3.1. Elementen invoegen

De eerste operatie die we gaan behandelen, is het invoegen van nieuwe knooppunten.

Eerste, we moeten de plaats vinden waar we een nieuw knooppunt willen toevoegen om de boom gesorteerd te houden. We volgen deze regels vanaf het hoofdknooppunt:

• als de waarde van het nieuwe knooppunt lager is dan die van het huidige knooppunt, gaan we naar het linkerkind
• als de waarde van het nieuwe knooppunt groter is dan die van het huidige knooppunt, gaan we naar het juiste kind
• wanneer het huidige knooppunt is nul, we hebben een bladknooppunt bereikt en we kunnen het nieuwe knooppunt op die positie invoegen

Eerst maken we een recursieve methode om de invoeging uit te voeren:

private Node addRecursive (Node current, int value) {if (current == null) {return new Node (value); } if (waarde current.value) {current.right = addRecursive (current.right, waarde); } else {// waarde bestaat al return current; } retourstroom; }

Vervolgens maken we de openbare methode die de recursie start vanaf het wortel knooppunt:

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

Laten we nu eens kijken hoe we deze methode kunnen gebruiken om de boom van ons voorbeeld te maken:

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

3.2. Een element zoeken

Laten we nu een methode toevoegen om te controleren of de boom een ​​specifieke waarde bevat.

Zoals eerder zullen we eerst een recursieve methode maken die de boom doorkruist:

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

Hier zoeken we naar de waarde door deze te vergelijken met de waarde in het huidige knooppunt, en gaan afhankelijk daarvan verder in het linker- of rechterkind.

Laten we vervolgens de openbare methode maken die begint met de wortel:

openbare boolean containsNode (int waarde) {return containsNodeRecursive (root, waarde); }

Laten we nu een eenvoudige test maken om te verifiëren dat de boom echt de ingevoegde elementen bevat:

@Test openbare leegte gegevenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.containsNode (6)); assertTrue (bt.containsNode (4)); assertFalse (bt.containsNode (1)); }

Alle toegevoegde knooppunten moeten in de boomstructuur staan.

3.3. Een element verwijderen

Een andere veel voorkomende bewerking is het verwijderen van een knooppunt uit de boom.

Eerst moeten we het te verwijderen knooppunt op dezelfde manier vinden als voorheen:

private Node deleteRecursive (Node current, int value) {if (current == null) {return null; } if (waarde == current.value) {// Knooppunt om gevonden te verwijderen // ... code om het knooppunt te verwijderen gaat hierheen} if (waarde <current.value) {current.left = deleteRecursive (current.left, waarde); retourstroom; } current.right = deleteRecursive (current.right, waarde); retourstroom; }

Zodra we het te verwijderen knooppunt hebben gevonden, zijn er 3 verschillende hoofdgevallen:

• een knoop heeft geen kinderen - dit is het eenvoudigste geval; we hoeven alleen dit knooppunt te vervangen door nul in het bovenliggende knooppunt
• een knoop heeft precies één kind - in het bovenliggende knooppunt vervangen we dit knooppunt door zijn enige kind.
• een knoop heeft twee kinderen - dit is het meest complexe geval omdat het een reorganisatie van de boom vereist

Laten we eens kijken hoe we het eerste geval kunnen implementeren wanneer het knooppunt een bladknooppunt is:

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

Laten we nu doorgaan met het geval wanneer het knooppunt één kind heeft:

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

Hier retourneren we de niet-nul child, zodat het kan worden toegewezen aan het bovenliggende knooppunt.

Ten slotte moeten we het geval afhandelen waarin het knooppunt twee kinderen heeft.

Eerst moeten we het knooppunt vinden dat het verwijderde knooppunt zal vervangen. We gebruiken het kleinste knooppunt van het te verwijderen knooppunt in de rechter subboom:

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

Vervolgens wijzen we de kleinste waarde toe aan het te verwijderen knooppunt en daarna verwijderen we het uit de rechter substructuur:

int smallestValue = findSmallestValue (current.right); current.value = smallestValue; current.right = deleteRecursive (current.right, smallestValue); retourstroom;

Laten we tot slot de openbare methode maken waarmee het verwijderen van het wortel:

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

Laten we nu controleren of het verwijderen werkt zoals verwacht:

@Test openbare leegte gegevenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.containsNode (9)); bt.delete (9); assertFalse (bt.containsNode (9)); }

4. Doorkruisen van de boom

In deze sectie zullen we verschillende manieren zien om een ​​boom te doorkruisen, waarbij we in detail de diepte-eerst en breedte-eerst zoekopdrachten behandelen.

We gebruiken dezelfde boom die we eerder hebben gebruikt en we zullen de doorloopvolgorde voor elk geval weergeven.

4.1. Diepte-eerste zoekopdracht

Diepte-eerst zoeken is een soort traversal die zo diep mogelijk in elk kind gaat voordat het de volgende broer of zus verkent.

Er zijn verschillende manieren om een ​​diepte-eerst-zoekopdracht uit te voeren: in-order, pre-order en post-order.

Het in volgorde doorlopen bestaat uit het eerst bezoeken van de linker subboom, dan het hoofdknooppunt en tenslotte de rechter subboom:

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

Als we deze methode aanroepen, toont de console-uitvoer de in-order-traversal:

3 4 5 6 7 8 9

Pre-order traversal bezoekt eerst het hoofdknooppunt, dan de linker substructuur en tenslotte de rechter substructuur:

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

En laten we de doorloop van de pre-order in de console-uitvoer bekijken:

6 4 3 5 8 7 9

Doorlopen na de bestelling bezoekt de linker substructuur, de rechter substructuur en het hoofdknooppunt aan het einde:

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

Dit zijn de knooppunten in postorder:

3 5 4 7 9 8 6

4.2. Breedte-eerste zoekopdracht

Dit is een ander veelvoorkomend type traversal bezoekt alle knooppunten van een niveau voordat hij naar het volgende niveau gaat.

Dit soort traversal wordt ook wel level-order genoemd en bezoekt alle niveaus van de boom, beginnend bij de wortel, en van links naar rechts.

Voor de implementatie gebruiken we een Wachtrij om de knooppunten van elk niveau op volgorde te houden. We halen elk knooppunt uit de lijst, drukken de waarden af ​​en voegen vervolgens de onderliggende items toe aan de wachtrij:

public void traverseLevelOrder () {if (root == null) {return; } Wachtrij nodes = nieuwe LinkedList (); nodes.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); }}}

In dit geval is de volgorde van de knooppunten:

6 4 8 3 5 7 9

5. Conclusie

In dit artikel hebben we gezien hoe we een gesorteerde binaire boomstructuur in Java en de meest voorkomende bewerkingen kunnen implementeren.

De volledige broncode voor de voorbeelden is beschikbaar op GitHub.