V tomto článku budeme diskutovať o prechode postorderom v dátovej štruktúre.
Lineárne dátové štruktúry, ako je zásobník, pole, front atď., majú iba jeden spôsob prechodu dát. Ale v hierarchickej dátovej štruktúre ako napr strom , existuje viacero spôsobov, ako prechádzať údajmi. Takže tu budeme diskutovať o inom spôsobe, ako prechádzať stromovou dátovou štruktúrou, t.j. zásielkový prechod . Postorder traversal je jednou z techník traverzovania používaných na návštevu uzla v strome. Riadi sa zásadou LRN (ľavý-pravý-uzol) . Postorder traversal sa používa na získanie postfixového výrazu stromu.
Na vykonanie prechodu postorderom sa používajú nasledujúce kroky:
- Prejdite ľavý podstrom volaním funkcie postorder rekurzívne.
- Prejdite pravým podstromom volaním funkcie postorder rekurzívne.
- Prístup k dátovej časti aktuálneho uzla.
Post order traversal technika nasleduje Ľavý pravý koreň politika. Ľavý pravý koreň tu znamená, že najprv sa prejde ľavý podstrom koreňového uzla, potom sa prejde pravý podstrom a nakoniec sa prejde koreňový uzol. Tu už samotný názov Postorder naznačuje, že by sa konečne prekročil koreňový uzol stromu.
Algoritmus
Teraz sa pozrime na algoritmus prechodu postorderom.
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
Príklad doručenia zásielky
Teraz sa pozrime na príklad prechodu postorderom. Na príklade bude jednoduchšie pochopiť proces prechodu postorderom.
Uzly so žltou farbou zatiaľ nie sú navštevované. Teraz budeme prechádzať uzly vyššie uvedeného stromu pomocou postorder traversal.
- Tu je 40 koreňový uzol. Najprv navštívime ľavý podstrom 40, t.j. 30. Uzol 30 bude tiež prechádzať v poradí. 25 je ľavý podstrom 30, takže sa prechádza aj v poštovom poradí. Potom 15 je ľavý podstrom 25. Ale 15 nemá žiadny podstrom, takže vytlačiť 15 a prejdite smerom k pravému podstromu 25.
- 28 je pravý podstrom 25 a nemá žiadne potomky. takže, vytlačiť 28 .
- teraz vytlačiť 25 , a postorder traversal pre 25 je dokončené.
- Ďalej prejdite smerom k pravému podstromu 30. 35 je pravý podstrom 30 a nemá žiadne potomky. takže, vytlačiť 35 .
- Potom, vytlačiť 30 , a postorder traversal pre 30 je dokončené. Prechádza sa teda ľavý podstrom daného binárneho stromu.
- Teraz sa posuňte smerom k pravému podstromu 40, čo je 50, a bude tiež prechádzať v poradí. 45 je ľavý podstrom 50 a nemá žiadne potomky. takže, tlač 45 a posuňte sa smerom k pravému podstromu 50.
- 60 je pravý podstrom 50, ktorý sa bude prechádzať aj pri poštovom príkaze. 55 je ľavý podstrom 60, ktorý nemá žiadne potomky. takže, vytlačiť 55 .
- teraz tlač 70, čo je pravý podstrom 60.
- teraz tlač 60, a prechod na objednávku pre 60 je dokončený.
- teraz tlač 50, a prechod pošty za 50 je dokončený.
- Nakoniec, tlač 40, ktorý je koreňovým uzlom daného binárneho stromu a prechod po príkaze pre uzol 40 je dokončený.
Konečný výstup, ktorý dostaneme po prechode postorderom, je -
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Zložitosť prechodu zásielky
Časová náročnosť prechodu postorderom je O(n) , kde 'n' je veľkosť binárneho stromu.
Zatiaľ čo priestorová zložitosť prechodu postorderom je O(1) , ak neberieme do úvahy veľkosť zásobníka pre volania funkcií. Inak priestorová náročnosť prechodu postorderom je O(h) , kde 'h' je výška stromu.
Implementácia zásielkového prechodu
Teraz sa pozrime na implementáciu postorder traversal v rôznych programovacích jazykoch.
Program: Napíšte program na implementáciu postorder traversal v jazyku 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; } Výkon
Program: Napíšte program na implementáciu postorder traversal v 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></'
></'> Výkon
Po vykonaní vyššie uvedeného kódu bude výstupom -
Program: Napíšte program na implementáciu postorder traversal v Jave.
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(); } } Výkon
Po vykonaní vyššie uvedeného kódu bude výstupom -
Tak, to je o článku všetko. Dúfam, že článok bude pre vás užitočný a poučný.