Attraversamenti degli alberi (in ordine, preordine e postordine) con esempi

Cos'è l'attraversamento degli alberi?

Nella struttura ad albero dei dati, attraversamento significa visitare i nodi in un modo specifico. Esistono nodi2 tipi di attraversamenti. Generalmente questo tipo di attraversamento si basa sull'albero binario. Un albero binario significa che ogni nodo può avere un massimo di 2 nodi.

Un albero binario è una struttura dati ben nota. C'è anche un albero di ricerca binaria (BST). Questo tipo di attraversamento viene utilizzato per vari scopi. L'attraversamento dell'ordine di livello viene utilizzato per calcolare la profondità tra due nodi. Esiste un altro tipo di albero chiamato “AVL”, dove è necessario calcolare l'altezza di un nodo. Possiamo rappresentare un albero binario nell'array, ma per l'ottimizzazione della memoria utilizzeremo la struttura e il puntatore per fare riferimento al nodo successivo.

Tipi di attraversamento degli alberi

Come abbiamo discusso alberi binari, ora discutiamo i singoli tipi di attraversamenti. A seconda dei tipi, esistono due tipi di attraversamento. In precedenza abbiamo menzionato la necessità dell'ordine dei livelli o dell'attraversamento in ampiezza. Ora Traversata in profondità così come l'ordine post viene utilizzato per l'eliminazione di un nodo (ne parleremo più avanti), il preordine viene utilizzato per copiare un albero binario e "inorder" attraverserà l'albero in modo non decrescente.

Traversata in ampiezza
Traversata in profondità
Viaggio in preordine
Attraversamento post-ordine
Attraversamento in ordine

Traversata in ampiezza

È anche noto come attraversamento level-order. Consideriamo il seguente albero per dimostrare l'attraversamento level-order.

Quindi, inizieremo dal nodo radice “1”. Verrà contrassegnato come livello 1. Quindi l'algoritmo andrà a tutti i figli del nodo corrente. Visiteremo ora i nodi 2 e 3. Saranno contrassegnati come livello 2.

Dopodiché, poiché abbiamo 2 nodi nel livello 2, visiteremo anche i loro figli. Quindi visiteremo 5,6,8,7 e li contrassegneremo come livello 3. Ecco una cosa di cui non parlo,

Livello del nodo = livello del nodo genitore + 1

Livello 1: 1

Livello 2: 2 3

Livello 3: 5 6 8 7

Un algoritmo simile viene utilizzato per il BFS (Prima ricerca in ampiezza).

Ecco lo pseudocodice per l'attraversamento dell'ordine di livello:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

Albero Bianry trasversale in ordine

Facciamo lo stesso esempio di prima. In questo tipo di attraversamento visitiamo prima il sottoalbero sinistro, poi la radice e infine il sottoalbero destro. Per facilità di ricordare, possiamo dire che l'ordine va come sinistra-radice-destra.

Per l'intero albero, diciamo che la radice è 1. Ora seguirà l'algoritmo:

Visita il sottoalbero sinistro del nodo 1.
Il nodo corrente è 2 (poiché è il sottoalbero sinistro di 1)

Visita il sottoalbero sinistro di 2. Il nodo corrente questa volta sarà 5.
Passando a 5, non ha figli, quindi il nodo 5 verrà contrassegnato come visitato. Tornerà al nodo genitore; che è 2.
Quando viene visitato il sottoalbero sinistro di 2, ora verrà visitato anche 2.
algoritmo sposterà il nodo corrente nel sottoalbero destro del nodo 2, che è il nodo 6. Dopo aver visitato il nodo 6. Si sposterà al nodo genitore 2.
Una volta visitato il nodo 2, ora visiteremo il genitore di 2; che è il nodo 1.
Successivamente visiteremo il sottoalbero destro.

Quindi la traversata finale sarà simile a questa:

In ordine: 5 → 2 → 6 → 1 → 8 → 3 → 7

Ecco lo pseudocodice per l'attraversamento in ordine:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

Questo è l'algoritmo ricorsivo per l'attraversamento in ordine. Per il Albero di ricerca binario (BST), L'attraversamento in ordine fornisce la matrice ordinata di valori.

Attraversamento post-ordine

In questo attraversamento, attraverseremo prima il sottoalbero più a sinistra, poi quello più a destra dopo la radice. Tutti gli attraversamenti saranno in Post-Order. Dimostriamo un esempio:

Qui per root = 1,

Andremo prima al sottoalbero di sinistra. Quindi la radice diventerà 2.
Quindi 2 ha lasciato il sottoalbero, quindi andremo al nodo 5. Ora la radice è 5.
Non ha un sottoalbero sinistro, né ha un sottoalbero destro. Quindi, ora contrassegneremo il nodo 5 come visitato e andremo al suo nodo genitore.

Ora la radice è 2 e il suo sottoalbero sinistro è completamente visitato. Ci sposteremo ora al sottoalbero destro. Quindi la radice diventa 6.
Poiché il nodo 6 non ha sottoalberi sinistro e destro, contrassegneremo il nodo 6 visitato e ci sposteremo al nodo genitore 2.
Ora, sia il sottoalbero sinistro che quello destro vengono visitati per il nodo 2. Anche questo verrà contrassegnato come visitato.
Ci sposteremo al genitore del nodo 2, che è il nodo 1.
Il sottoalbero di sinistra viene visitato per la radice 1. Ora, analogamente, visiteremo il sottoalbero di destra.

Il cerchio contrassegnato è il sottoalbero destro. Ora visiteremo il sottoalbero di destra come abbiamo visitato quello di sinistra. Successivamente visiteremo il nodo. Quindi la traversata finale sarà:

PostOrdine: 5 → 6 → 2 → 8 → 7 → 3 → 1

Ecco lo pseudocodice per l'attraversamento post-ordine:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

Traversata del preordine

Per l'attraversamento del preordine, l'algoritmo visiterà prima il nodo radice, dopodiché si sposterà rispettivamente nel sottoalbero sinistro e destro. Per facilità di comprensione, possiamo pensare a visite trasversali di preordine come radice → sinistra-destra.

Quindi, selezioniamo il nodo 1 come radice.

Secondo l'algoritmo, verrà scoperta prima la radice, poi quella sinistra e infine quella destra.
Quindi visiteremo la radice 1. Quindi ci sposteremo al sottoalbero sinistro. La radice diventa 2.
Visiteremo il nodo 2 e ci sposteremo al suo sottoalbero sinistro. Quindi la radice diventa 3.
Visitiamo il nodo 3, quindi ci spostiamo al suo nodo genitore. Ora vengono visitati il nodo 2 e il suo sottoalbero sinistro. È ora di visitare il sottoalbero giusto.
Ci sposteremo sul sottoalbero destro, la radice diventa 4. Visiteremo 4. Poiché 4 non ha un nodo figlio, ci sposteremo sul suo genitore.
Ora la radice è 2 e viene visitata insieme ai suoi sottoalberi sinistro e destro. Quindi, ci sposteremo al suo nodo genitore. Ora la radice diventa 1.
Allo stesso modo, visiteremo il sottoalbero destro.

Preordine: 1 → 2 → 3 → 4 → 5 → 6 → 7

Ecco lo pseudocodice per l'attraversamento post-ordine:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

implementazione in Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) & gt;
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

Produzione:

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Implementazione in C

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}