U ovom ćemo članku raspravljati o obilasku postordera u strukturi podataka.
Linearne podatkovne strukture kao što su stog, niz, red čekanja itd. imaju samo jedan način za prolazak kroz podatke. Ali u hijerarhijskoj strukturi podataka kao što je drvo , postoji više načina za prelazak podataka. Dakle, ovdje ćemo raspravljati o drugom načinu prelaska strukture podataka stabla, tj. mail order traversal . Postorder traversal jedna je od tehnika obilaska koja se koristi za posjet čvoru u stablu. Slijedi princip LRN (lijevi-desni čvor) . Postorder traversal se koristi za dobivanje postfiksnog izraza stabla.
inorder stablo traversal
Sljedeći koraci koriste se za izvođenje postorder traverzacije:
- Pređite lijevo podstablo rekurzivnim pozivanjem funkcije postorder.
- Pređite desnim podstablom rekurzivnim pozivanjem funkcije postorder.
- Pristup podatkovnom dijelu trenutnog čvora.
Tehnika prolaska naloga slijedi Lijevo Desno Korijen politika. Ovdje Lijevi desni korijen znači da se prvo prelazi lijevo podstablo korijenskog čvora, zatim desno podstablo i na kraju se prelazi korijenski čvor. Ovdje samo ime Postordera sugerira da će korijenski čvor stabla konačno biti pređen.
Algoritam
Sada, da vidimo algoritam postorder traverzacije.
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
Primjer prolaska putem pošte
Pogledajmo sada primjer obilaska postordera. Na primjeru će biti lakše razumjeti proces postorder traversal-a.
Čvorovi sa žutom bojom još nisu posjećeni. Sada ćemo preći čvorove gornjeg stabla koristeći postorder traversal.
- Ovdje je 40 korijenski čvor. Prvo posjećujemo lijevo podstablo od 40, tj. 30. Čvor 30 će također preći u post redoslijedu. 25 je lijevo podstablo od 30, tako da se također prelazi u naknadnom redoslijedu. Onda je 15 lijevo podstablo od 25. Ali 15 nema podstablo, dakle ispis 15 i pomaknite se prema desnom podstablu od 25.
- 28 je desno podstablo od 25 i nema djece. Tako, ispis 28 .
- Sada, ispis 25 , i obilazak postordera za 25 gotovo je.
- Zatim se pomaknite prema desnom podstablu od 30. 35 je desno podstablo od 30 i nema djece. Tako, ispis 35 .
- nakon toga, ispis 30 , i obilazak postordera za 30 gotovo je. Dakle, prelazi se lijevo podstablo zadanog binarnog stabla.
- Sada se pomaknite prema desnom podstablu od 40, to jest 50, i ono će također preći po redoslijedu. 45 je lijevo podstablo od 50 i nema djece. Tako, ispis 45 i pomaknite se prema desnom podstablu od 50.
- 60 je desno podstablo od 50, koje će također biti pređeno u naknadnom redoslijedu. 55 je lijevo podstablo od 60 koje nema djece. Tako, ispis 55 .
- Sada, ispis 70, što je desno podstablo od 60.
- Sada, ispis 60, i dovršeno je prolaženje post naloga za 60.
- Sada, ispis 50, i dovršeno je prolaženje post naloga za 50.
- Napokon, ispis 40, koji je korijenski čvor zadanog binarnog stabla i dovršeno je prolaženje post naloga za čvor 40.
Konačni rezultat koji ćemo dobiti nakon postorder traverzacije je -
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Složenost narudžbe putem pošte
Vremenska složenost prolaska postordera je Na) , gdje je 'n' veličina binarnog stabla.
Dok je prostorna složenost postorder traverzacije O(1) , ako ne uzmemo u obzir veličinu stoga za pozive funkcija. U suprotnom, prostorna složenost postorder traverzacije je Oh) , gdje je 'h' visina stabla.
Implementacija prolaska putem pošte
Pogledajmo sada implementaciju postorder traversal-a u različitim programskim jezicima.
Program: Napišite program za implementaciju postorder traversal-a u C jeziku.
#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; } Izlaz
povezivanje baze podataka java
Program: Napišite program za implementaciju postorder traversal-a u 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></'
></'> Izlaz
Nakon izvršenja gornjeg koda, izlaz će biti -
Program: Napišite program za implementaciju postorder traversal-a u Javi.
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(); } } Izlaz
Nakon izvršenja gornjeg koda, izlaz će biti -
Dakle, to je sve o članku. Nadamo se da će vam članak biti koristan i informativan.