Tehnici de traversare a arborilor include diferite moduri de a vizita toate nodurile arborelui. Spre deosebire de structurile de date liniare (Matrice, Listă Linked, Cozi, Stive etc.) care au o singură modalitate logică de a le traversa, copacii pot fi traversați în moduri diferite. În acest articol, vom discuta despre toate tehnicile de traversare a copacilor împreună cu utilizările acestora.

Cuprins

• Semnificația traversării arborelui
• Tehnici de traversare a copacilor
• Traversarea în ordine
• Precomandă Traversal
• Traversarea comenzii poștale
• Traversarea ordinului la nivel
• Alte traversări ale copacilor
• Întrebări frecvente (FAQs) despre tehnicile de traversare a arborilor

Semnificația traversării arborelui:

Traversarea copacului se referă la procesul de vizitare sau accesare a fiecărui nod al arborelui exact o dată într-o anumită ordine. Algoritmii de traversare a arborilor ne ajută să vizităm și să procesăm toate nodurile arborelui. Deoarece arborele nu este o structură de date liniară, există mai multe noduri pe care le putem vizita după ce vizităm un anumit nod. Există mai multe tehnici de traversare a arborelui care decid ordinea în care nodurile arborelui vor fi vizitate.

Tehnici de traversare a copacilor:

O structură de date arbore poate fi parcursă în următoarele moduri:

• Depth First Search sau DFS
  • Traversarea în ordine
  • Precomandă Traversal
  • Traversarea comenzii poștale
• Traversarea ordinului de nivel sau Căutarea întâi pe lățime sau BFS

Traversarea în ordine :

Parcursul în ordine vizitează nodul în ordinea: Stânga -> Rădăcină -> Dreapta

arhitectura linux

Algoritm pentru traversarea în ordine:

În ordine (arborele)

• Traversați subarborele din stânga, adică apelați Inorder(stânga->subarborele)
• Vizitați rădăcina.
• Traversați subarborele din dreapta, adică apelați Inorder(dreapta->subarborele)

Utilizări ale traversării în ordine:

• În cazul arborilor de căutare binare (BST), traversarea în ordine oferă noduri în ordine nedescrescătoare.
• Pentru a obține nodurile BST în ordine necrescătoare, poate fi utilizată o variație a traversării în ordine în care traversarea în ordine este inversată.
• Parcurgerea în ordine poate fi folosită pentru a evalua expresiile aritmetice stocate în arbori de expresii.

Fragment de cod pentru traversarea în ordine:

// Given a binary tree, print its nodes in inorder void printInorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->stânga);  // Apoi tipăriți datele nodului cout<< node->date<< ' ';  // Now recur on right child  printInorder(node->dreapta); }>>>Cdata);  // Acum se repetă pe copilul din dreapta printInorder(nod->right); }>>>Java

# A function to do inorder tree traversal def printInorder(root): if root: # First recur on left child printInorder(root.left) # Then print the data of node print(root.val, end=' '), # Now recur on right child printInorder(root.right)>

// Given a binary tree, print // its nodes in inorder void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  Console.Write(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>

// Given a binary tree, print its nodes in inorder function printInorder(node) {  if (node == null)  return;  // First recur on left child */  printInorder(node.left);  // Then print the data of node  console.log(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>

Inorder traversal of binary tree is 4 2 5 1 3>

Complexitatea timpului: PE)
Spațiu auxiliar: Dacă nu luăm în considerare dimensiunea stivei pentru apelurile de funcție, atunci O(1) în caz contrar O(h) unde h este înălțimea arborelui.

Precomandă Traversal :

Parcurgerea precomenzilor vizitează nodul în ordinea: Rădăcină -> Stânga -> Dreapta

obiect în programarea java

Algoritm pentru traversarea precomenzii:

Precomanda (arborele)

• Vizitați rădăcina.
• Traversați subarborele din stânga, adică apelați Precomanda (stânga->subarborele)
• Traversați subarborele din dreapta, adică apelați Precomanda (dreapta->subarborele)

