Kirjoita iteratiivinen ja rekursiivinen ratkaisu puun läpikäymiseen käyttämällä inorder traversal -menetelmää C++:ssa, Javassa ja Pythonissa.
Toisin kuin linkitetyt listat, yksiulotteiset matriisit ja muut lineaariset tietorakenteet, jotka läpikäydään lineaarisessa järjestyksessä, puut voidaan läpikäydä usealla eri tavalla syvyysjärjestyksessä (preorder, inorder ja postorder) tai leveysjärjestyksessä (level order traversal). Näiden peruskäsittelyjen lisäksi on mahdollista käyttää erilaisia monimutkaisempia tai hybridejä järjestelmiä, kuten syvyysrajattuja hakuja, kuten iteratiivista syvenevää syvyys-ensimmäistä hakua. Tässä postauksessa käsitellään yksityiskohtaisesti inorder-puiden läpikäyntiä.
Puun läpikäyntiin kuuluu kaikkien solmujen iterointi jollakin tavalla. Koska puu ei ole lineaarinen tietorakenne, tietystä solmusta voi olla useampi kuin yksi mahdollinen seuraava solmu, joten joitakin solmuja on lykättävä eli tallennettava jollain tavalla myöhempää vierailua varten. Kulkeminen voidaan tehdä iteratiivisesti, jolloin lykätyt solmut tallennetaan pinoon, tai se voidaan tehdä rekursiivisesti, jolloin lykätyt solmut tallennetaan implisiittisesti kutsupinoon.
Kulkemiseksi (ei-tyhjän) binääripuun läpi järjestyksessä meidän on tehtävä nämä kolme asiaa jokaiselle solmulle n alkaen puun juuresta:
(L) Kulkemalla rekursiivisesti sen vasen alapuu. Kun tämä vaihe on suoritettu, olemme taas n:n luona.(N) Käsittele n itseään.(R) Kierrä rekursiivisesti sen oikea alipuu. Kun tämä vaihe on valmis, olemme taas takaisin kohdassa n.Normaalissa inorder traversalissa käymme vasemmassa alipuussa ennen oikeaa alipuuta. Jos käymme oikeassa alipuussa ennen kuin käymme vasemmassa alipuussa, puhutaan käänteisestä inorder traversalista.
Kuten näemme, ennen minkään solmun käsittelyä käsitellään ensin vasen alipuu, sen jälkeen solmu ja viimeisenä käsitellään oikea alipuu. Nämä operaatiot voidaan määritellä rekursiivisesti jokaiselle solmulle. Rekursiivista toteutusta kutsutaan syvyyshakuksi (Depth-first search, DFS), koska hakupuuta syvennetään mahdollisimman paljon jokaisessa lapsessa, ennen kuin siirrytään seuraavaan sisarukseen.
Seuraavana on C++-, Java- ja Python-ohjelma, joka havainnollistaa sitä:
Iteratiivinen toteutus –
Muuttaaksemme edellä esitellyn rekursiivisen menettelyn iteratiiviseksi tarvitsemme eksplisiittisen pinon. Alla on yksinkertainen pinoon perustuva iteratiivinen algoritmi järjestyksen sisäisen läpikäynnin suorittamiseksi.
iterativeInorder(node)
Algoritmi voidaan toteuttaa seuraavasti C++:ssa, Javassa ja Pythonissa:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
funktio, jolla suoritetaan järjestyksessä tapahtuva puun läpikäynti void inorderIterative(Node *root)
{
// luodaan tyhjä pino
stack<Node*> stack;
// aloitetaan juurisolmusta (asetetaan nykyinen solmu juurisolmuksi)
Node *curr = root;
// jos nykyinen solmu ei ole nolla ja pino on myös tyhjä, ollaan valmiita
while (!stack.empty() || curr != nullptr)
{
// jos nykyinen solmu on olemassa, työnnä se pinoon (lykkää sitä)
// ja siirry sen vasempaan lapseen
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else
{
// otherwise, if the current node is null, pop an element from the stack,
// print it, and finally set the current node to its right child
curr = stack.
}
}
|
Lataus Suorita täydellinen koodi
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
|
// Iteratiiviset funktio, jolla suoritetaan järjestyksessä tapahtuva läpikäynti puulle
public static void inorderIterative(TreeNode root)
{
// luodaan tyhjä pino
Stack<TreeNode> stack = new Stack();
// aloitetaan juurisolmusta (asetetaan nykyinen solmu juurisolmuksi)
TreeNode curr = root;
// jos nykyinen solmu on nolla ja pino on myös tyhjä, olemme valmiit
while (!stack.empty() || curr != null)
{
// jos nykyinen solmu on olemassa, työnnä se pinoon (siirrä se)
// ja siirry sen vasempaan lapseen
if (curr != null)
{
stack.push(curr);
curr = curr.left;
} }
else
{
// otherwise, if the current node is null, pop an element from the stack,
// print it, and finally set the current node to its right child
curr = stack.pop();
System.out.print(curr.data + ” ”);
curr = curr.right;
} }
}
}
|
Lataus Suorita täydellinen koodi
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
|
# Iteratiivinen funktio, jolla suoritetaan järjestyksenmukainen läpikäynti puulle
def inorderIterative(root):
# luodaan tyhjä pino
stack = deque()
# aloitetaan juurisolmusta (asetetaan nykyinen solmu juurisolmuksi)
curr = root
# jos nykyinen solmu ei ole None ja pino on myös tyhjä, olemme valmiit
while stack tai curr:
# jos nykyinen solmu on olemassa, työnnä se pinoon (siirrä se)
# ja siirry sen vasempaan lapseen
if curr:
stack.append(curr)
curr = curr.left
else:
# muuten, jos nykyinen solmu ei ole None, popataan elementti pinosta,
# tulostetaan se ja lopuksi asetetaan nykyinen solmu sen oikeaksi lapseksi
curr = stack.pop()
print(curr.data, end=’ ’)
curr = curr.right
|
Lataus Suorita täydellinen koodi
Ylläolevien ratkaisujen aikakompleksisuus on O(n), missä n on binääripuun solmujen kokonaismäärä. Ohjelman tilakompleksisuus on O(n), koska tarvittava tila on verrannollinen puun korkeuteen, joka voi pahimmassa tapauksessa vinoissa puissa olla yhtä suuri kuin puun solmujen kokonaismäärä.