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.
