Adott egy bináris fa, írj egy iteratív és rekurzív megoldást a fa átjárására az inorder traversal segítségével C++, Java és Python nyelven.
Az összekapcsolt listákkal, az egydimenziós tömbökkel és más lineáris adatstruktúrákkal ellentétben, amelyeket lineáris sorrendben járunk át, a fákat többféleképpen is átjárhatjuk mélységi sorrendben (preorder, inorder és postorder) vagy szélességi sorrendben (level order traversal). Ezeken az alapvető keresztezéseken túlmenően különböző összetettebb vagy hibrid sémák is lehetségesek, mint például a mélységkorlátozott keresés, például az iteratív mélyülő mélység-első keresés. Ebben a bejegyzésben részletesen tárgyaljuk az inorder tree traversal-t.
A fa átszelése magában foglalja az összes csomóponton való iterációt valamilyen módon. Mivel a fa nem lineáris adatszerkezet, egy adott csomópontból több lehetséges következő csomópont is lehet, ezért néhány csomópontot el kell halasztani, azaz valamilyen módon tárolni a későbbi látogatáshoz. A bejárás történhet iteratív módon, ahol a halasztott csomópontokat a veremben tároljuk, vagy történhet rekurzióval, ahol a halasztott csomópontokat implicit módon a hívási veremben tároljuk.
Egy (nem üres) bináris fa sorrendben történő bejárásához a következő három dolgot kell tennünk minden egyes csomópontra n a fa gyökerétől kezdve:
(L) Rekurzívan bejárjuk a bal oldali részfát. Amikor ezt a lépést befejeztük, újra a n-nál vagyunk.(N) Magát a n-t is feldolgozzuk.(R) Rekurzívan végigjárjuk a jobb oldali részfáját. Amikor ez a lépés befejeződött, ismét a n-nál vagyunk.A normál sorrendben történő átjárás során a bal oldali részfát a jobb oldali részfa előtt látogatjuk meg. Ha a jobb részfát a bal részfa meglátogatása előtt látogatjuk meg, akkor ezt fordított sorrendben történő átjárásnak nevezzük.
Amint láthatjuk, bármelyik csomópont feldolgozása előtt először a bal részfát dolgozzuk fel, utána a csomópontot, és végül a jobb részfát. Ezek a műveletek rekurzívan definiálhatók minden egyes csomópontra. A rekurzív megvalósítást mélységi keresésnek (DFS) nevezzük, mivel a keresési fát minden egyes gyermeken a lehető legmélyebbre mélyítjük, mielőtt a következő testvérre lépnénk.
A következő C++, Java és Python program demonstrálja ezt:
Iteratív megvalósítás –
A fenti rekurzív eljárás iteratívvá alakításához szükségünk van egy explicit veremre. Az alábbiakban egy egyszerű veremalapú iteratív algoritmust mutatunk be a sorrendben történő átjárás végrehajtására.
iterativeInorder(node)
Az algoritmus az alábbiak szerint implementálható C++, Java és Python nyelven:
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
|
// Iterativ. függvény a fán való sorrendbeli átjárás végrehajtására
void inorderIterative(Node *root)
{
// üres verem létrehozása
stack<Node*> stack;
// a gyökércsomópontból indulunk (az aktuális csomópontot a gyökércsomópontra állítjuk)
Node *curr = root;
// ha az aktuális csomópont null és a verem is üres, akkor végeztünk
while (!stack.empty() || curr != nullptr)
{
// ha az aktuális csomópont létezik, toljuk be a verembe (halasszuk el)
// és lépjünk a bal oldali gyermekére
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else
{
// egyébként, ha az aktuális csomópont nulla, pop egy elemet a veremről,
// kiírjuk, és végül az aktuális csomópontot a jobb oldali gyermekének állítjuk
curr = stack.top();
stack.pop();
cout << curr->adatok << ” “;
curr = curr->right;
}
}
}
|
Download Run Complete Code
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
|
// Iterative függvény a fán való sorrendbeli átjárás végrehajtására
public static void inorderIterative(TreeNode root)
{
// üres verem létrehozása
Stack<TreeNode> stack = new Stack();
// kezdjük a gyökércsomópontból (az aktuális csomópontot a gyökércsomópontra állítjuk)
TreeNode curr = root;
// ha az aktuális csomópont null és a verem is üres, akkor végeztünk
while (!stack.empty() || curr != null)
{
// ha az aktuális csomópont létezik, toljuk be a verembe (halasszuk el)
// és lépjünk a bal oldali gyermekére
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
else
{
// egyébként, ha az aktuális csomópont null, pop egy elemet a veremről,
// kiírjuk, és végül az aktuális csomópontot a jobb oldali gyermekének állítjuk
curr = stack.pop();
System.out.print(curr.data + ” “);
curr = curr.right;
} }
}
}
|
Download Run Complete Code
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
|
# Iteratív függvény a fán való soron belüli átjárás végrehajtására
def inorderIterative(root):
# üres verem létrehozása
stack = deque()
# a gyökércsomópontból indul (aktuális csomópontot a gyökércsomópontra állítjuk)
curr = root
# ha az aktuális csomópont None és a verem is üres, akkor végeztünk
while stack vagy curr:
# ha az aktuális csomópont létezik, toljuk be a verembe (halasszuk el)
# és lépjünk a baloldali gyermekére
if curr:
stack.append(curr)
curr = curr.left
else:
# egyébként, ha az aktuális csomópont None, pop egy elemet a veremről,
# kiírjuk, és végül az aktuális csomópontot a jobb oldali gyermekének állítjuk
curr = stack.pop()
print(curr.data, end=’ ‘)
curr = curr.right
|
Futtatás teljes kód letöltése
A fenti megoldások időbonyolultsága O(n), ahol n a bináris fa összes csomópontjának száma. A program térbonyolultsága O(n), mivel a helyigény arányos a fa magasságával, ami ferde fák esetén legrosszabb esetben megegyezhet a fa összes csomópontjának számával.