Ebben a cikkben a postorder bejárást tárgyaljuk az adatstruktúrában.
A lineáris adatstruktúráknak, például a veremnek, a tömbnek, a sornak stb., csak egy módja van az adatok bejárására. De egy hierarchikus adatszerkezetben, mint pl fa , többféle módon lehet bejárni az adatokat. Tehát itt egy másik módot fogunk tárgyalni a fa adatszerkezeten való bejárására, pl. csomagküldő bejárás . A postorder bejárás a fa csomópontjának meglátogatására használt bejárási technikák egyike. Az elvet követi LRN (bal-jobb-csomópont) . A postorder bejárás egy fa postfix kifejezésének lekérésére szolgál.
Az utólagos bejárás a következő lépésekkel hajtható végre:
- Haladjon be a bal oldali részfán a postorder függvény rekurzív meghívásával.
- Haladjon be a jobb oldali részfán a postorder függvény rekurzív meghívásával.
- Az aktuális csomópont adatrészének elérése.
Az utólagos bejárási technika követi a Bal jobb gyökér irányelv. Itt a Left Right Root azt jelenti, hogy először a gyökércsomópont bal oldali részfáját kell bejárni, majd a jobb oldali részfát, végül pedig a gyökércsomópontot. Itt maga a Postorder név azt sugallja, hogy a fa gyökércsomópontját végre bejárjuk.
Algoritmus
Most pedig lássuk az utólagos bejárás algoritmusát.
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élda a csomagküldő rendelés bejárására
Most pedig lássunk egy példát az utólagos bejárásra. Egy példa segítségével könnyebb lesz megérteni az utólagos bejárás folyamatát.
A sárga színű csomópontok még nincsenek felkeresve. Most a fenti fa csomópontjain fogunk bejárni a postorder bejárás segítségével.
- Itt a 40 a gyökércsomópont. Először a 40-es, azaz a 30-as bal oldali részfát keressük fel. A 30-as csomópont is utólagos sorrendben fog bejárni. A 25 a 30 bal oldali részfája, tehát utólagos sorrendben is bejárjuk. Ekkor a 15 a 25 bal oldali részfája. De a 15-nek nincs részfája, így nyomtatás 15 és lépjen a 25-ös jobb oldali részfa felé.
- A 28 a 25 jobb oldali részfája, és nincs gyermeke. Így, nyomtatás 28 .
- Most, nyomtatás 25 , és a postorder traversal for 25 befejeződött.
- Ezután lépjen a 30-as jobb oldali részfa felé. A 35 a 30-as jobb oldali részfa, és nincs gyermeke. Így, nyomtatás 35 .
- Azt követően, nyomtatás 30 , és a postorder traversal for 30 befejeződött. Tehát az adott bináris fa bal oldali részfáját bejárjuk.
- Most menjen a 40-es jobb oldali részfa felé, amely 50, és az is utólagos sorrendben fog haladni. A 45 az 50 bal oldali részfája, és nincs gyermeke. Így, nyomtatás 45 és lépjen az 50-es jobb oldali részfa felé.
- A 60 az 50-es jobb oldali részfa, amelyen szintén utólagos sorrendben járunk be. Az 55 a 60 bal oldali részfája, amelynek nincs gyermeke. Így, nyomtatás 55 .
- Most, nyomtatott 70, ami a 60 jobb oldali részfája.
- Most, nyomtatás 60, és a 60-ra szóló postarendelés bejárása befejeződött.
- Most, nyomtatás 50, és az 50-es postai rendelés bejárása befejeződött.
- Végül, nyomtatott 40, amely az adott bináris fa gyökércsomópontja, és a 40-es csomópont utórendelési bejárása befejeződött.
A végső kimenet, amit az utólagos bejárás után kapunk:
vlc youtube videók letöltéséhez
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
A csomagküldő áru bejárásának összetettsége
Az utólagos bejárás időbonyolultsága az Tovább) , ahol az 'n' a bináris fa mérete.
Ezzel szemben az utólagos bejárás térbonyolultsága az O(1) , ha nem vesszük figyelembe a függvényhívások veremméretét. Ellenkező esetben a postorder bejárás térbonyolultsága az O(h) , ahol a „h” a fa magassága.
Postai rendelés bejárás megvalósítása
Most pedig lássuk a postorder bejárás megvalósítását különböző programozási nyelveken.
Program: Írjon programot a postorder bejárás megvalósítására C nyelven.
#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; } Kimenet
Program: Írjon programot a postorder bejárás megvalósítására C++ nyelven.
#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></'
></'> Kimenet
A fenti kód végrehajtása után a kimenet a következő lesz:
Program: Írjon programot a postorder bejárás megvalósítására Java nyelven.
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(); } } Kimenet
A fenti kód végrehajtása után a kimenet a következő lesz:
Szóval ennyi a cikkről. Reméljük, hogy a cikk hasznos és informatív lesz az Ön számára.