Šajā rakstā mēs apspriedīsim postorder šķērsošanu datu struktūrā.
Lineārām datu struktūrām, piemēram, kaudze, masīvs, rinda utt., ir tikai viens veids, kā šķērsot datus. Bet hierarhiskā datu struktūrā, piemēram, koks , ir vairāki veidi, kā pārvietot datus. Tātad, šeit mēs apspriedīsim citu veidu, kā šķērsot koka datu struktūru, t.i., pasta pasūtījumu šķērsošana . Postorder šķērsošana ir viena no šķērsošanas metodēm, ko izmanto koka mezgla apmeklēšanai. Tas seko principam LRN (kreisais-labais-mezgls) . Postorder traversal tiek izmantots, lai iegūtu koka postfiksa izteiksmi.
pēc pasūtījuma šķērsošana
Lai veiktu pēcpasūtīšanas šķērsošanu, tiek izmantotas šādas darbības:
- Pārejiet pa kreiso apakškoku, rekursīvi izsaucot postorder funkciju.
- Pārejiet pa labo apakškoku, rekursīvi izsaucot postorder funkciju.
- Piekļūstiet pašreizējā mezgla datu daļai.
Pēc pasūtījuma šķērsošanas tehnika ir šāda Kreisā labā sakne politiku. Šeit Left Right Root nozīmē, ka vispirms tiek šķērsots saknes mezgla kreisais apakškoks, pēc tam labais apakškoks un, visbeidzot, tiek šķērsots saknes mezgls. Šeit pats Postorder nosaukums liecina, ka koka saknes mezgls beidzot tiks šķērsots.
Algoritms
Tagad apskatīsim pēckārtošanas šķērsošanas algoritmu.
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
Pasūtījuma pa pastu šķērsošanas piemērs
Tagad apskatīsim piemēru pēc pasūtījuma šķērsošanas. Izmantojot piemēru, būs vieglāk izprast pēcdošanas procesu.
Mezgli ar dzeltenu krāsu vēl nav apmeklēti. Tagad mēs šķērsosim augšējā koka mezglus, izmantojot postorder traversal.
- Šeit 40 ir saknes mezgls. Vispirms mēs apmeklējam kreiso apakškoku 40, t.i., 30. 30. mezgls arī šķērsos pasta secībā. 25 ir 30 kreisais apakškoks, tāpēc tas tiek šķērsots arī pēc kārtas. Tad 15 ir 25 kreisais apakškoks. Bet 15 nav apakškoka, tāpēc drukāt 15 un virzieties uz labo apakškoku 25.
- 28 ir 25 labais apakškoks, un tam nav bērnu. Tātad, drukāt 28 .
- Tagad drukāt 25 , un postorder traversal for 25 ir pabeigts.
- Pēc tam pārejiet uz labo apakškoku 30. 35 ir labais apakškoks 30, un tam nav bērnu. Tātad, drukāt 35 .
- Pēc tam, drukāt 30 , un postorder traversal for 30 ir pabeigts. Tātad tiek šķērsots dotā binārā koka kreisais apakškoks.
- Tagad virzieties uz labo apakškoku 40, kas ir 50, un tas arī šķērsos pēc kārtas. 45 ir 50 kreisais apakškoks, un tam nav bērnu. Tātad, drukāt 45 un virzieties uz labo apakškoku 50.
- 60 ir 50. labais apakškoks, kas arī tiks šķērsots pasta secībā. 55 ir 60. kreisais apakškoks, kuram nav bērnu. Tātad, drukāt 55 .
- Tagad drukāt 70, kas ir 60 labais apakškoks.
- Tagad drukāt 60, un pasta pasūtījuma šķērsošana par 60 ir pabeigta.
- Tagad drukāt 50, un pasta pasūtījuma šķērsošana par 50 ir pabeigta.
- Beidzot, drukāt 40, kas ir dotā binārā koka saknes mezgls, un pēc pasūtījuma šķērsošana mezglam 40 ir pabeigta.
Galīgais rezultāts, ko mēs iegūsim pēc pasūtījuma apbraukšanas, ir -
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Pa pastu aprites sarežģītība
Postorder šķērsošanas laika sarežģītība ir O(n) , kur “n” ir binārā koka izmērs.
Turpretim pēc pasūtījuma šķērsošanas kosmosa sarežģītība ir O(1) , ja neņemam vērā funkciju izsaukumu steka lielumu. Pretējā gadījumā pēc pasūtījuma caurbraukšanas telpa ir sarežģīta O(h) , kur “h” ir koka augstums.
Pasta pasūtījumu šķērsošanas ieviešana
Tagad apskatīsim postorder traversal ieviešanu dažādās programmēšanas valodās.
Programma: Uzrakstiet programmu postorder traversal ieviešanai C valodā.
#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; } Izvade
darīt java
Programma: Uzrakstiet programmu postorder traversal ieviešanai C++ valodā.
#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></'
></'> Izvade
Pēc iepriekš minētā koda izpildes izvade būs -
Programma: Uzrakstiet programmu, lai Java ieviestu postorder traversal.
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(); } } Izvade
Pēc iepriekš minētā koda izpildes izvade būs -
Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs.