В тази статия ще обсъдим прехода след поръчка в структурата на данните.
Линейните структури от данни като стек, масив, опашка и т.н. имат само един начин за преминаване през данните. Но в йерархична структура от данни като напр дърво , има множество начини за преминаване на данните. И така, тук ще обсъдим друг начин за преминаване през дървовидната структура на данните, т.е. преминаване по пощата . Преминаването след поръчка е една от техниките за преминаване, използвани за посещение на възела в дървото. Следва принципа LRN (ляв-десен възел) . Обхождането след поръчка се използва за получаване на постфиксния израз на дърво.
Следните стъпки се използват за извършване на обхождане след поръчка:
- Преминете през лявото поддърво чрез рекурсивно извикване на функцията postorder.
- Преминете през дясното поддърво чрез рекурсивно извикване на функцията postorder.
- Достъп до частта с данни на текущия възел.
Техниката за преминаване на поръчката следва Ляв десен корен политика. Тук ляв десен корен означава, че първо се преминава през лявото поддърво на коренния възел, след това през дясното поддърво и накрая се преминава през основния възел. Тук самото име Postorder подсказва, че основният възел на дървото най-накрая ще бъде пресечен.
Алгоритъм
Сега, нека видим алгоритъма за преминаване след поръчка.
опитайте catch catch java
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
Пример за преминаване на поръчки по пощата
Сега, нека видим пример за преминаване след поръчка. Ще бъде по-лесно да разберете процеса на преминаване след поръчка, като използвате пример.
Възлите с жълт цвят все още не са посетени. Сега ще прекосим възлите на горното дърво с помощта на обхождане след поръчка.
- Тук 40 е основният възел. Първо посещаваме лявото поддърво на 40, т.е. 30. Възел 30 също ще премине в последващ ред. 25 е лявото поддърво на 30, така че то също се преминава в последващ ред. Тогава 15 е лявото поддърво на 25. Но 15 няма поддърво, така че печат 15 и се придвижете към дясното поддърво на 25.
- 28 е дясното поддърво на 25 и то няма деца. Така, печат 28 .
- Сега, печат 25 , и прехода след поръчка за 25 е завършено.
- След това се придвижете към дясното поддърво на 30. 35 е дясното поддърво на 30 и то няма деца. Така, печат 35 .
- След това, печат 30 , и прехода след поръчка за 30 е завършено. И така, лявото поддърво на дадено двоично дърво се пресича.
- Сега се придвижете към дясното поддърво на 40, което е 50, и то също ще премине в последващ ред. 45 е лявото поддърво на 50 и то няма деца. Така, печат 45 и се преместете към дясното поддърво на 50.
- 60 е дясното поддърво на 50, което също ще бъде обходено в последващ ред. 55 е лявото поддърво на 60, което няма деца. Така, печат 55 .
- Сега, печат 70, което е дясното поддърво на 60.
- Сега, печат 60, и преминаването на пост поръчка за 60 е завършено.
- Сега, печат 50, и преминаването на пост поръчка за 50 е завършено.
- Най-накрая, печат 40, който е основният възел на даденото двоично дърво и обхождането на пост поръчката за възел 40 е завършено.
Крайният изход, който ще получим след обхождане след поръчка е -
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
хеширане в структурата на данните
Сложност на преминаването на поръчката по пощата
Времевата сложност на преминаването след поръчка е На) , където 'n' е размерът на двоичното дърво.
Като има предвид, че пространствената сложност на преминаването след поръчка е О(1) , ако не вземем предвид размера на стека за извиквания на функции. В противен случай пространствената сложност на прехода след поръчка е O(h) , където 'h' е височината на дървото.
Внедряване на обхождане на поръчки по пощата
Сега, нека видим изпълнението на postorder traversal в различни езици за програмиране.
програма: Напишете програма за реализиране на следпоръчково обхождане на език 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; } Изход
програма: Напишете програма за внедряване на обхождане след поръчка в 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></'
></'> Изход
След изпълнението на горния код, изходът ще бъде -
програма: Напишете програма за реализиране на обхождане след поръчка в 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(); } } Изход
След изпълнението на горния код, изходът ще бъде -
Актрисата Рубина Дилайк
И така, това е всичко за статията. Надяваме се, че статията ще ви бъде полезна и информативна.