I denne artikel vil vi diskutere postorder-gennemgangen i datastruktur.
Lineære datastrukturer såsom stak, array, kø osv. har kun én måde at krydse dataene på. Men i en hierarkisk datastruktur som f.eks træ , er der flere måder at krydse dataene på. Så her vil vi diskutere en anden måde at krydse trædatastrukturen på, dvs. postordregennemgang . Postorder-traversal er en af de traverseringsteknikker, der bruges til at besøge knudepunktet i træet. Det følger princippet LRN (venstre-højre-node) . Postorder traversal bruges til at få postfix-udtrykket af et træ.
python sorteret tuple
Følgende trin bruges til at udføre postordre-gennemgangen:
- Gå gennem det venstre undertræ ved at kalde postorder-funktionen rekursivt.
- Gå gennem det højre undertræ ved at kalde postorder-funktionen rekursivt.
- Få adgang til datadelen af den aktuelle node.
Postordre-traversalteknikken følger Venstre Højre Rod politik. Her betyder Venstre højre rod, at det venstre undertræ af rodknuden krydses først, derefter det højre undertræ, og til sidst krydses rodknuden. Her tyder selve Postorder-navnet på, at træets rodknude til sidst ville blive krydset.
Algoritme
Lad os nu se algoritmen for postorder-gennemgang.
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å postordregennemgang
Lad os nu se et eksempel på postordre-gennemgang. Det vil være lettere at forstå processen med postordre-gennemgang ved hjælp af et eksempel.
Noderne med gul farve er ikke besøgt endnu. Nu vil vi krydse knudepunkterne i ovenstående træ ved at bruge postorder-gennemgang.
- Her er 40 rodknuden. Vi besøger først det venstre undertræ på 40, dvs. 30. Node 30 vil også krydse i postordre. 25 er det venstre undertræ af 30, så det krydses også i postordre. Så er 15 det venstre undertræ af 25. Men 15 har ikke noget undertræ, så print 15 og bevæg dig mod højre undertræ af 25.
- 28 er det rigtige undertræ af 25, og det har ingen børn. Så, print 28 .
- Nu, print 25 , og postordre-gennemgangen for 25 er færdig.
- Bevæg dig derefter mod det højre undertræ på 30. 35 er det højre undertræ på 30, og det har ingen børn. Så, print 35 .
- Efter det, print 30 , og postordre-gennemgangen for 30 er færdig. Så det venstre undertræ af et givet binært træ krydses.
- Bevæg dig nu mod det højre undertræ af 40, som er 50, og det vil også krydse i postordrefølge. 45 er det venstre undertræ af 50, og det har ingen børn. Så, print 45 og bevæg dig mod det højre undertræ af 50.
- 60 er det højre undertræ af 50, som også vil blive krydset i postordre. 55 er det venstre undertræ af 60, der ikke har nogen børn. Så, tryk 55 .
- Nu, tryk 70, hvilket er det højre undertræ af 60.
- Nu, print 60, og postordregennemgangen for 60 er gennemført.
- Nu, print 50, og postordregennemgangen for 50 er gennemført.
- Endelig, print 40, som er rodknudepunktet for det givne binære træ, og postordregennemgangen for knudepunkt 40 er fuldført.
Det endelige output, som vi vil få efter postordre-gennemgang er -
netværkstopologier
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Kompleksiteten af postordregennemgang
Tidskompleksiteten af postordergennemgang er På) , hvor 'n' er størrelsen af binært træ.
Hvorimod rumkompleksiteten af postordergennemgang er O(1) , hvis vi ikke overvejer stakstørrelsen for funktionskald. Ellers er pladskompleksiteten af postorder-gennemgang O(h) , hvor 'h' er højden af træet.
Implementering af postordregennemgang
Lad os nu se implementeringen af postorder-traversal i forskellige programmeringssprog.
Program: Skriv et program til at implementere postordre-traversal i C-sprog.
#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; } Produktion
Program: Skriv et program til at implementere postordre-traversal 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></'
></'> Produktion
Efter udførelse af ovenstående kode vil outputtet være -
Program: Skriv et program til at implementere postordre-traversal i Java.
alfabetets tal
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(); } } Produktion
Efter udførelse af ovenstående kode vil outputtet være -
Så det handler om artiklen. Håber artiklen vil være nyttig og informativ for dig.