Geef een binaire boom, schrijf een iteratieve en recursieve oplossing om de boom te doorkruisen met behulp van inorder traversal in C++, Java, en Python.
In tegenstelling tot gelinkte lijsten, een-dimensionale arrays, en andere lineaire datastructuren, die in lineaire volgorde worden doorlopen, kunnen bomen op meerdere manieren worden doorlopen in de diepte-eerste volgorde (pre order, in order, en post order) of in de breedte-eerste volgorde (level order traversal). Naast deze basis traversals zijn er verschillende complexere of hybride schema’s mogelijk, zoals diepte-gelimiteerde zoekopdrachten zoals iteratief diepte-eerst zoeken. In dit bericht wordt in detail ingegaan op inorder tree traversal.
Het doorlopen van een boom houdt in dat alle knooppunten op een of andere manier worden doorlopen. Aangezien de boom geen lineaire gegevensstructuur is, kan er meer dan één mogelijk volgend knooppunt zijn vanaf een gegeven knooppunt, zodat sommige knooppunten moeten worden uitgesteld, d.w.z. op een of andere manier moeten worden opgeslagen om later te kunnen worden bezocht. De traverse kan iteratief worden uitgevoerd, waarbij de uitgestelde knooppunten in de stack worden opgeslagen, of kan door middel van recursie worden uitgevoerd, waarbij de uitgestelde knooppunten impliciet in de aanroepstack worden opgeslagen.
Om een (niet-lege) binaire boom op een inorder-manier te traverseren, moeten we voor elk knooppunt n vanaf de wortel van de boom de volgende drie dingen doen:
(L) Recursief de linker subtree traverseren. Als deze stap is voltooid, zijn we weer terug bij n.(N) Verwerk n zelf.(R) Ga recursief door de rechter subtree. Als deze stap is voltooid, zijn we weer terug bij n.In normale inorder traversal, bezoeken we de linker subtree voor de rechter subtree. Als we de rechter subtree bezoeken voordat we de linker subtree bezoeken, spreken we van omgekeerde inorder traversal.
Zoals we kunnen zien, wordt voor het verwerken van een node eerst de linker subtree verwerkt, gevolgd door de node, en wordt de rechter subtree als laatste verwerkt. Deze bewerkingen kunnen voor elke knoop recursief worden gedefinieerd. De recursieve implementatie wordt een Depth-first search (DFS) genoemd, omdat de zoekboom bij elk kind zo diep mogelijk wordt gemaakt voordat naar de volgende sibling wordt gegaan.
Volgende is het C++, Java, en Python programma dat dit demonstreert:
Iteratieve implementatie –
Om de bovenstaande recursieve procedure om te zetten in een iteratieve, hebben we een expliciete stack nodig. Hieronder staat een eenvoudig iteratief algoritme op basis van een stack om in order traversal uit te voeren.
iterativeInorder(node)
Het algoritme kan als volgt worden geïmplementeerd in C++, Java, en Python:
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
|
// Iteratieve functie om in order traversal op de boom uit te voeren
void inorderIterative(Node *root)
{
// maak een lege stack
stack<Node*> stack;
// start vanaf de root node (stel huidige node in op de root node)
Node *curr = root;
// als de huidige node null is en de stack ook leeg is, zijn we klaar
while (!stack.empty() || curr != nullptr)
{
// als de huidige node bestaat, duw deze dan in de stack (defer it)
// en ga naar zijn linker child
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
anders
{
// anders, als de huidige node null is, pop een element van de stack,
// print het, en zet tenslotte de huidige node op zijn rechter child
curr = stack.top();
stack.pop();
cout << curr->data << ” “;
curr = curr->right;
}
}
}
|
Download Volledige code uitvoeren
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
|
// Iteratieve functie om in order traversal op de boom uit te voeren
public static void inorderIterative(TreeNode root)
{
// maak een lege stack
Stack<TreeNode> stack = new Stack();
// start vanaf de root node (stel huidige node in op de root node)
TreeNode curr = root;
// als de huidige node null is en de stack ook leeg is, zijn we klaar
while (!stack.empty() || curr != null)
{
// als de huidige node bestaat, duw deze dan in de stack (defer it)
// en ga naar zijn linker child
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
anders
{
// anders, als de huidige node null is, pop een element van de stack,
// print het, en zet tenslotte de huidige node op zijn rechter child
curr = stack.pop();
System.out.print(curr.data + ” “);
curr = curr.right;
}
}
}
|
Download Volledige code uitvoeren
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
|
# Iteratieve functie om inorder traversal uit te voeren op de boom
def inorderIterative(root):
# maak een lege stack
stack = deque()
# start vanaf de root node (stel huidige node in op de root node)
curr = root
# als de huidige node None is en de stack ook leeg is, zijn we klaar
while stack or curr:
# als het huidige knooppunt bestaat, duw het dan in de stack (uitstellen)
# en ga naar zijn linker kind
if curr:
stack.append(curr)
curr = curr.left
else:
# anders, als de huidige node None is, pop een element van de stack,
# print het, en stel tenslotte de huidige node in als zijn rechter child
curr = stack.pop()
print(curr.data, end=’ ‘)
curr = curr.right
|
Download Volledige code
De tijdcomplexiteit van bovenstaande oplossingen is O(n), waarbij n het totale aantal knooppunten in de binaire boom is. De ruimtecomplexiteit van het programma is O(n) aangezien de benodigde ruimte evenredig is met de hoogte van de boom, die in het slechtste geval gelijk kan zijn aan het totale aantal knopen in de boom voor scheve bomen.