In questo articolo discuteremo dell'attraversamento del postordine nella struttura dei dati.
Le strutture di dati lineari come stack, array, coda, ecc. hanno solo un modo per attraversare i dati. Ma in una struttura di dati gerarchica come albero , esistono diversi modi per esaminare i dati. Quindi, qui discuteremo un altro modo per attraversare la struttura dei dati ad albero, vale a dire, attraversamento delle vendite per corrispondenza . L'attraversamento postorder è una delle tecniche di attraversamento utilizzate per visitare il nodo dell'albero. Segue il principio LRN (nodo sinistro-destro) . L'attraversamento postordine viene utilizzato per ottenere l'espressione suffissa di un albero.
Per eseguire l'attraversamento postorder vengono utilizzati i seguenti passaggi:
- Attraversa il sottoalbero sinistro chiamando ricorsivamente la funzione postorder.
- Attraversa il sottoalbero destro chiamando ricorsivamente la funzione postorder.
- Accedi alla parte dati del nodo corrente.
La tecnica di attraversamento dell'ordine post segue il Radice sinistra destra politica. Qui, Radice Sinistra Destra significa che viene attraversato prima il sottoalbero sinistro del nodo radice, poi il sottoalbero destro e infine il nodo radice. Qui, il nome stesso Postorder suggerisce che il nodo radice dell'albero sarà finalmente attraversato.
Algoritmo
Vediamo ora l'algoritmo di attraversamento del postorder.
assolutamente unico
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: POSTORDER(TREE -> LEFT) Step 3: POSTORDER(TREE -> RIGHT) Step 4: Write TREE -> DATA [END OF LOOP] Step 5: END
Esempio di attraversamento di ordini per corrispondenza
Vediamo ora un esempio di attraversamento postorder. Sarà più semplice comprendere il processo di attraversamento del postorder utilizzando un esempio.
I nodi di colore giallo non sono ancora visitati. Ora attraverseremo i nodi dell'albero sopra usando l'attraversamento postorder.
- Qui, 40 è il nodo radice. Visitiamo prima il sottoalbero sinistro di 40, cioè 30. Anche il nodo 30 lo attraverserà in ordine successivo. 25 è il sottoalbero sinistro di 30, quindi viene attraversato anche in ordine successivo. Allora 15 è il sottoalbero sinistro di 25. Ma 15 non ha un sottoalbero, quindi stampa 15 e spostarsi verso il sottoalbero destro di 25.
- 28 è il sottoalbero destro di 25 e non ha figli. COSÌ, stampa 28 .
- Ora, stampa 25 e l'attraversamento postorder per 25 è finito.
- Successivamente, spostati verso il sottoalbero destro di 30. 35 è il sottoalbero destro di 30 e non ha figli. COSÌ, stampa 35 .
- Dopo di che, stampa 30 e l'attraversamento postorder per 30 è finito. Quindi, viene attraversato il sottoalbero sinistro di un dato albero binario.
- Ora spostati verso il sottoalbero destro di 40, ovvero 50, e anch'esso attraverserà in ordine postale. 45 è il sottoalbero sinistro di 50 e non ha figli. COSÌ, stampa 45 e spostarsi verso il sottoalbero destro di 50.
- 60 è il sottoalbero destro di 50, che verrà anch'esso attraversato in ordine successivo. 55 è il sottoalbero sinistro di 60 che non ha figli. COSÌ, stampa 55 .
- Ora, stampa 70, che è il sottoalbero destro di 60.
- Ora, stampa 60, e l'attraversamento dell'ordine postale per 60 è stato completato.
- Ora, stampa 50, e l'attraversamento dell'ordine postale per 50 è stato completato.
- Infine, stampa 40, che è il nodo radice del dato albero binario, e l'attraversamento del post-ordine per il nodo 40 è completato.
L'output finale che otterremo dopo l'attraversamento postorder è:
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
arp-un comando
Complessità dell'attraversamento degli ordini per corrispondenza
La complessità temporale dell'attraversamento del postordine è SU) , dove 'n' è la dimensione dell'albero binario.
Mentre la complessità spaziale dell'attraversamento postordine lo è O(1) , se non consideriamo la dimensione dello stack per le chiamate di funzione. Altrimenti, la complessità spaziale dell'attraversamento postordine lo è OH) , dove 'h' è l'altezza dell'albero.
Implementazione dell'attraversamento degli ordini per corrispondenza
Ora vediamo l'implementazione del postorder traversal in diversi linguaggi di programmazione.
Programma: Scrivere un programma per implementare l'attraversamento postorder in linguaggio C.
#include #include struct node { s 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 postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); printf(' %d ', root->element); } 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 Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } Produzione
Programma: Scrivere un programma per implementare l'attraversamento postorder 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 postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); cout<<' '<element<left="createNode(28);" root->right = createNode(48); root->left->left = createNode(23); root->left->right = createNode(33); root->left->left->left = createNode(13); root->left->left->right = createNode(26); root->right->left = createNode(43); root->right->right = createNode(58); root->right->right->left = createNode(53); root->right->right->right = createNode(68); cout<<'
the postorder traversal of given binary tree is -
'; traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-14.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder 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 traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePostorder() { traversePostorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(37); bt.root.left = new Node(27); bt.root.right = new Node(47); bt.root.left.left = new Node(22); bt.root.left.right = new Node(32); bt.root.left.left.left = new Node(12); bt.root.left.left.right = new Node(25); bt.root.right.left = new Node(42); bt.root.right.right = new Node(57); bt.root.right.right.left = new Node(52); bt.root.right.right.right = new Node(67); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-15.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-16.webp" alt="Postorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Produzione
Dopo l'esecuzione del codice sopra, l'output sarà:
Programma: Scrivere un programma per implementare l'attraversamento postorder in Java.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } Produzione
Dopo l'esecuzione del codice sopra, l'output sarà:
matematica Java casuale
Quindi, questo è tutto sull'articolo. Spero che l'articolo ti sia utile e informativo.