V tomto článku se budeme zabývat přechodem postorderu v datové struktuře.
Lineární datové struktury, jako je zásobník, pole, fronta atd., mají pouze jeden způsob, jak data procházet. Ale v hierarchické datové struktuře jako je např strom , existuje několik způsobů, jak data procházet. Zde tedy probereme další způsob, jak procházet stromovou datovou strukturou, tj. zásilkový obchod . Postorder traversal je jednou z technik procházení používaných k návštěvě uzlu ve stromu. Dodržuje princip LRN (levý-pravý-uzel) . Postorder traversal se používá k získání postfixového výrazu stromu.
K provedení postorderu se používají následující kroky:
- Projděte levý podstrom voláním funkce postorder rekurzivně.
- Projděte pravý podstrom voláním funkce postorder rekurzivně.
- Přístup k datové části aktuálního uzlu.
Technika post order traversal následuje Levý pravý kořen politika. Zde Left Right Root znamená, že se nejprve projde levý podstrom kořenového uzlu, potom pravý podstrom a nakonec se projde kořenový uzel. Zde už samotný název Postorder napovídá, že kořenový uzel stromu bude konečně překročen.
bash rozdělit řetězec oddělovačem
Algoritmus
Nyní se podívejme na algoritmus procházení postorderem.
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
Příklad doručení zásilky
Nyní se podívejme na příklad procházení postorderem. Na příkladu bude snazší pochopit proces procházení postorderem.
Uzly se žlutou barvou zatím nejsou navštěvovány. Nyní budeme procházet uzly výše uvedeného stromu pomocí postorder traversal.
- Zde je 40 kořenový uzel. Nejprve navštívíme levý podstrom 40, tj. 30. Uzel 30 bude také procházet v poštovním pořadí. 25 je levý podstrom 30, takže se také prochází v poštovním pořadí. Pak 15 je levý podstrom 25. Ale 15 žádný podstrom nemá, takže tisknout 15 a přejděte k pravému podstromu 25.
- 28 je správný podstrom 25 a nemá žádné potomky. Tak, tisknout 28 .
- Nyní, tisknout 25 , a postorder traversal pro 25 je dokončena.
- Dále přejděte k pravému podstromu 30. 35 je pravý podstrom 30 a nemá žádné potomky. Tak, tisknout 35 .
- Potom, tisknout 30 , a postorder traversal pro 30 je dokončena. Prochází se tedy levý podstrom daného binárního stromu.
- Nyní přejděte k pravému podstromu 40, to je 50, a bude také procházet v pořadí. 45 je levý podstrom 50 a nemá žádné potomky. Tak, tisk 45 a přejděte k pravému podstromu 50.
- 60 je pravý podstrom 50, který bude také procházet v poštovním pořadí. 55 je levý podstrom 60, který nemá žádné potomky. Tak, tisk 55 .
- Nyní, tisk 70, což je pravý podstrom 60.
- Nyní, tisk 60, a přechod na objednávku za 60 je dokončen.
- Nyní, tisk 50, a přechod na objednávku za 50 je dokončen.
- Nakonec, tisk 40, což je kořenový uzel daného binárního stromu a procházení příkazu pro uzel 40 je dokončeno.
Konečný výstup, který dostaneme po průchodu postorderem, je -
java jak převést řetězec na int
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Složitost zásilkového obchodu
Časová složitost průchodu postorderem je Na) , kde 'n' je velikost binárního stromu.
Kdežto prostorová složitost procházení postorderem je O(1) , pokud neuvažujeme velikost zásobníku pro volání funkcí. Jinak prostorová složitost postorder traversal je Ach) , kde 'h' je výška stromu.
Implementace zásilkového obchodu
Nyní se podívejme na implementaci postorder traversal v různých programovacích jazycích.
Program: Napište program pro implementaci postorder traversal v jazyce C.
řetězec na int v jazyce 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; } Výstup
Program: Napište program pro implementaci 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ýstup
včetně programování c
Po provedení výše uvedeného kódu bude výstupem -
Program: Napište program pro implementaci postorder traversal v Javě.
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ýstup
Po provedení výše uvedeného kódu bude výstupem -
Tak to je k článku vše. Doufám, že vám článek bude užitečný a informativní.