Dat fiind un arbore binar, scrieți o soluție iterativă și recursivă pentru a traversa arborele folosind inorder traversal în C++, Java și Python.
Spre deosebire de listele legate, array-urile unidimensionale și alte structuri de date liniare, care sunt parcurse în ordine liniară, arborii pot fi parcurși în mai multe moduri în ordine profundă (preorder, inorder și postorder) sau în ordine amplă (parcurgerea în ordine de nivel). Dincolo de aceste traversări de bază, sunt posibile diverse scheme mai complexe sau hibride, cum ar fi căutările limitate în profunzime, cum ar fi căutarea iterativă în profunzime (depth-first search). În această postare, se discută în detaliu traversarea arborelui în ordine.
Traversarea unui arbore implică iterarea peste toate nodurile într-un anumit mod. Deoarece arborele nu este o structură de date liniară, pot exista mai multe noduri următoare posibile de la un nod dat, astfel încât unele noduri trebuie să fie amânate, adică să fie stocate într-un fel pentru a fi vizitate ulterior. Parcurgerea se poate face iterativ, în cazul în care nodurile amânate sunt stocate în stivă, sau se poate face prin recursivitate, în cazul în care nodurile amânate sunt stocate implicit în stiva de apeluri.
Pentru parcurgerea unui arbore binar (nevid) într-o manieră ordonată, trebuie să facem aceste trei lucruri pentru fiecare nod n pornind de la rădăcina arborelui:
(L) Parcurgerea recursivă a subarborelui său stâng. Când această etapă este terminată, ne întoarcem din nou la n.(N) Procesarea lui n însuși.(R) Parcurgerea recurentă a subarborelui său drept. Când acest pas se termină, ne întoarcem din nou la n.În parcurgerea normală în ordine, vizităm subarborele stâng înainte de subarborele drept. Dacă vizităm subarborele din dreapta înainte de a vizita subarborele din stânga, se numește traversare în ordine inversă.
După cum putem vedea, înainte de a procesa orice nod, subarborele din stânga este procesat mai întâi, urmat de nod, iar subarborele din dreapta este procesat la final. Aceste operații pot fi definite în mod recursiv pentru fiecare nod. Implementarea recursivă este denumită căutare în profunzime (Depth-first search – DFS), deoarece arborele de căutare este adâncit cât mai mult posibil pe fiecare copil înainte de a trece la următorul frate.
În continuare este prezentat programul C++, Java și Python care o demonstrează:
Implementare iterativă –
Pentru a converti procedura recursivă de mai sus într-una iterativă, avem nevoie de o stivă explicită. Mai jos este prezentat un algoritm iterativ simplu bazat pe stivă pentru a efectua traversarea în ordine.
iterativeInorder(node)
Algoritmul poate fi implementat după cum urmează în C++, Java și 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
|
// Iterativ funcție pentru a efectua traversarea în ordine a arborelui
void inorderIterative(Node *root)
{
// creați o stivă goală
stack<Node*> stack;
// pornim de la nodul rădăcină (setați nodul curent la nodul rădăcină)
Node *curr = root;
// dacă nodul curent este nul și stiva este de asemenea goală, am terminat
while (!stack.empty() || curr != nullptr)
{
// dacă nodul curent există, îl împingem în stivă (îl amânăm)
// și trecem la copilul său din stânga
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else
{
// altfel, dacă nodul curent este nul, pop un element din stivă,
// îl imprimă și, în final, setează nodul curent la copilul său din dreapta
curr = stack.top();
stack.pop();
cout << curr->data << ” „;
curr = curr->dreapta;
}
}
}
|
Download Run Complete Code
.
Java
|
1
2
3
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
|
// Iterativă funcție pentru a efectua traversarea în ordine a arborelui
public static void inorderIterative(TreeNode root)
{
// creați o stivă goală
Stack<TreeNode> stack = new Stack();
// pornim de la nodul rădăcină (setați nodul curent la nodul rădăcină)
TreeNode curr = root;
// dacă nodul curent este nul și stiva este de asemenea goală, am terminat
while (!stack.empty() || curr != null)
{
// dacă nodul curent există, îl împingem în stivă (îl amânăm)
// și trecem la copilul său din stânga
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
else
{
// altfel, dacă nodul curent este nul, pop un element din stivă,
// îl imprimă și, în final, setează nodul curent la copilul său din dreapta
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
|
# Funcție iterativă pentru a efectua traversarea în ordine a arborelui
def inorderIterative(root):
# creați o stivă goală
stack = deque()
# începeți de la nodul rădăcină (setați nodul curent la nodul rădăcină)
curr = root
# dacă nodul curent este None și stiva este de asemenea goală, am terminat
while stack or curr:
# dacă nodul curent există, îl împingem în stivă (îl amânăm)
# și trecem la copilul său din stânga
if curr:
stack.append(curr)
curr = curr.left
else:
# altfel, dacă nodul curent este None, se extrage un element din stivă,
# se tipărește și, în final, se stabilește nodul curent la copilul său din dreapta
curr = stack.pop()
print(curr.data, end=’ ‘)
curr = curr.right
|
Download Run Complete Code
Complexitatea în timp a soluțiilor de mai sus este O(n), unde n este numărul total de noduri din arborele binar. Complexitatea spațială a programului este O(n), deoarece spațiul necesar este proporțional cu înălțimea arborelui, care poate fi egală cu numărul total de noduri din arbore în cel mai rău caz pentru arbori înclinați.
.