Informatică Programare
Parcurgeri arbore binar C++
Parcurgerile unui arbore binar în C++ sunt metode de vizitare a nodurilor într-o anumită ordine, esențiale pentru procesarea datelor arborescente. Cele trei parcurgeri principale sunt în ordine (inorder), preordine (preorder) și postordine (postorder), fiecare având reguli specifice de traversare a rădăcinii, subarborelui stâng și subarborelui drept.
Tipuri de parcurgeri
- Inorder (stânga-rădăcină-dreapta) Vizitează subarborele stâng, apoi rădăcina, apoi subarborele drept. Pentru un arbore binar de căutare, produce elementele în ordine sortată.
- Preorder (rădăcină-stânga-dreapta) Vizitează rădăcina, apoi subarborele stâng, apoi subarborele drept. Utilă pentru copierea structurii arborelui.
- Postorder (stânga-dreapta-rădăcină) Vizitează subarborele stâng, apoi subarborele drept, apoi rădăcina. Folosită pentru ștergerea arborelui sau evaluarea expresiilor.
Exemplu de cod C++ pentru parcurgeri
- 1 Definirea structurii nod struct Node { int data; Node* left; Node* right; Node(int val) : data(val), left(nullptr), right(nullptr) {} };
- 2 Funcția inorder void inorder(Node* root) { if (root == nullptr) return; inorder(root->left); cout << root->data << " "; inorder(root->right); }
- 3 Funcția preorder void preorder(Node* root) { if (root == nullptr) return; cout << root->data << " "; preorder(root->left); preorder(root->right); }
- 4 Funcția postorder void postorder(Node* root) { if (root == nullptr) return; postorder(root->left); postorder(root->right); cout << root->data << " "; }
Alege parcurgerea în funcție de nevoie: inorder pentru sortare, preorder pentru copiere, postorder pentru ștergere.