Attraversamento in ordine è definito come un tipo di tecnica di attraversamento degli alberi che segue lo schema Sinistra-Radice-Destra, tale che:
- Il sottoalbero sinistro viene attraversato per primo
- Quindi viene attraversato il nodo radice per quel sottoalbero
- Infine viene attraversato il sottoalbero destro
Attraversamento in ordine
Algoritmo per l'attraversamento in ordine di alberi binari
L'algoritmo per l'attraversamento in ordine è mostrato come segue:
In ordine(radice):
- Seguire i passaggi da 2 a 4 fino a root != NULL
- In ordine (radice -> sinistra)
- Scrivi root -> dati
- In ordine (radice -> destra)
- Fine del ciclo
Come funziona l'attraversamento in ordine dell'albero binario?
Consideriamo il seguente albero:
Esempio di albero binario
Se eseguiamo un attraversamento in ordine in questo albero binario, l'attraversamento sarà il seguente:
Passo 1: L'attraversamento andrà da 1 al sottoalbero sinistro, ovvero 2, quindi da 2 alla radice del sottoalbero sinistro, ovvero 4. Ora 4 non ha un sottoalbero sinistro, quindi verrà visitato. Inoltre non ha alcun sottoalbero destro. Quindi niente più attraversamento da 4
Viene visitato il nodo 4
Passo 2: Poiché il sottoalbero sinistro di 2 viene visitato completamente, ora legge i dati del nodo 2 prima di spostarsi nel sottoalbero destro.
attraversamento delle vendite per corrispondenzaViene visitato il nodo 2
Passaggio 3: Ora verrà attraversato il sottoalbero destro di 2, ovvero ci si sposterà al nodo 5. Per il nodo 5 non esiste un sottoalbero sinistro, quindi viene visitato e successivamente l'attraversamento ritorna perché non esiste un sottoalbero destro del nodo 5.
Viene visitato il nodo 5
Passaggio 4: Come lo è il sottoalbero sinistro del nodo 1, verrà visitata la radice stessa, cioè il nodo 1.
Il nodo 1 viene visitato
Passaggio 5: Viene visitato il sottoalbero sinistro del nodo 1 e il nodo stesso. Quindi ora verrà attraversato il sottoalbero destro di 1, ovvero ci si sposterà al nodo 3. Poiché il nodo 3 non ha un sottoalbero sinistro, viene visitato.
Viene visitato il nodo 3
Passaggio 6: Viene visitato il sottoalbero sinistro del nodo 3 e il nodo stesso. Quindi attraversa il sottoalbero destro e visita il nodo 6. Ora l'attraversamento termina quando tutti i nodi sono attraversati.
Viene attraversato l'intero albero
Quindi l'ordine di attraversamento dei nodi è 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Programma per implementare l'attraversamento in ordine dell'albero binario:
Di seguito è riportata l'implementazione del codice dell'attraversamento in ordine:
C++
// C++ program for inorder traversals> #include> using> namespace> std;> // Structure of a Binary Tree Node> struct> Node {> >int> data;> >struct> Node *left, *right;> >Node(>int> v)> >{> >data = v;> >left = right = NULL;> >}> };> // Function to print inorder traversal> void> printInorder(>struct> Node* node)> {> >if> (node == NULL)> >return>;> >// First recur on left subtree> >printInorder(node->sinistra);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->Giusto); } // Codice driver int main() { struct Node* root = new Node(1); radice->sinistra = nuovo nodo(2); radice->destra = nuovo nodo(3); radice->sinistra->sinistra = nuovo nodo(4); root->sinistra->destra = nuovo nodo(5); radice->destra->destra = nuovo Nodo(6); // Chiamata di funzione cout<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
Giava
// Java program for inorder traversals> import> java.util.*;> // Structure of a Binary Tree Node> class> Node {> >int> data;> >Node left, right;> >Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Main class> class> GFG {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >System.out.print(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> main(String[] args)> >{> >Node root =>new> Node(>1>);> >root.left =>new> Node(>2>);> >root.right =>new> Node(>3>);> >root.left.left =>new> Node(>4>);> >root.left.right =>new> Node(>5>);> >root.right.right =>new> Node(>6>);> >// Function call> >System.out.println(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> // This code is contributed by prasad264> |
>
>
Python3
# Structure of a Binary Tree Node> class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Function to print inorder traversal> def> printInorder(node):> >if> node>is> None>:> >return> ># First recur on left subtree> >printInorder(node.left)> ># Now deal with the node> >print>(node.data, end>=>' '>)> ># Then recur on right subtree> >printInorder(node.right)> # Driver code> if> __name__>=>=> '__main__'>:> >root>=> Node(>1>)> >root.left>=> Node(>2>)> >root.right>=> Node(>3>)> >root.left.left>=> Node(>4>)> >root.left.right>=> Node(>5>)> >root.right.right>=> Node(>6>)> ># Function call> >print>(>'Inorder traversal of binary tree is:'>)> >printInorder(root)> |
>
convenzione di denominazione per Java
>
C#
// C# program for inorder traversals> using> System;> // Structure of a Binary Tree Node> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Class to store and print inorder traversal> public> class> BinaryTree {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >Console.Write(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> Main()> >{> >Node root =>new> Node(1);> >root.left =>new> Node(2);> >root.right =>new> Node(3);> >root.left.left =>new> Node(4);> >root.left.right =>new> Node(5);> >root.right.right =>new> Node(6);> >// Function call> >Console.WriteLine(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> |
>
>
Javascript
// JavaScript program for inorder traversals> // Structure of a Binary Tree Node> class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // Function to print inorder traversal> function> printInorder(node) {> >if> (node ===>null>) {> >return>;> >}> > >// First recur on left subtree> >printInorder(node.left);> > >// Now deal with the node> >console.log(node.data);> > >// Then recur on right subtree> >printInorder(node.right);> }> // Driver code> const root =>new> Node(1);> root.left =>new> Node(2);> root.right =>new> Node(3);> root.left.left =>new> Node(4);> root.left.right =>new> Node(5);> root.right.right =>new> Node(6);> // Function call> console.log(>'Inorder traversal of binary tree is: '>);> printInorder(root);> |
>
>Produzione
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Spiegazione:
Come funziona l'attraversamento in ordine
Analisi della complessità:
Complessità temporale: O(N) dove N è il numero totale di nodi. Perché attraversa tutti i nodi almeno una volta.
Spazio ausiliario: O(1) se non viene considerato lo spazio dello stack di ricorsione. Altrimenti O(h) dove h è l'altezza dell'albero
- Nel peggiore dei casi, H può essere lo stesso di N (quando l'albero è un albero inclinato)
- Nel migliore dei casi, H può essere lo stesso di calma (quando l'albero è un albero completo)
Casi d'uso di Inorder Traversal:
Nel caso del BST (Binary Search Tree), se in qualsiasi momento è necessario ottenere i nodi in ordine non decrescente, il modo migliore è implementare un attraversamento in ordine.
Articoli Correlati:
- Tipi di attraversamenti degli alberi
- Attraversamento iterativo in ordine
- Costruisci un albero binario dal preordine e dall'attraversamento inordine
- Attraversamento Morris per l'attraversamento in ordine dell'albero
- Attraversamento in ordine senza ricorsione