logo

TechCodeview

Tecniche di attraversamento degli alberi: esercitazioni sulla struttura dei dati e sugli algoritmi

Tecniche di attraversamento degli alberi includere vari modi per visitare tutti i nodi dell'albero. A differenza delle strutture dati lineari (array, liste collegate, code, stack, ecc.) che hanno un solo modo logico per attraversarle, gli alberi possono essere attraversati in diversi modi. In questo articolo discuteremo di tutte le tecniche di attraversamento degli alberi insieme ai loro usi.



Tabella dei contenuti

Significato dell'attraversamento dell'albero:

Attraversamento degli alberi si riferisce al processo di visita o accesso a ciascun nodo dell'albero esattamente una volta in un determinato ordine. Gli algoritmi di attraversamento dell'albero ci aiutano a visitare ed elaborare tutti i nodi dell'albero. Poiché l'albero non è una struttura dati lineare, ci sono più nodi che possiamo visitare dopo aver visitato un determinato nodo. Esistono molteplici tecniche di attraversamento dell'albero che decidono l'ordine in cui i nodi dell'albero devono essere visitati.

Tecniche di attraversamento degli alberi:



Una struttura dati ad albero può essere attraversata nei seguenti modi:

  • Prima ricerca in profondità o DFS
    • Attraversamento in ordine
    • Traversata del preordine
    • Traslazione vaglia postale
  • Traversamento dell'ordine di livello o Ricerca prima in ampiezza o BFS

Attraversamento in ordine :

L'attraversamento in ordine visita il nodo nell'ordine: Sinistra -> Radice -> Destra




Algoritmo per l'attraversamento inordine:

In ordine (albero)

  • Attraversa il sottoalbero sinistro, ovvero chiama Inorder(left->subtree)
  • Visita la radice.
  • Attraversa il sottoalbero destro, ovvero chiama Inorder(right->subtree)

Usi dell'attraversamento in ordine ordinato:

come convertire da stringa a int
  • Nel caso degli alberi di ricerca binari (BST), l'attraversamento in ordine fornisce i nodi in ordine non decrescente.
  • Per ottenere i nodi di BST in ordine non crescente, è possibile utilizzare una variazione dell'attraversamento in ordine in cui l'attraversamento in ordine è invertito.
  • L'attraversamento in ordine può essere utilizzato per valutare le espressioni aritmetiche archiviate negli alberi delle espressioni.

Snippet di codice per l'attraversamento in ordine:

C++ 
// 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->Sinistra);  // Quindi stampa i dati del nodo cout<< node->dati<< ' ';  // Now recur on right child  printInorder(node->Giusto); }>
C 
// 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->Sinistra);  // Quindi stampa i dati del nodo printf('%d ', node->data);  // Ora ricorre sul figlio destro printInorder(node->right); }>
Giava 
void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  System.out.print(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Python3 
# 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)>
C# 
// 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); }>
Javascript 
// 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); }>
Produzione 
Inorder traversal of binary tree is 4 2 5 1 3>

Complessità temporale: SU)
Spazio ausiliario: Se non consideriamo la dimensione dello stack per le chiamate di funzione allora O(1) altrimenti O(h) dove h è l’altezza dell’albero.

Traversata del preordine :

L'attraversamento del preordine visita il nodo nell'ordine: Radice -> Sinistra -> Destra

Algoritmo per l'attraversamento del preordine:

Preordine(albero)

  • Visita la radice.
  • Attraversa il sottoalbero sinistro, ovvero chiama Preorder(left->subtree)
  • Attraversa il sottoalbero destro, ovvero chiama Preorder(right->subtree)

Usi dell'attraversamento del preordine:

  • L'attraversamento del preordine viene utilizzato per creare una copia dell'albero.
  • L'attraversamento del preordine viene utilizzato anche per ottenere espressioni di prefisso su un albero delle espressioni.

Snippet di codice per l'attraversamento del preordine:

