Implementering av ett binärt träd i Java

1. Introduktion

I den här artikeln behandlar vi implementeringen av ett binärt träd i Java.

För den här artikelns skull använder vi ett sorterat binärt träd som innehåller int- värden .

2. Binärt träd

Ett binärt träd är en rekursiv datastruktur där varje nod kan ha högst två barn.

En vanlig typ av binärt träd är ett binärt sökträd, där varje nod har ett värde som är större än eller lika med nodvärdena i det vänstra subträdet och mindre än eller lika med nodvärdena i det högra subträdet. träd.

Här är en snabb visuell representation av denna typ av binärt träd:

För implementeringen använder vi en extra nodklass som lagrar int- värden och håller en referens till varje barn:

class Node { int value; Node left; Node right; Node(int value) { this.value = value; right = null; left = null; } }

Låt oss sedan lägga till startnoden på vårt träd, vanligtvis kallat root:

public class BinaryTree { Node root; // ... }

3. Gemensamma operationer

Låt oss nu se de vanligaste operationerna vi kan utföra på ett binärt träd.

3.1. Infoga element

Den första operationen vi ska täcka är införandet av nya noder.

Först måste vi hitta den plats där vi vill lägga till en ny nod för att hålla trädet sorterat . Vi följer dessa regler från rotnoden:

  • om den nya nodens värde är lägre än den aktuella nodens, går vi till det vänstra barnet
  • om den nya nodens värde är större än den aktuella nodens, går vi till rätt barn
  • när den aktuella noden är noll har vi nått en bladnod och vi kan infoga den nya noden i den positionen

Först skapar vi en rekursiv metod för att göra insättningen:

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 { // value already exists return current; } return current; }

Nu ska vi skapa en offentlig metod som startar rekursion från rot -noden:

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

Låt oss nu se hur vi kan använda den här metoden för att skapa trädet från vårt exempel:

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

3.2. Hitta ett element

Låt oss nu lägga till en metod för att kontrollera om trädet innehåller ett visst värde.

Som tidigare skapar vi först en rekursiv metod som passerar trädet:

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

Här söker vi efter värdet genom att jämföra det med värdet i den aktuella noden, fortsätt sedan i vänster eller höger barn beroende på det.

Låt oss sedan skapa den offentliga metoden som börjar från roten :

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

Nu ska vi skapa ett enkelt test för att verifiera att trädet verkligen innehåller de infogade elementen:

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

Alla noder som läggs till ska finnas i trädet.

3.3. Ta bort ett element

En annan vanlig operation är borttagning av en nod från trädet.

Först måste vi hitta noden som ska tas bort på ett liknande sätt som vi gjorde tidigare:

private Node deleteRecursive(Node current, int value) { if (current == null) { return null; } if (value == current.value) { // Node to delete found // ... code to delete the node will go here } if (value < current.value) { current.left = deleteRecursive(current.left, value); return current; } current.right = deleteRecursive(current.right, value); return current; }

När vi väl har hittat noden som ska raderas finns det tre huvudsakliga fall:

  • en nod har inga barn - detta är det enklaste fallet; vi behöver bara ersätta den här noden med null i dess överordnade nod
  • en nod har exakt ett barn - i föräldernoden ersätter vi denna nod med sitt enda barn.
  • en nod har två barn - detta är det mest komplexa fallet eftersom det kräver en trädorganisation

Låt oss se hur vi kan implementera det första fallet när noden är en bladnod:

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

Låt oss nu fortsätta med fallet när noden har ett barn:

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

Här returnerar vi barnet som inte är null så att det kan tilldelas föräldernoden.

Slutligen måste vi hantera fallet där noden har två barn.

Först måste vi hitta noden som kommer att ersätta den raderade noden. Vi använder den minsta noden på noden som ska raderas högra underträd:

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

Sedan tilldelar vi det minsta värdet till noden som ska raderas och därefter tar vi bort det från rätt underträd:

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

Slutligen, låt oss skapa den offentliga metoden som startar borttagningen från roten :

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

Låt oss nu kontrollera att borttagningen fungerar som förväntat:

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

4. Korsa trädet

I det här avsnittet kommer vi att se olika sätt att korsa ett träd och täcka i detalj djup-första och bredd-första-sökningen.

Vi kommer att använda samma träd som vi använde tidigare och vi visar tvärsordning för varje fall.

4.1. Djup-första sökning

Djup-första sökning är en typ av traversal som går djupt så mycket som möjligt i varje barn innan de utforskar nästa syskon.

Det finns flera sätt att utföra en djup-första sökning: i ordning, förbeställning och efterbeställning.

Beställningen i ordning består av att först besöka det vänstra underträdet, sedan rotnoden och slutligen det högra underträdet:

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

Om vi ​​kallar den här metoden kommer konsolutgången att visa övergången i ordning:

3 4 5 6 7 8 9

Förbeställ traversal besöker först rotnoden, sedan vänster subtree och slutligen rätt subtree:

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

Och låt oss kontrollera förbeställningspassering i konsolutgången:

6 4 3 5 8 7 9

Traversal efter beställning besöker vänster subtree, höger subtree och rotnoden i slutet:

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

Här är noder i postorder:

3 5 4 7 9 8 6

4.2. Utöka första sökningen

Detta är en annan vanlig typ av traversal som besöker alla noder på en nivå innan de går till nästa nivå .

Denna typ av traversal kallas också nivåordning och besöker alla nivåer i trädet från roten och från vänster till höger.

För implementeringen använder vi en kö för att hålla noder från varje nivå i ordning. Vi extraherar varje nod från listan, skriver ut dess värden och lägger sedan till sina barn i kön:

public void traverseLevelOrder() { if (root == null) { return; } Queue nodes = new 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); } } }

I det här fallet kommer nodernas ordning att vara:

6 4 8 3 5 7 9

5. Sammanfattning

I den här artikeln har vi sett hur man implementerar ett sorterat binärt träd i Java och dess vanligaste operationer.

Den fullständiga källkoden för exemplen finns tillgänglig på GitHub.