I denne artikkelen vil vi diskutere postorder-traversering i datastruktur.
Lineære datastrukturer som stack, array, queue, etc., har bare én måte å krysse dataene på. Men i en hierarkisk datastruktur som f.eks tre , er det flere måter å krysse dataene på. Så her vil vi diskutere en annen måte å krysse tredatastrukturen på, dvs. postordregjennomgang . Postorder-traverseringen er en av traverseringsteknikkene som brukes for å besøke noden i treet. Det følger prinsippet LRN (venstre-høyre-node) . Postorder-traversal brukes for å få postfix-uttrykket til et tre.
pytonsortert tuppel
Følgende trinn brukes for å utføre postordreovergangen:
- Gå gjennom det venstre undertreet ved å kalle postordrefunksjonen rekursivt.
- Gå gjennom det høyre undertreet ved å kalle postordrefunksjonen rekursivt.
- Få tilgang til datadelen av gjeldende node.
Postordre-traverseringsteknikken følger Venstre Høyre Rot Politikk. Her betyr venstre høyre rot at det venstre undertreet til rotnoden krysses først, deretter det høyre undertreet, og til slutt krysses rotnoden. Her antyder selve Postorder-navnet at treets rotknute til slutt ville bli krysset.
Algoritme
La oss nå se algoritmen for postorder-traversering.
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
Eksempel på postordregjennomgang
La oss nå se et eksempel på postordreovergang. Det vil være lettere å forstå prosessen med postordre-traversering ved å bruke et eksempel.
Nodene med gul farge er ikke besøkt ennå. Nå vil vi krysse nodene til treet ovenfor ved å bruke postorder-traversering.
- Her er 40 rotnoden. Vi besøker først det venstre undertreet på 40, dvs. 30. Node 30 vil også krysse i postordre. 25 er det venstre undertreet av 30, så det krysses også i postrekkefølge. Da er 15 venstre undertre av 25. Men 15 har ikke noe undertre, så utskrift 15 og gå mot høyre undertre på 25.
- 28 er det høyre undertreet av 25, og det har ingen barn. Så, utskrift 28 .
- Nå, utskrift 25 , og postordre-traverseringen for 25 er ferdig.
- Deretter går du mot høyre undertre på 30. 35 er høyre undertre på 30, og det har ingen barn. Så, trykk 35 .
- Etter det, print 30 , og postordre-traverseringen for 30 er ferdig. Så det venstre undertreet til det gitte binære treet krysses.
- Beveg deg nå mot høyre undertre på 40 som er 50, og det vil også gå i postrekkefølge. 45 er det venstre undertreet av 50, og det har ingen barn. Så, utskrift 45 og gå mot høyre undertre på 50.
- 60 er det høyre undertreet av 50, som også vil bli krysset i postordre. 55 er det venstre undertreet av 60 som ikke har barn. Så, trykk 55 .
- Nå, print 70, som er det høyre undertreet av 60.
- Nå, print 60, og postordreovergangen for 60 er fullført.
- Nå, print 50, og postordreovergangen for 50 er fullført.
- Endelig, print 40, som er rotnoden til det gitte binære treet, og postordre-traverseringen for node 40 er fullført.
Det endelige resultatet som vi vil få etter gjennomgang av postordre er -
nettverkstopologier
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Kompleksiteten i postordregjennomgang
Tidskompleksiteten til postordre-traversering er På) , hvor 'n' er størrelsen på binært tre.
Mens romkompleksiteten til postorder-traversering er O(1) , hvis vi ikke vurderer stabelstørrelsen for funksjonskall. Ellers er plasskompleksiteten til postorder-traversering Åh) , hvor 'h' er høyden på treet.
Gjennomføring av postordreovergang
La oss nå se implementeringen av postorder-traversering i forskjellige programmeringsspråk.
Program: Skriv et program for å implementere postordre-traversering på C-språk.
#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; } Produksjon
Program: Skriv et program for å implementere postordre-traversering i 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></'
></'> Produksjon
Etter utførelse av koden ovenfor, vil utgangen være -
Program: Skriv et program for å implementere postordre-traversering i Java.
forekomst av 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(); } } Produksjon
Etter utførelse av koden ovenfor, vil utgangen være -
Så det handler om artikkelen. Håper artikkelen vil være nyttig og informativ for deg.