Utilizări ale traversării precomenzilor:

• Parcurgerea precomenzilor este folosită pentru a crea o copie a arborelui.
• Parcurgerea precomenzilor este, de asemenea, folosită pentru a obține expresii de prefix pe un arbore de expresii.

Fragment de cod pentru traversarea precomenzii:

// Given a binary tree, print its nodes in preorder void printPreorder(struct Node* node) {  if (node == NULL)  return;  // First print data of node  cout << node->date<< ' ';  // Then recur on left subtree  printPreorder(node->stânga);  // Acum se repetă în subarborele din dreapta printPreorder(nod->right); }>>>Cdate);  // Apoi se repetă pe subarborele din stânga printPreorder(nod->left);  // Acum se repetă în subarborele din dreapta printPreorder(nod->right); }>>>Java

# A function to do preorder tree traversal def printPreorder(root): if root: # First print the data of node print(root.val, end=' '), # Then recur on left child printPreorder(root.left) # Finally recur on right child printPreorder(root.right)>

// Given a binary tree, print // its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  Console.Write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>

// Given a binary tree, print its nodes in preorder function printPreorder(node) {  if (node == null)  return;  // First print data of node  document.write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>

Preorder traversal of binary tree is 1 2 4 5 3>

Complexitatea timpului: PE)
Spațiu auxiliar: Dacă nu luăm în considerare dimensiunea stivei pentru apelurile de funcție, atunci O(1) în caz contrar O(h) unde h este înălțimea arborelui.

Traversarea comenzii poștale :

Parcurgerea postcomandă vizitează nodul în ordinea: Stânga -> Dreapta -> Rădăcină

Algoritm pentru traversarea postcomandă:

Algoritm Ordin poștal(arboresc)

• Traversați subarborele din stânga, adică apelați Postorder(stânga->subarborele)
• Traversați subarborele din dreapta, adică apelați Postorder(dreapta->subarborele)
• Vizitați rădăcina

Utilizări ale Mailorder Traversal:

• Traversarea post-comandă este folosită pentru a șterge arborele. Vedea întrebarea pentru ștergerea unui arbore pentru detalii.
• Parcurgerea post-comandă este, de asemenea, utilă pentru a obține expresia postfixă a unui arbore de expresii.
• Parcurgerea după comandă poate ajuta la algoritmii de colectare a gunoiului, în special în sistemele în care se utilizează gestionarea manuală a memoriei.

Fragment de cod pentru Mailorder Traversal:

// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->stânga);  // Apoi se repetă în subarborele din dreapta printPostorder(nod->right);  // Acum ocupă-te de nodul cout<< node->date<< ' '; }>

// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->stânga);  // Apoi se repetă în subarborele din dreapta printPostorder(nod->right);  // Acum se ocupă de nodul printf('%d', node->data); }>>>Java

# A function to do postorder tree traversal def printPostorder(root): if root: # First recur on left child printPostorder(root.left) # The recur on right child printPostorder(root.right) # Now print the data of node print(root.val, end=' '),>

// Given a binary tree, print its nodes according to // the 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  Console.Write(node.key + ' '); }>

// Given a binary tree, print its nodes according  // to the 'bottom-up' postorder traversal function printPostorder(node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  console.log(node.key + ' '); }>

Postorder traversal of binary tree is 4 5 2 3 1>

Traversarea ordinului la nivel :

Traversarea ordinului la nivel vizitează complet toate nodurile prezente la același nivel înainte de a vizita nivelul următor.

Algoritm pentru trecerea comenzii de nivel:

LevelOrder(arborele)

• Creați o coadă goală Q
• Puneți în coadă nodul rădăcină al arborelui la Q
• Buclă în timp ce Q nu este gol
  • Scoateți în coadă un nod de la Q și vizitați-l
  • Puneți în coadă copilul din stânga al nodului scos din coadă dacă acesta există
  • Puneți în coadă copilul drept al nodului scos din coadă dacă acesta există

Utilizări ale ordinii de nivel:

• Level Order Traversal este folosit în principal ca Breadth First Search pentru a căuta sau procesa nodurile nivel cu nivel.
• Traversarea Level Order este, de asemenea, folosită pentru Serializarea arborelui și deserializarea .

Fragment de cod pentru trecerea comenzii la nivel:

// Iterative method to find height of Binary Tree void printLevelOrder(Node* root) {  // Base Case  if (root == NULL)  return;  // Create an empty queue for level order traversal  queueq;  // Pune la coadă Root și inițializează înălțimea q.push(root);  while (q.empty() == false) { // Imprimă în fața cozii și scoate-l din coadă Node* node = q.front();  cout<< node->date<< ' ';  q.pop();  // Enqueue left child  if (node->stânga != NULL) q.push(nod->stânga);  // Pune la coada copilul drept if (nod->right != NULL) q.push(nod->right);  } }>>>Cdate);  // Așezați copilul stânga if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Pune în coadă copilul drept if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Scoateți la coadă nodul și faceți-l temp_node temp_node = deQueue(coadă, &front);  } }>>>Java>>Python3

// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuecoadă = coadă nouă();  queue.Enqueue(rădăcină);  while (coadă.Număr != 0) { Node tempNode = coadă.Decodă ();  Console.Write(tempNode.data + ' ');  // Așezați copilul stânga dacă (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // Pune în coadă copilul drept dacă (tempNode.right != null) { queue.Enqueue(tempNode.right);  } } }>>>JavaScript

Alte traversări ale copacilor:

1. Traversarea graniței
2. Traversare diagonală

1. Traversarea graniței :

Traversarea graniței a unui arbore include:

• limita stângă (nodurile din stânga, excluzând nodurile frunzelor)
• frunze (constă numai din nodurile frunzelor)
• limita dreaptă (nodurile din dreapta, excluzând nodurile frunzelor)

Algoritm pentru traversarea limitelor:

Traversare limită (arborele)

cel mai bun zâmbet din lume

• Dacă rădăcina nu este nulă:
  • Imprimați datele root
  • PrintLeftBoundary(root->left) // Imprimă nodurile de limita stângă
  • PrintLeafNodes(root->left) // Printează nodurile frunzelor subarborelului stâng
  • PrintLeafNodes(root->right) // Imprimă nodurile frunze din subarborele din dreapta
  • PrintRightBoundary(root->right) // Printează nodurile de delimitare din dreapta

Utilizări ale traversării limitelor:

• Traversarea limitelor ajută la vizualizarea structurii exterioare a unui arbore binar, oferind perspective asupra formei și limitelor acestuia.
• Parcursul limitelor oferă o modalitate de a accesa și modifica aceste noduri, permițând operațiuni precum tăierea sau repoziționarea nodurilor de delimitare.

2. Traversare diagonală

În Traversarea în diagonală a unui arbore, toate nodurile dintr-o singură diagonală vor fi imprimate unul câte unul.

Algoritm pentru traversarea diagonală:

Traversare diagonală (arborele):

• Dacă rădăcina nu este nulă:
  • Creați o hartă goală
  • DiagonalTraversalUtil(rădăcină, 0, M) // Apelați funcția de ajutor cu nivelul inițial al diagonalei 0
  • Pentru fiecare pereche cheie-valoare (Nivel diagonal, noduri) din M:
    • Pentru fiecare nod din noduri:
    • Tipăriți datele nodului

DiagonalTraversalUtil(nod, diagonalLevel, M):

• Dacă nodul este nul:
• Întoarcere
• Dacă diagonalLevel nu este prezent în M:
  • Creați o nouă listă în M pentru diagonalLevel
