streamalism.org

1. Prehľad

Reverzia binárneho stromu je jedným z problémov, ktoré by sme mohli byť požiadaní o vyriešenie počas technického pohovoru.

V tejto rýchlej príručke sa dozvieme niekoľko rôznych spôsobov riešenia tohto problému.

2. Binárny strom

Binárny strom je dátová štruktúra, v ktorej má každý prvok najviac dve deti, ktoré sa označujú ako ľavé dieťa a pravé dieťa. Horným prvkom stromu je koreňový uzol, zatiaľ čo deti sú vnútorné uzly.

Avšak ak uzol nemá dieťa, nazýva sa to list.

Po tomto, vytvorme náš objekt, ktorý predstavuje uzol:

verejná trieda TreeNode {private int hodnota; privátny TreeNode rightChild; súkromný TreeNode leftChild; // Getters and setters}

Potom vytvorme náš strom, ktorý použijeme v našich príkladoch:

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

V predchádzajúcej metóde sme vytvorili nasledujúcu štruktúru:

Otočením stromu zľava doprava nakoniec dosiahneme nasledujúcu štruktúru:

3. Reverzia binárneho stromu

3.1. Rekurzívna metóda

V prvom príklade použijeme rekurziu na obrátenie stromu.

Po prvé, zavoláme našu metódu pomocou koreňa stromu, potom ju použijeme na ľavé a pravé dieťa kým nedosiahneme lístie stromu:

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

3.2. Iteratívna metóda

V druhom príklade zvrátime strom pomocou iteračného prístupu. Pre to, použijeme a LinkedList, ktoré inicializujeme koreňom nášho stromu.

Potom, pre každý uzol, ktorý vyzveme zo zoznamu, pridáme jeho deti do tohto zoznamu skôr, ako ich permutujeme.

Stále pridávame a odoberáme z LinkedList kým nedosiahneme lístie stromu:

public void reverseIterative (TreeNode treeNode) {List queue = new LinkedList (); if (treeNode! = null) {queue.add (treeNode); } while (! queue.isEmpty ()) {TreeNode node = queue.poll (); if (node.getLeftChild ()! = null) {queue.add (node.getLeftChild ()); } if (node.getRightChild ()! = null) {queue.add (node.getRightChild ()); } Teplota TreeNode = node.getLeftChild (); node.setLeftChild (node.getRightChild ()); node.setRightChild (teplota); }}

4. Záver

V tomto rýchlom článku sme preskúmali dva spôsoby obrátenia binárneho stromu. Začali sme pomocou rekurzívnej metódy na jej zvrátenie. Potom sme nakoniec použili rovnaký postup, aby sme dosiahli rovnaký výsledok.

Celý zdrojový kód týchto príkladov a testovacích prípadov jednotiek nájdete na serveri Github.