streamalism.org

1. Pregled

Obrtanje binarnog stabla jedan je od problema koji bi se od nas trebali riješiti tijekom tehničkog razgovora.

U ovom brzom uputstvu vidjet ćemo nekoliko različitih načina rješavanja ovog problema.

2. Binarno stablo

Binarno stablo je struktura podataka u kojoj svaki element ima najviše dvoje djece, koji se nazivaju lijevim i desnim djetetom. Gornji element stabla je korijenski čvor, dok djeca su unutarnji čvorovi.

Međutim, ako čvor nema dijete, zove se list.

Rekavši to, kreirajmo svoj objekt koji predstavlja čvor:

javna klasa TreeNode {private int vrijednost; privatni TreeNode rightChild; privatni TreeNode leftChild; // Dobavljači i postavljači}

Zatim, kreirajmo naše stablo koje ćemo koristiti u našim primjerima:

 TreeNode leaf1 = novi TreeNode (1); TreeNode leaf2 = novi TreeNode (3); TreeNode leaf3 = novi TreeNode (6); TreeNode leaf4 = novi TreeNode (9); TreeNode nodeRight = novi TreeNode (7, list3, list4); TreeNode nodeLeft = novi TreeNode (2, list1, list2); Korijen TreeNode = novi TreeNode (4, nodeLeft, nodeRight); 

U prethodnoj metodi stvorili smo sljedeću strukturu:

Preokretanjem stabla slijeva udesno, na kraju ćemo imati sljedeću strukturu:

3. Obrtanje binarnog stabla

3.1. Rekurzivna metoda

U prvom primjeru, koristit ćemo rekurziju za okretanje stabla.

Kao prvo, nazvat ćemo našu metodu koristeći korijen stabla, a zatim ćemo je primijeniti na lijevoj i desnoj djeci dok ne dođemo do lišća drveća:

javna praznina reverseRecursive (TreeNode treeNode) {if (TreeNode == null) {return; } Temp TreeNode = treeNode.getLeftChild (); treeNode.setLeftChild (treeNode.getRightChild ()); treeNode.setRightChild (temp); reverseRecursive (treeNode.getLeftChild ()); reverseRecursive (treeNode.getRightChild ()); }

3.2. Iterativna metoda

U drugom primjeru, stablo ćemo preokrenuti koristeći iterativni pristup. Za to, koristit ćemo a LinkedList, koju inicijaliziramo korijenom našeg stabla.

Zatim, za svaki čvor koji anketiramo s popisa dodamo njegova podređena na taj popis prije nego što ih permutiramo.

Nastavljamo dodavati i uklanjati iz LinkedList dok ne dođemo do lišća drveća:

javna praznina reverseIterative (TreeNode treeNode) {Red čekanja = novi LinkedList (); if (TreeNode! = null) {queue.add (TreeNode); } while (! queue.isEmpty ()) {Čvor TreeNode = queue.poll (); if (node.getLeftChild ()! = null) {queue.add (node.getLeftChild ()); } if (node.getRightChild ()! = null) {queue.add (node.getRightChild ()); } Temp TreeNode = node.getLeftChild (); node.setLeftChild (node.getRightChild ()); node.setRightChild (temp); }}

4. Zaključak

U ovom kratkom članku istražili smo dva načina okretanja binarnog stabla. Počeli smo s rekurzivnom metodom da bismo je preokrenuli. Zatim smo na kraju koristili iterativni način da postignemo isti rezultat.

Cjelokupni izvorni kod ovih primjera i primjeri jedinstvenih testova mogu se naći na Githubu.