• Adăugați datele nodului la listă la M[diagonalLevel]
• DiagonalTraversalUtil(nod->stânga, diagonalLevel + 1, M) // Traversați copilul stâng cu nivelul diagonal crescut
• DiagonalTraversalUtil(nod->right, diagonalLevel, M) // Traversați copilul drept cu același nivel diagonal

Utilizări ale traversării diagonale:

• Traversarea în diagonală ajută la vizualizarea structurii ierarhice a arborilor binari, în special în structurile de date bazate pe arbore, cum ar fi arborii de căutare binari (BST) și arborii heap.
• Traversarea diagonală poate fi utilizată pentru a calcula sumele căilor de-a lungul diagonalelor într-un arbore binar.

Întrebări frecvente (FAQs) despre tehnicile de traversare a arborilor:

1. Ce sunt tehnicile de traversare a copacilor?

Tehnicile de traversare a arborilor sunt metode utilizate pentru a vizita și procesa toate nodurile dintr-o structură de date arborescentă. Ele vă permit să accesați fiecare nod exact o dată într-o manieră sistematică.

2. Care sunt tipurile comune de traversare a copacilor?

Tipurile obișnuite de parcurgere a arborilor sunt: ​​traversare în ordine, parcurgere precomandă, traversare după ordine, traversare în ordine de nivel (Breadth-First Search)

3. Ce este traversarea în ordine?

Traversarea în ordine este o metodă de parcurgere a adâncimii în care nodurile sunt vizitate în ordinea: subarborele stânga, nodul curent, subarborele din dreapta.

4. Ce este traversarea precomenzilor?

Parcurgerea precomandă este o metodă de parcurgere în profunzime, în care nodurile sunt vizitate în ordinea: nodul curent, subarborele stânga, subarborele din dreapta.

5. Ce este traversarea mandatelor poștale?

Parcurgerea postorder este o metodă de parcurgere în profunzime, în care nodurile sunt vizitate în ordinea: subarborele stânga, subarborele din dreapta, nodul curent.

6. Ce este traversarea ordinului la nivel?

Parcurgerea ordinii de nivel, cunoscută și sub numele de Breadth-First Search (BFS), vizitează nodurile nivel cu nivel, începând de la rădăcină și trecând la nivelul următor înainte de a parcurge mai adânc.

7. Când ar trebui să folosesc fiecare tehnică de traversare?

Parcurgerea în ordine este adesea folosită pentru arborii binari de căutare pentru a obține nodurile în ordine sortată.

Parcurgerea precomenzilor este utilă pentru a crea o copie a arborelui.

Parcurgerea post-comandă este folosită în mod obișnuit în arborele de expresii pentru a evalua expresiile.

data dactilografiată

Parcurgerea ordinii de nivel este utilă pentru a găsi calea cea mai scurtă între noduri.

8. Cum implementez algoritmi de traversare a arborilor?

Algoritmii de traversare a arborilor pot fi implementați recursiv sau iterativ, în funcție de cerințele specifice și limbajul de programare utilizat.

9. Pot fi aplicați algoritmi de traversare a arborilor altor structuri asemănătoare arborilor?

Da, algoritmii de traversare a arborilor pot fi adaptați pentru a traversa alte structuri asemănătoare arborilor, cum ar fi grămezi binari, arbori n-ari și grafice reprezentate ca arbori.

10. Există considerații de performanță atunci când alegeți o tehnică de traversare?

Considerațiile de performanță depind de factori precum dimensiunea și forma arborelui, memoria disponibilă și operațiunile specifice efectuate în timpul traversării. În general, alegerea tehnicii de traversare poate afecta eficiența anumitor operațiuni, așa că este important să alegeți metoda cea mai potrivită pentru cazul dumneavoastră de utilizare specific.

Alte tutoriale importante:

• Tutorial DSA
• Tutorial de proiectare a sistemului
• Foaia de parcurs pentru dezvoltarea software-ului
• Foaia de parcurs pentru a deveni manager de produs
• Învață SAP
• Învață SEO