Šiame straipsnyje aptarsime postorder perėjimą duomenų struktūroje.
Linijinės duomenų struktūros, tokios kaip dėklas, masyvas, eilė ir t. t., turi tik vieną būdą perduoti duomenis. Tačiau hierarchinėje duomenų struktūroje, pvz medis , yra keli būdai, kaip peržiūrėti duomenis. Taigi, čia aptarsime kitą būdą, kaip pereiti medžio duomenų struktūrą, t.y. užsakymo paštu pervežimas . Postorder traversal yra vienas iš perėjimo būdų, naudojamų aplankant medžio mazgą. Tai vadovaujasi principu LRN (kairė-dešinė-mazgas) . Postorder traversal naudojamas medžio postfix išraiškai gauti.
Norėdami atlikti postorder perėjimą, naudojami šie veiksmai:
- Pereikite kairįjį pomedį, rekursyviai iškviesdami postorder funkciją.
- Pereikite dešinįjį pomedį, rekursyviai iškviesdami postorder funkciją.
- Pasiekite dabartinio mazgo duomenų dalį.
Pašto užsakymo perėjimo technika yra tokia Kairė dešinė šaknis politika. Čia kairioji dešinioji šaknis reiškia, kad pirmiausia pereinama kairysis šakninio mazgo pomedis, tada dešinysis pomedis ir galiausiai perkeliamas šakninis mazgas. Čia pats Postorder pavadinimas rodo, kad medžio šaknies mazgas pagaliau bus perkeltas.
kaip java perduoti eilutę į int
Algoritmas
Dabar pažiūrėkime į postorder traversal algoritmą.
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
Užsakymo paštu pervežimo pavyzdys
Dabar pažiūrėkime į postorder perėjimo pavyzdį. Naudojant pavyzdį, bus lengviau suprasti postorder perėjimo procesą.
Geltonos spalvos mazgai dar nelankyti. Dabar pereisime aukščiau esančio medžio mazgus naudodami postorder traversal.
- Čia 40 yra šakninis mazgas. Pirmiausia aplankome kairįjį pomedį 40, t.y. 30. 30 mazgas taip pat eis posto tvarka. 25 yra kairysis 30 pomedis, todėl jis taip pat kertamas posto tvarka. Tada 15 yra kairysis 25 pomedis. Bet 15 neturi pomedžio, todėl spausdinti 15 ir pereikite link dešiniojo 25 pomedžio.
- 28 yra dešinysis 25 pomedis ir jis neturi vaikų. Taigi, spausdinti 28 .
- Dabar spausdinti 25 , ir postorder traversal for 25 yra baigta.
- Tada pereikite prie dešiniojo 30 pomedžio. 35 yra dešinysis 30 pomedis ir jis neturi vaikų. Taigi, spausdinti 35 .
- Po to spausdinti 30 , ir postorder traversal for 30 yra baigta. Taigi, kertamas duoto dvejetainio medžio kairysis pomedis.
- Dabar eikite link dešiniojo 40 pomedžio, kuris yra 50, ir jis taip pat eis posto tvarka. 45 yra kairysis 50 pomedis ir jis neturi vaikų. Taigi, Spausdinti 45 ir pereikite link dešiniojo 50 pomedžio.
- 60 yra dešinysis 50 pomedis, kuris taip pat bus perkeltas pašto tvarka. 55 yra kairysis 60 pomedis, neturintis vaikų. Taigi, spausdinti 55 .
- Dabar spausdinti 70, kuris yra dešinysis 60 pomedis.
- Dabar spausdinti 60, ir pašto užsakymo perkėlimas už 60 baigtas.
- Dabar spausdinti 50, ir pašto užsakymo perkėlimas už 50 baigtas.
- Pagaliau, spausdinti 40, kuris yra duoto dvejetainio medžio šakninis mazgas, ir baigiamas 40 mazgo post orderis.
Galutinė produkcija, kurią gausime atlikę postorder perėjimą, yra
rūšiavimas kortelių python
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Prekybos paštu sudėtingumas
Postorder traverzavimo laiko sudėtingumas yra O(n) , kur „n“ yra dvejetainio medžio dydis.
Tuo tarpu postorder traverzavimo erdvė yra sudėtinga O(1) , jei neatsižvelgsime į funkcijų iškvietimų krūvos dydį. Priešingu atveju postorder traverzavimo erdvė yra sudėtinga Oi) , kur „h“ yra medžio aukštis.
Užsakymo paštu pervežimo įgyvendinimas
Dabar pažiūrėkime, kaip įgyvendinamas postorder traversal įvairiose programavimo kalbose.
Programa: Parašykite programą, kuri įgyvendintų postorder traversal C kalba.
kaip konvertuoti int į eilutę
#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; } Išvestis
Programa: Parašykite programą, kuri įgyvendintų postorder traversal 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></'
></'> Išvestis
regexp_like mysql
Įvykdžius aukščiau pateiktą kodą, išvestis bus -
Programa: Parašykite programą, skirtą įdiegti postorder traversal Java.
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(); } } Išvestis
Įvykdžius aukščiau pateiktą kodą, išvestis bus -
Taigi, viskas apie straipsnį. Tikimės, kad straipsnis bus jums naudingas ir informatyvus.