In questo articolo discuteremo dell'attraversamento in ordine nella struttura dei dati.
tutorial sulla scintilla
Se vogliamo attraversare i nodi in ordine crescente, allora usiamo l'attraversamento inordine. Di seguito sono riportati i passaggi necessari per l'attraversamento dell'ordine:
- Visita tutti i nodi nel sottoalbero di sinistra
- Visita il nodo radice
- Visita tutti i nodi nel sottoalbero destro
Le strutture di dati lineari come stack, array, coda, ecc. hanno solo un modo per attraversare i dati. Ma in strutture di dati gerarchiche come albero, ci sono diversi modi per attraversare i dati. Qui discuteremo un altro modo per attraversare la struttura dei dati ad albero, ovvero l'attraversamento in ordine.
Esistono due approcci utilizzati per l'attraversamento in ordine:
- Attraversamento in ordine utilizzando la ricorsione
- Attraversamento in ordine utilizzando un metodo iterativo
Una tecnica di attraversamento in ordine segue la Radice sinistra destra politica. Qui, Radice Sinistra Destra significa che viene attraversato prima il sottoalbero sinistro del nodo radice, poi il nodo radice e infine il sottoalbero destro del nodo radice. Qui, l'ordine del nome stesso suggerisce che il nodo radice si trova tra i sottoalberi sinistro e destro.
Discuteremo l'attraversamento in ordine utilizzando sia tecniche ricorsive che iterative. Iniziamo innanzitutto con l'attraversamento in ordine utilizzando la ricorsione.
Attraversamento in ordine utilizzando la ricorsione
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Esempio di attraversamento in ordine
Vediamo ora un esempio di attraversamento in ordine. Sarà più semplice comprendere la procedura di attraversamento in ordine utilizzando un esempio.
I nodi di colore giallo non sono ancora visitati. Ora attraverseremo i nodi dell'albero precedente utilizzando l'attraversamento in ordine.
- Qui, 40 è il nodo radice. Ci spostiamo al sottoalbero sinistro di 40, cioè 30, che ha anche il sottoalbero 25, quindi ci spostiamo nuovamente al sottoalbero sinistro di 25, cioè 15. Qui, 15 non ha sottoalbero, quindi stampa 15 e spostarsi verso il suo nodo genitore, 25.
- Ora, stampa 25 e spostati nel sottoalbero destro di 25.
- Ora, stampa 28 e spostati sul nodo radice di 25 cioè 30.
- Quindi viene visitato il sottoalbero sinistro di 30. Ora, stampa 30 e spostati al figlio destro di 30.
- Ora, stampa 35 e spostati al nodo radice di 30.
- Ora, stampa il nodo radice 40 e spostarsi al sottoalbero destro.
- Ora attraversa ricorsivamente il sottoalbero destro di 40 che è 50.
50 hanno un sottoalbero quindi prima attraversa il sottoalbero sinistro di 50 che è 45. 45 non ha figli, quindi stampa 45 e spostarsi al suo nodo radice.
- Ora stampa 50 e spostati nel sottoalbero destro di 50 cioè 60.
- Ora attraversa ricorsivamente il sottoalbero destro di 50 che è 60. 60 ha un sottoalbero quindi prima attraversa il sottoalbero sinistro di 60 che è 55. 55 non ha figli, quindi stampa 55 e spostarsi al suo nodo radice.
- Ora stampa 60 e spostati nel sottoalbero destro di 60 cioè 70.
- Ora stampa 70.
Dopo il completamento dell'attraversamento in ordine, l'output finale è:
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Complessità dell'attraversamento in ordine
La complessità temporale dell'attraversamento in ordine è SU), dove 'n' è la dimensione dell'albero binario.
Mentre la complessità spaziale dell'attraversamento in ordine lo è O(1), se non consideriamo la dimensione dello stack per le chiamate di funzione. Altrimenti, la complessità spaziale dell'attraversamento in ordine lo è OH), dove 'h' è l'altezza dell'albero.
Implementazione dell'attraversamento in ordine
Ora vediamo l'implementazione dell'attraversamento in ordine in diversi linguaggi di programmazione.
Programma: Scrivere un programma per implementare l'attraversamento in ordine in linguaggio C.
#include #include struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(root->right); } int main() { struct node* root = createNode(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
The Inorder traversal of given binary tree is -
'); traverseInorder(root); return 0; } Produzione
Programma: Scrivere un programma per implementare l'attraversamento in ordine in C++.
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); cout<<' '<element<right); } int main() { struct node* root="createNode(39);" root->left = createNode(29); root->right = createNode(49); root->left->left = createNode(24); root->left->right = createNode(34); root->left->left->left = createNode(14); root->left->left->right = createNode(27); root->right->left = createNode(44); root->right->right = createNode(59); root->right->right->left = createNode(54); root->right->right->right = createNode(69); cout<<'
the inorder traversal of given binary tree is -
'; traverseinorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-14.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in C#.</p> <pre> using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(36); bt.root.left = new Node(26); bt.root.right = new Node(46); bt.root.left.left = new Node(21); bt.root.left.right = new Node(31); bt.root.left.left.left = new Node(11); bt.root.left.left.right = new Node(24); bt.root.right.left = new Node(41); bt.root.right.right = new Node(56); bt.root.right.right.left = new Node(51); bt.root.right.right.right = new Node(66); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-15.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-16.webp" alt="Inorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Produzione
Programma: Scrivere un programma per implementare l'attraversamento in ordine in Java.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } Produzione
Quindi, questo è tutto sull'articolo. Spero che l'articolo ti sia utile e informativo.