streamalism.org

1. Oversigt

At vende et binært træ er et af de problemer, som vi måske bliver bedt om at løse under et teknisk interview.

I denne hurtige vejledning ser vi et par forskellige måder at løse dette problem på.

2. Binært træ

Et binært træ er en datastruktur, hvor hvert element højst har to børn, der kaldes det venstre barn og det højre barn. Det øverste element i træet er rodnoden, hvorimod børnene er de indre knudepunkter.

Imidlertid, hvis en knude ikke har noget barn, kaldes det et blad.

Når det er sagt, lad os oprette vores objekt, der repræsenterer en node:

offentlig klasse TreeNode {private int værdi; privat TreeNode rightChild; privat TreeNode leftChild; // Getters og setters}

Lad os derefter oprette vores træ, som vi bruger i vores eksempler:

 TreeNode leaf1 = ny TreeNode (1); TreeNode leaf2 = ny TreeNode (3); TreeNode leaf3 = ny TreeNode (6); TreeNode leaf4 = ny TreeNode (9); TreeNode nodeRight = ny TreeNode (7, blad3, blad4); TreeNode nodeLeft = ny TreeNode (2, blad1, blad2); TreeNode rod = ny TreeNode (4, nodeLeft, nodeRight); 

I den foregående metode oprettede vi følgende struktur:

Ved at vende træet fra venstre mod højre, vil vi ende med at have følgende struktur:

3. Vend det binære træ

3.1. Rekursiv metode

I det første eksempel vi bruger rekursion til at vende træet.

Først og fremmest, vi kalder vores metode ved hjælp af træets rod, så anvender vi den på henholdsvis venstre og højre børn indtil vi når træets blade:

public void reverseRecursive (TreeNode treeNode) {if (treeNode == null) {return; } TreeNode temp = treeNode.getLeftChild (); treeNode.setLeftChild (treeNode.getRightChild ()); treeNode.setRightChild (temp); reverseRecursive (treeNode.getLeftChild ()); reverseRecursive (treeNode.getRightChild ()); }

3.2. Iterativ metode

I det andet eksempel vi vender træet ved hjælp af en iterativ tilgang. For det, vi skal bruge en LinkedList, som vi initialiserer med roden af ​​vores træ.

Derefter, for hver node, vi undersøger fra listen, tilføjer vi dens børn til listen, før vi permuterer dem.

Vi fortsætter med at tilføje og fjerne fra LinkedList indtil vi når træets blade:

offentlig ugyldig reverseIterative (TreeNode treeNode) {Liste kø = ny LinkedList (); hvis (treeNode! = null) {queue.add (treeNode); } mens (! queue.isEmpty ()) {TreeNode node = queue.poll (); hvis (node.getLeftChild ()! = null) {queue.add (node.getLeftChild ()); } hvis (node.getRightChild ()! = null) {queue.add (node.getRightChild ()); } TreeNode temp = node.getLeftChild (); node.setLeftChild (node.getRightChild ()); node.setRightChild (temp); }}

4. Konklusion

I denne hurtige artikel udforskede vi de to måder at vende et binært træ på. Vi er startet med at bruge en rekursiv metode til at vende den. Derefter endte vi med at bruge en iterativ måde at opnå det samme resultat på.

Den komplette kildekode for disse eksempler og enhedstestsager kan findes på Github.