C++ 
// 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->dati<< ' ';  // Then recur on left subtree  printPreorder(node->Sinistra);  // Ora ricorre sul sottoalbero destro printPreorder(node->right); }>
C 
// Given a binary tree, print its nodes in preorder void printPreorder(struct node* node) {  if (node == NULL)  return;  // First print data of node  printf('%d ', node->dati);  // Quindi ricorre sul sottoalbero sinistro printPreorder(node->left);  // Ora ricorre sul sottoalbero destro printPreorder(node->right); }>
Giava 
// Given a binary tree, print its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  System.out.print(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Python3 
# 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)>
C# 
// 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); }>
Javascript 
// 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); }>
Produzione 
Preorder traversal of binary tree is 1 2 4 5 3>

Complessità temporale: SU)
Spazio ausiliario: Se non consideriamo la dimensione dello stack per le chiamate di funzione allora O(1) altrimenti O(h) dove h è l’altezza dell’albero.

Traslazione vaglia postale :

L'attraversamento Postorder visita il nodo nell'ordine: Sinistra -> Destra -> Radice

Algoritmo per l'attraversamento del postorder:

Algoritmo Vaglia postale(albero)

  • Attraversa il sottoalbero sinistro, ovvero chiama Postorder(left->subtree)
  • Attraversa il sottoalbero destro, ovvero chiama Postorder(right->subtree)
  • Visita la radice

Usi dell'attraversamento degli ordini per corrispondenza:

  • L'attraversamento postordine viene utilizzato per eliminare l'albero. Vedere la domanda per l'eliminazione di un albero per dettagli.
  • L'attraversamento postordine è utile anche per ottenere l'espressione suffissa di un albero delle espressioni.
  • L'attraversamento postordine può aiutare negli algoritmi di garbage collection, in particolare nei sistemi in cui viene utilizzata la gestione manuale della memoria.

Snippet di codice per l'attraversamento degli ordini postali:

C++ 
// 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->Sinistra);  // Quindi ricorre sul sottoalbero destro printPostorder(node->right);  // Ora gestisci il nodo cout<< node->dati<< ' '; }>
C 
// 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->Sinistra);  // Quindi ricorre sul sottoalbero destro printPostorder(node->right);  // Ora gestisci il nodo printf('%d ', node->data); }>
Giava 
// 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  System.out.print(node.key + ' '); }>
Python3 
# 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=' '),>
C# 
// 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 + ' '); }>
Javascript 
// 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 + ' '); }>
Produzione 
Postorder traversal of binary tree is 4 5 2 3 1>

Attraversamento dell'ordine di livello :

Attraversamento dell'ordine di livello visita completamente tutti i nodi presenti nello stesso livello prima di visitare il livello successivo.

Algoritmo per l'attraversamento dell'ordine di livello:

OrdineLivello(albero)

  • Creare una coda vuota Q
  • Accoda il nodo radice dell'albero a Q
  • Ciclo mentre Q non è vuoto
    • Rimuovi dalla coda un nodo da Q e visitalo
    • Accoda il figlio sinistro del nodo rimosso dalla coda, se esiste
    • Accoda il figlio destro del nodo rimosso dalla coda, se esiste

Usi dell'ordine dei livelli:

  • L'attraversamento dell'ordine dei livelli viene utilizzato principalmente come ricerca in ampiezza per cercare o elaborare i nodi livello per livello.
  • Viene utilizzato anche l'attraversamento dell'ordine di livello Serializzazione e deserializzazione degli alberi .

Snippet di codice per l'attraversamento dell'ordine di livello:

