În acest articol, vom discuta traversarea post-comandă în structura datelor.
Structurile liniare de date, cum ar fi stiva, matricea, coada etc., au o singură modalitate de a parcurge datele. Dar într-o structură de date ierarhică precum copac , există mai multe moduri de a parcurge datele. Deci, aici vom discuta un alt mod de a traversa structura de date arborescentă, și anume, traversarea comenzilor prin corespondență . Traversarea post-comandă este una dintre tehnicile de traversare utilizate pentru vizitarea nodului din arbore. Urmează principiul LRN (stânga-dreapta-nod) . Parcursul postorder este folosit pentru a obține expresia postfixă a unui arbore.
Următorii pași sunt utilizați pentru a efectua traversarea postcomandă:
- Traversați subarborele din stânga apelând recursiv funcția post-comanda.
- Traversați subarborele din dreapta apelând recursiv funcția post-comanda.
- Accesați partea de date a nodului curent.
Tehnica de traversare post-comandă urmează Rădăcină stânga dreapta politică. Aici, Left Right Root înseamnă că subarborele din stânga al nodului rădăcină este traversat mai întâi, apoi subarborele din dreapta și, în sfârșit, nodul rădăcină este traversat. Aici, numele Postorder în sine sugerează că nodul rădăcină al arborelui va fi traversat în cele din urmă.
Algoritm
Acum, să vedem algoritmul traversării post-comandă.
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
Exemplu de traversare a comenzii prin corespondență
Acum, să vedem un exemplu de traversare postcomandă. Va fi mai ușor de înțeles procesul de traversare postcomandă folosind un exemplu.
Nodurile cu culoare galbenă nu sunt încă vizitate. Acum, vom traversa nodurile arborelui de mai sus folosind traversarea post-comandă.
- Aici, 40 este nodul rădăcină. Mai întâi vizităm subarborele din stânga 40, adică 30. Nodul 30 va traversa și el în ordinea postării. 25 este subarborele din stânga al lui 30, deci este parcurs și în ordinea postării. Atunci 15 este subarborele din stânga lui 25. Dar 15 nu are subarborele, deci imprimare 15 și deplasați-vă spre subarborele din dreapta al lui 25.
- 28 este subarborele drept al lui 25 și nu are copii. Asa de, imprimare 28 .
- Acum, imprimare 25 , iar traversarea post-comandă pentru 25 e terminat.
- Apoi, deplasați-vă către subarborele din dreapta al lui 30. 35 este subarborele din dreapta lui 30 și nu are copii. Asa de, imprimare 35 .
- După care, imprimare 30 , iar traversarea post-comandă pentru 30 e terminat. Deci, subarborele din stânga al arborelui binar dat este parcurs.
- Acum, deplasați-vă spre subarborele din dreapta al lui 40, adică 50 și, de asemenea, va traversa în ordinea postării. 45 este subarborele din stânga lui 50 și nu are copii. Asa de, imprimare 45 și deplasați-vă spre subarborele din dreapta al lui 50.
- 60 este subarborele drept al lui 50, care va fi, de asemenea, parcurs în ordinea postării. 55 este subarborele din stânga lui 60 care nu are copii. Asa de, tipăriți 55 .
- Acum, imprimare 70, care este subarborele drept al lui 60.
- Acum, imprimare 60, iar parcurgerea post-comandă pentru 60 este finalizată.
- Acum, imprima 50, iar parcurgerea post-comandă pentru 50 este finalizată.
- În sfârșit, imprima 40, care este nodul rădăcină al arborelui binar dat, iar traversarea post-comandă pentru nodul 40 este finalizată.
Rezultatul final pe care îl vom obține după parcurgerea postcomandă este -
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Complexitatea traversării comenzilor prin corespondență
Complexitatea temporală a traversării post-comandă este Pe) , unde „n” este dimensiunea arborelui binar.
Întrucât, complexitatea spațială a traversării post-ordine este O(1) , dacă nu luăm în considerare dimensiunea stivei pentru apelurile de funcții. În caz contrar, complexitatea spațială a traversării post-comandă este Oh) , unde „h” este înălțimea copacului.
Implementarea traversării comenzilor prin corespondență
Acum, să vedem implementarea traversării post-comandă în diferite limbaje de programare.
Program: Scrieți un program pentru a implementa traversarea postcomandă în limbaj 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; } Ieșire
Program: Scrieți un program pentru a implementa traversarea postcomandă în 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></'
></'> Ieșire
După executarea codului de mai sus, rezultatul va fi -
Program: Scrieți un program pentru a implementa traversarea post-comandă în 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(); } } Ieșire
După executarea codului de mai sus, rezultatul va fi -
Deci, asta e totul despre articol. Sper că articolul vă va fi util și informativ.