In dit artikel bespreken we de postorder-traversal in de datastructuur.
Lineaire datastructuren zoals stack, array, wachtrij, etc. hebben maar één manier om de data te doorkruisen. Maar in een hiërarchische gegevensstructuur zoals boom , zijn er meerdere manieren om de gegevens te doorkruisen. Hier zullen we dus een andere manier bespreken om de boomdatastructuur te doorkruisen, d.w.z. postorderverkeer . De postorder-traversal is een van de traverseringstechnieken die worden gebruikt om het knooppunt in de boom te bezoeken. Het volgt het principe LRN (links-rechts-knooppunt) . Postorder traversal wordt gebruikt om de postfix-expressie van een boom te verkrijgen.
De volgende stappen worden gebruikt om de postorder-traversal uit te voeren:
- Doorloop de linker deelboom door de postorderfunctie recursief aan te roepen.
- Doorloop de rechter deelboom door de postorderfunctie recursief aan te roepen.
- Toegang tot het gegevensgedeelte van het huidige knooppunt.
De postordertraversaltechniek volgt de Links Rechts Wortel beleid. Hier betekent Left Right Root dat eerst de linker subboom van het hoofdknooppunt wordt doorlopen, dan de rechter subboom en ten slotte het hoofdknooppunt. Hier suggereert de naam Postorder zelf dat het hoofdknooppunt van de boom eindelijk zou worden doorkruist.
tekenreeksen java toevoegen
Algoritme
Laten we nu eens kijken naar het algoritme van postorder-traversal.
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
Voorbeeld van postordertransactie
Laten we nu een voorbeeld bekijken van postorder-traversal. Het zal gemakkelijker zijn om het proces van postorder-traversal te begrijpen aan de hand van een voorbeeld.
De knooppunten met gele kleur zijn nog niet bezocht. Nu zullen we de knooppunten van de bovenstaande boom doorkruisen met behulp van postorder-traversal.
- Hier is 40 het hoofdknooppunt. We bezoeken eerst de linker subboom van 40, d.w.z. 30. Knooppunt 30 zal ook in postvolgorde doorlopen. 25 is de linker subboom van 30, dus deze wordt ook in de postorder doorlopen. Dan is 15 de linker deelboom van 25. Maar 15 heeft dus geen deelboom afdrukken 15 en ga naar de rechter deelboom van 25.
- 28 is de rechter deelboom van 25 en heeft geen kinderen. Dus, afdrukken 28 .
- Nu, afdrukken 25 , en de postorder-traversal voor 25 is klaar.
- Ga vervolgens naar de rechter deelboom van 30. 35 is de rechter deelboom van 30 en heeft geen kinderen. Dus, afdrukken 35 .
- Daarna, afdrukken 30 , en de postorder-traversal voor 30 is klaar. Dus de linker subboom van een gegeven binaire boom wordt doorlopen.
- Ga nu naar de rechter subboom van 40, dat is 50, en deze zal ook in de postvolgorde doorlopen. 45 is de linkerdeelboom van 50 en heeft geen kinderen. Dus, afdrukken 45 en ga naar de rechter deelboom van 50.
- 60 is de rechter subboom van 50, die ook in de postvolgorde zal worden doorlopen. 55 is de linkerdeelboom van 60 die geen kinderen heeft. Dus, afdrukken 55 .
- Nu, afdrukken 70, dat is de rechter deelboom van 60.
- Nu, afdrukken 60, en de postordertransactie voor 60 is voltooid.
- Nu, afdrukken 50, en de postordertransactie voor 50 is voltooid.
- Eindelijk, afdrukken 40, dat is het hoofdknooppunt van de gegeven binaire boom, en de postorder-doorgang voor knooppunt 40 is voltooid.
De uiteindelijke output die we krijgen na postorder-traversal is -
Java-wiskunde
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Complexiteit van het postorderverkeer
De tijdscomplexiteit van postorder-traversal is Op) , waarbij 'n' de grootte van de binaire boom is.
Terwijl de ruimtecomplexiteit van postorder-traversal dat wel is O(1) , als we geen rekening houden met de stapelgrootte voor functieaanroepen. Anders is de ruimtecomplexiteit van postorder-traversal dat wel Oh) , waarbij 'h' de hoogte van de boom is.
Implementatie van postordertraversal
Laten we nu eens kijken naar de implementatie van postorder traversal in verschillende programmeertalen.
Programma: Schrijf een programma om postorder traversal in C-taal te implementeren.
doe while loop java
#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; } Uitvoer
Programma: Schrijf een programma om postorder traversal in C++ te implementeren.
#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></'
></'> Uitvoer
handmatig testen
Na de uitvoering van de bovenstaande code zal de uitvoer zijn:
Programma: Schrijf een programma om postorder traversal in Java te implementeren.
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(); } } Uitvoer
Na de uitvoering van de bovenstaande code zal de uitvoer zijn:
Dus dat is alles over het artikel. Ik hoop dat het artikel nuttig en informatief voor u zal zijn.