C++ 
// 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;  // Accoda Root e inizializza l'altezza q.push(root);  while (q.empty() == false) { // Stampa la parte anteriore della coda e rimuovila dalla coda Node* node = q.front();  cout<< node->dati<< ' ';  q.pop();  // Enqueue left child  if (node->sinistra != NULL) q.push(nodo->sinistra);  // Accoda il figlio destro if (node->right != NULL) q.push(node->right);  } }>
C 
// Given a binary tree, print its nodes in level order // using array for implementing queue void printLevelOrder(struct node* root) {  int rear, front;  struct node** queue = createQueue(&front, &rear);  struct node* temp_node = root;  while (temp_node) {  printf('%d ', temp_node->dati);  // Accoda il figlio sinistro if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Accoda il figlio destro if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Rimuove il nodo dalla coda e lo rende temp_node temp_node = deQueue(queue, &front);  } }>
Giava 
// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuecoda = nuova Lista Collegata();  coda.add(root);  while (!queue.isEmpty()) { // poll() rimuove l'intestazione attuale.  Nodo tempNode = coda.poll();  System.out.print(tempNode.data + ' ');  // Accoda il figlio sinistro if (tempNode.left!= null) { tail.add(tempNode.left);  } // Accoda il figlio destro if (tempNode.right != null) { Queue.add(tempNode.right);  } } }>
Python3 
# Iterative Method to print the # height of a binary tree def printLevelOrder(root): # Base Case if root is None: return # Create an empty queue # for level order traversal queue = [] # Enqueue Root and initialize height queue.append(root) while(len(queue)>0): # Stampa la parte anteriore della coda e # la rimuove dalla coda print(queue[0].data, end=' ') node = Queue.pop(0) # Accoda il figlio sinistro se node.left non è Nessuno: coda.append(node.left) # Accoda il figlio destro se node.right non è None: coda.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuecoda = nuova coda();  coda.Enqueue(root);  while (queue.Count!= 0) { Nodo tempNode = coda.Dequeue();  Console.Write(tempNode.data + ' ');  // Accoda il figlio sinistro if (tempNode.left!= null) { tail.Enqueue(tempNode.left);  } // Accoda il figlio destro if (tempNode.right != null) { tail.Enqueue(tempNode.right);  } } }>
JavaScript 
// Function to perform level order traversal of a binary tree function printLevelOrder(root) {  // Create a deque to store nodes for traversal  const queue = new Deque();  // Add the root node to the queue  queue.enqueue(root);  // Continue traversal until the queue is empty  while (!queue.isEmpty()) {  // Remove and get the first node from the queue  const tempNode = queue.dequeue();  // Print the data of the current node  console.log(tempNode.data + ' ');  // Enqueue the left child if it exists  if (tempNode.left !== null) {  queue.enqueue(tempNode.left);  }  // Enqueue the right child if it exists  if (tempNode.right !== null) {  queue.enqueue(tempNode.right);  }  } }>

Altri attraversamenti sugli alberi:

  1. Attraversamento dei confini
  2. Traslazione diagonale

1. Attraversamento dei confini :

Attraversamento dei confini di un albero comprende:

  • confine sinistro (nodi a sinistra esclusi i nodi foglia)
  • foglie (costituite solo dai nodi foglia)
  • confine destro (nodi a destra esclusi i nodi fogliari)

Algoritmo per l'attraversamento dei confini:

Attraversamento del confine(albero)

  • Se root non è nullo:
    • Stampa i dati di root
    • PrintLeftBoundary(root->left) // Stampa i nodi del limite sinistro
    • PrintLeafNodes(root->left) // Stampa i nodi foglia del sottoalbero sinistro
    • PrintLeafNodes(root->right) // Stampa i nodi foglia del sottoalbero destro
    • PrintRightBoundary(root->right) // Stampa i nodi del confine destro

Usi dell'attraversamento dei confini:

  • L'attraversamento dei confini aiuta a visualizzare la struttura esterna di un albero binario, fornendo informazioni sulla sua forma e sui suoi confini.
  • L'attraversamento del confine fornisce un modo per accedere e modificare questi nodi, consentendo operazioni come l'eliminazione o il riposizionamento dei nodi del confine.

2. Traslazione diagonale

Nell'Attraversamento Diagonale di un Albero, tutti i nodi di un'unica diagonale verranno stampati uno per uno.

Algoritmo per l'attraversamento diagonale:

Diagonale trasversale(albero):

  • Se root non è nullo:
    • Crea una mappa vuota
    • DiagonalTraversalUtil(root, 0, M) // Chiama la funzione helper con livello diagonale iniziale 0
    • Per ogni coppia chiave-valore (diagonalLevel, nodi) in M:
      • Per ogni nodo nei nodi:
      • Stampa i dati del nodo

