I den här artikeln kommer vi att diskutera postorderövergången i datastruktur.
Linjära datastrukturer som stack, array, kö etc. har bara ett sätt att gå igenom data. Men i en hierarkisk datastruktur som t.ex träd , det finns flera sätt att gå igenom data. Så här kommer vi att diskutera ett annat sätt att korsa träddatastrukturen, dvs. postorder traversal . Postorder-traverseringen är en av de traverseringstekniker som används för att besöka noden i trädet. Det följer principen LRN (vänster-höger-nod) . Postorder-traversal används för att få postfix-uttrycket för ett träd.
Följande steg används för att utföra postorderövergången:
- Gå igenom det vänstra underträdet genom att anropa postorderfunktionen rekursivt.
- Gå igenom det högra underträdet genom att anropa postorderfunktionen rekursivt.
- Gå till datadelen av den aktuella noden.
Postorder-traverseringstekniken följer Vänster Höger Rot politik. Här betyder Left Right Root att det vänstra underträdet av rotnoden korsas först, sedan det högra underträdet, och slutligen korsas rotnoden. Här antyder själva Postorder-namnet att trädets rotnod äntligen skulle korsas.
sträng för att chatta
Algoritm
Låt oss nu se algoritmen för genomgång av postorder.
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
Example of postorder traversal
Låt oss nu se ett exempel på genomgång av postorder. Det kommer att bli lättare att förstå processen med att gå igenom postorder med hjälp av ett exempel.
Noderna med gul färg är inte besökta ännu. Nu kommer vi att korsa noderna i ovanstående träd med hjälp av postorder-traversering.
- Här är 40 rotnoden. Vi besöker först det vänstra underträdet på 40, dvs. 30. Nod 30 kommer också att korsa i postordning. 25 är det vänstra underträdet av 30, så det korsas också i postordning. Då är 15 det vänstra underträdet av 25. Men 15 har inget underträd, så tryck 15 och flytta mot höger underträd av 25.
- 28 är det högra underträdet av 25, och det har inga barn. Så, tryck 28 .
- Nu, tryck 25 , och postordergenomgången för 25 är klar.
- Gå sedan mot det högra underträdet av 30. 35 är det högra underträdet av 30, och det har inga barn. Så, tryck 35 .
- Efter det, tryck 30 , och postordergenomgången för 30 är klar. Så det vänstra underträdet av ett givet binärt träd korsas.
- Gå nu mot det högra underträdet av 40, det vill säga 50, och det kommer också att gå i postordning. 45 är det vänstra underträdet av 50, och det har inga barn. Så, tryck 45 och flytta mot höger underträd av 50.
- 60 är det högra underträdet av 50, som också kommer att passeras i postordning. 55 är det vänstra underträdet av 60 som inte har några barn. Så, tryck 55 .
- Nu, tryck 70, vilket är det högra underträdet av 60.
- Nu, tryck 60, och postorderövergången för 60 är klar.
- Nu, tryck 50, och postorderövergången för 50 är klar.
- Äntligen, tryck 40, som är rotnoden för det givna binära trädet, och postordergenomgången för nod 40 är slutförd.
Den slutliga utdata som vi kommer att få efter genomgång av postorder är -
hur många miljoner är det i en miljard
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Complexity of Postorder traversal
Tidskomplexiteten för genomgång av postorder är På) , där 'n' är storleken på ett binärt träd.
Medan rymdkomplexiteten i postorder-traversering är O(1) , om vi inte tar hänsyn till stackstorleken för funktionsanrop. Annars är utrymmeskomplexiteten av postorder-traversering Åh) , där 'h' är trädets höjd.
Implementation of Postorder traversal
Låt oss nu se implementeringen av postorder-traversering i olika programmeringsspråk.
Program: Skriv ett program för att implementera postordertraversering i C-språk.
sammansatt primärnyckel
#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 ett program för att implementera postordertraversal 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
java mvc
Efter exekvering av ovanstående kod kommer utgången att vara -
Program: Skriv ett program för att implementera postordertraversal i 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(); } } Produktion
Efter exekvering av ovanstående kod kommer utgången att vara -
Så det handlar om artikeln. Hoppas artikeln kommer att vara användbar och informativ för dig.