Bináris fa megfordítása Java-ban

1. Áttekintés

A bináris fa megfordítása az egyik probléma, amelyet megoldásra kérhetünk egy technikai interjú során.

Ebben a gyors bemutatóban megismerhetünk pár különböző módszert a probléma megoldására.

2. bináris fa

A bináris fa olyan adatszerkezet, amelyben minden elemnek legfeljebb két gyermeke van, amelyeket a bal és a jobb gyermekként emlegetünk. A fa legfelső eleme a gyökércsomópont, míg a gyerekek a belső csomópontok.

Azonban, ha egy csomópontnak nincs gyermeke, akkor levélnek hívják.

Ezt követően hozzuk létre az objektumunkat, amely egy csomópontot képvisel:

public class TreeNode {private int value; privát TreeNode rightChild; privát TreeNode leftChild; // Getters and setters}

Ezután hozzuk létre a fánkat, amelyet a példáinkban használunk:

 TreeNode leaf1 = új TreeNode (1); TreeNode leaf2 = új TreeNode (3); TreeNode leaf3 = új TreeNode (6); TreeNode leaf4 = új TreeNode (9); TreeNode nodeRight = új TreeNode (7, leaf3, leaf4); TreeNode nodeLeft = új TreeNode (2, leaf1, leaf2); TreeNode root = új TreeNode (4, nodeLeft, nodeRight); 

Az előző módszerben a következő struktúrát hoztuk létre:

A fa balról jobbra fordításával a következő felépítésűek leszünk:

3. A bináris fa megfordítása

3.1. Rekurzív módszer

Az első példában rekurzióval fogjuk megfordítani a fát.

Először is, meghívjuk a módszerünket a fa gyökerével, majd a bal és a jobb gyermeknél alkalmazzuk amíg el nem érjük a fa leveleit:

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. Iteratív módszer

A második példában iteratív megközelítéssel megfordítjuk a fát. Azért, használni fogjuk a LinkedList, amelyet a fánk gyökerével inicializálunk.

Azután, minden csomópontra, amelyet a listából lekérdezünk, hozzáadjuk gyermekeit ehhez a listához, mielőtt megismételnénk őket.

Folyamatosan hozzáadjuk és eltávolítjuk a LinkedList amíg el nem érjük a fa leveleit:

public void reverseIterative (TreeNode treeNode) {Lista sor = új LinkedList (); if (treeNode! = null) {queue.add (treeNode); } while (! queue.isEmpty ()) {TreeNode csomópont = queue.poll (); if (node.getLeftChild ()! = null) {queue.add (node.getLeftChild ()); } if (node.getRightChild ()! = null) {queue.add (node.getRightChild ()); } TreeNode temp = node.getLeftChild (); node.setLeftChild (node.getRightChild ()); node.setRightChild (temp); }}

4. Következtetés

Ebben a gyors cikkben a bináris fa megfordításának két módját tártuk fel. Rekurzív módszerrel kezdtük megfordítani. Aztán végül egy iteratív módszert használtunk ugyanazon eredmény eléréséhez.

Ezeknek a példáknak és az egységes teszteseteknek a teljes forráskódja megtalálható a Github oldalon.