DiagonalTraversalUtil(nodo, diagonalLevel, M):

  • Se il nodo è nullo:
  • Ritorno
  • Se diagonalLevel non è presente in M:
    • Crea un nuovo elenco in M ​​per diagonalLevel
  • Aggiungi i dati del nodo all'elenco in M[diagonalLevel]
  • DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Attraversa il bambino sinistro con un livello diagonale aumentato
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Attraversa il figlio destro con lo stesso livello diagonale

Usi dell'attraversamento diagonale:

  • L'attraversamento diagonale aiuta a visualizzare la struttura gerarchica degli alberi binari, in particolare nelle strutture dati basate su alberi come alberi di ricerca binaria (BST) e alberi heap.
  • L'attraversamento diagonale può essere utilizzato per calcolare le somme dei percorsi lungo le diagonali in un albero binario.

Domande frequenti (FAQ) sulle tecniche di attraversamento degli alberi:

1. Cosa sono le tecniche di attraversamento degli alberi?

Le tecniche di attraversamento dell'albero sono metodi utilizzati per visitare ed elaborare tutti i nodi in una struttura dati ad albero. Permettono di accedere a ciascun nodo esattamente una volta in modo sistematico.

2. Quali sono i tipi più comuni di attraversamento degli alberi?

I tipi comuni di attraversamento dell'albero sono: attraversamento inordine, attraversamento preordine, attraversamento postordine, attraversamento ordine di livello (ricerca in ampiezza)

css sottolinea il testo

3. Cos'è l'attraversamento Inorder?

L'attraversamento in ordine è un metodo di attraversamento in profondità in cui i nodi vengono visitati nell'ordine: sottoalbero sinistro, nodo corrente, sottoalbero destro.

4. Cos'è l'attraversamento del preordine?

L'attraversamento del preordine è un metodo di attraversamento in profondità in cui i nodi vengono visitati nell'ordine: nodo corrente, sottoalbero sinistro, sottoalbero destro.

5. Cos'è il vaglia postale trasversale?

L'attraversamento postordine è un metodo di attraversamento in profondità in cui i nodi vengono visitati nell'ordine: sottoalbero sinistro, sottoalbero destro, nodo corrente.

6. Cos'è l'attraversamento dell'ordine di livello?

L'attraversamento dell'ordine di livello, noto anche come Breadth-First Search (BFS), visita i nodi livello per livello, partendo dalla radice e spostandosi al livello successivo prima di procedere più in profondità.

7. Quando dovrei utilizzare ciascuna tecnica di attraversamento?

L'attraversamento in ordine viene spesso utilizzato per gli alberi di ricerca binari per ottenere i nodi in ordine.

L'attraversamento del preordine è utile per creare una copia dell'albero.

L'attraversamento postordine viene comunemente utilizzato negli alberi delle espressioni per valutare le espressioni.

L'attraversamento dell'ordine dei livelli è utile per trovare il percorso più breve tra i nodi.

8. Come posso implementare gli algoritmi di attraversamento degli alberi?

Gli algoritmi di attraversamento degli alberi possono essere implementati in modo ricorsivo o iterativo, a seconda dei requisiti specifici e del linguaggio di programmazione utilizzato.

9. Gli algoritmi di attraversamento degli alberi possono essere applicati ad altre strutture simili ad alberi?

Sì, gli algoritmi di attraversamento degli alberi possono essere adattati per attraversare altre strutture simili ad alberi come heap binari, alberi n-ari e grafici rappresentati come alberi.

10. Ci sono considerazioni sulle prestazioni quando si sceglie una tecnica trasversale?

Le considerazioni sulle prestazioni dipendono da fattori quali la dimensione e la forma dell'albero, la memoria disponibile e le operazioni specifiche eseguite durante l'attraversamento. In generale, la scelta della tecnica di attraversamento può influire sull’efficienza di determinate operazioni, quindi è importante scegliere il metodo più adatto al proprio caso d’uso specifico.

Alcuni altri tutorial importanti:

  • Tutorial DSA
  • Esercitazione sulla progettazione del sistema
  • Tabella di marcia per lo sviluppo del software
  • Roadmap per diventare Product Manager
  • Impara SAP
  • Impara il SEO