Při zadání binárního stromu napište iterativní a rekurzivní řešení pro procházení stromu pomocí inorder traversalu v jazycích C++, Java a Python.
Na rozdíl od spojových seznamů, jednorozměrných polí a dalších lineárních datových struktur, které se procházejí v lineárním pořadí, lze stromy procházet více způsoby v pořadí do hloubky (preorder, inorder a postorder) nebo do šířky (level order traversal). Kromě těchto základních procházení jsou možná různá složitější nebo hybridní schémata, například prohledávání s omezením hloubky, jako je iterativní prohledávání s prohloubením do hloubky. V tomto příspěvku se podrobně zabýváme procházením stromů v pořadí
Procházení stromu zahrnuje iteraci nad všemi uzly určitým způsobem. Protože strom není lineární datová struktura, může od daného uzlu existovat více než jeden možný další uzel, takže některé uzly je třeba odložit, tj. nějakým způsobem uložit pro pozdější návštěvu. Procházení lze provést iterativně, kdy jsou odložené uzly uloženy v zásobníku, nebo rekurzivně, kdy jsou odložené uzly uloženy implicitně v zásobníku volání.
Pro procházení (neprázdného) binárního stromu inordinačním způsobem musíme pro každý uzel n počínaje kořenem stromu provést tyto tři věci:
(L) Rekurzivně projít jeho levý podstrom. Po dokončení tohoto kroku jsme opět u n. (N) Zpracujte samotný n. (R) Rekurzivně projděte jeho pravý podstrom. Po dokončení tohoto kroku jsme opět u n.Při normálním inorder traversalu navštívíme levý podstrom před pravým podstromem. Pokud navštívíme pravý podstrom před návštěvou levého podstromu, označuje se to jako reverzní inorder traversal.
Jak vidíme, před zpracováním libovolného uzlu se nejprve zpracuje levý podstrom, poté uzel a nakonec se zpracuje pravý podstrom. Tyto operace lze definovat rekurzivně pro každý uzel. Rekurzivní implementace se označuje jako prohledávání do hloubky (Depth-first search – DFS), protože prohledávaný strom je na každém potomkovi co nejvíce prohlouben, než se přejde k dalšímu sourozenci.
Následuje program v jazycích C++, Java a Python, který to demonstruje:
Iterativní implementace –
Pro převod výše uvedeného rekurzivního postupu na iterativní potřebujeme explicitní zásobník. Níže je uveden jednoduchý iterativní algoritmus založený na zásobníku, který provádí inorder traversal.
iterativeInorder(node)
Algoritmus lze v jazycích C++, Java a Python implementovat následujícím způsobem:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
// Iterativní funkce pro provedení inorder traverzování stromu
void inorderIterative(Node *root)
{
// vytvoření prázdného zásobníku
stack<Node*> stack;
// začneme od kořenového uzlu (nastavíme aktuální uzel na kořenový uzel)
Uzel *curr = root;
// pokud je aktuální uzel nulový a zásobník je také prázdný, skončili jsme
while (!stack.empty() || curr != nullptr)
{
// pokud aktuální uzel existuje, vložíme jej do zásobníku (odložíme jej)
// a přesuneme se na jeho levého potomka
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else
{
// jinak, pokud je aktuální uzel nulový, vyskočí prvek ze zásobníku,
// vypíše jej a nakonec nastaví aktuální uzel na jeho pravého potomka
curr = stack.top();
stack.pop();
cout << curr->data << “ „;
curr = curr->right;
}
}
}
|
Stáhnout kompletní kód spuštění
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// Iterativní funkce pro provedení inorder traverzování stromu
public static void inorderIterative(TreeNode root)
{
// vytvoření prázdného zásobníku
Stack<TreeNode> stack = new Stack();
// začneme od kořenového uzlu (nastavíme aktuální uzel na kořenový uzel)
TreeNode curr = root;
// pokud je aktuální uzel nulový a zásobník je také prázdný, skončili jsme
while (!stack.empty() || curr != null)
{
// pokud aktuální uzel existuje, vložíme jej do zásobníku (odložíme jej)
// a přesuneme se na jeho levého potomka
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
else
{
// jinak, pokud je aktuální uzel nulový, vyskočí prvek ze zásobníku,
// vypíše jej a nakonec nastaví aktuální uzel na jeho pravého potomka
curr = stack.pop();
System.out.print(curr.data + “ „);
curr = curr.right;
}
}
}
|
Stáhnout spustit kompletní kód
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
# Iterativní funkce pro provedení inorder traverzování stromu
def inorderIterative(root):
# vytvořit prázdný zásobník
stack = deque()
# začít od kořenového uzlu (nastavit aktuální uzel na kořenový)
curr = root
# pokud je aktuální uzel None a zásobník je také prázdný, skončili jsme
while stack or curr:
# pokud aktuální uzel existuje, vložíme ho do zásobníku (odložíme ho)
# a přesuneme se na jeho levého potomka
if curr:
stack.append(curr)
curr = curr.left
else:
# jinak, pokud je aktuální uzel None, vyskočíme prvek ze zásobníku,
# vypíšeme ho a nakonec nastavíme aktuální uzel na jeho pravého potomka
curr = stack.pop()
print(curr.data, end=‘ ‚)
curr = curr.right
|
Stáhnout spustit kompletní kód
Časová složitost výše uvedených řešení je O(n), kde n je celkový počet uzlů binárního stromu. Prostorová složitost programu je O(n), protože potřebný prostor je úměrný výšce stromu, která může být v nejhorším případě rovna celkovému počtu uzlů ve stromu u šikmých stromů.
.