Tässä artikkelissa käsittelemme postorder-läpikulkua tietorakenteessa.
Lineaarisilla tietorakenteilla, kuten pino, taulukko, jono jne., on vain yksi tapa kulkea datan läpi. Mutta hierarkkisessa tietorakenteessa, kuten esim puu , on olemassa useita tapoja kulkea dataa läpi. Joten tässä käsittelemme toista tapaa kulkea puun tietorakenteen läpi, ts. postimyynnin läpikulku . Postorder-läpikulku on yksi läpikulkutekniikoista, joita käytetään puun solmussa vierailemiseen. Se noudattaa periaatetta LRN (vasen-oikea-solmu) . Postorder-läpikulkua käytetään puun postfix-lausekkeen saamiseksi.
Seuraavia vaiheita käytetään jälkitilauksen läpikäymiseen:
- Läpi vasen alipuu kutsumalla postorder-funktiota rekursiivisesti.
- Kulje oikea alipuu kutsumalla postorder-funktiota rekursiivisesti.
- Käytä nykyisen solmun dataosaa.
Postitilauksen läpikulkutekniikka noudattaa Vasen Oikea juuri käytäntö. Tässä Left Right Root tarkoittaa, että juurisolmun vasen alipuu kuljetetaan ensin, sitten oikea alipuu ja lopuksi juurisolmun läpi. Tässä itse Postorder-nimi viittaa siihen, että puun juurisolmu kuljetettaisiin vihdoinkin läpi.
Algoritmi
Katsotaanpa nyt postorder-läpikulun algoritmia.
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
Esimerkki postimyynnin läpikulusta
Katsotaanpa nyt esimerkkiä postorder traversalista. On helpompi ymmärtää postorder-läpikulkuprosessi esimerkin avulla.
Keltaisilla solmuilla ei ole vielä käyty. Nyt kuljemme yllä olevan puun solmut käyttämällä postorder-läpikulkua.
array.sort javassa
- Tässä 40 on juurisolmu. Käymme ensin vasemmassa alipuussa 40, eli 30. Solmu 30 kulkee myös jälkijärjestyksessä. 25 on luvun 30 vasen alipuu, joten se ajetaan myös jälkijärjestyksessä. Silloin 15 on luvun 25 vasen alipuu. Mutta 15:llä ei ole alipuuta, joten tulostaa 15 ja siirry kohti oikeaa alipuuta 25.
- 28 on 25:n oikea alipuu, eikä sillä ole lapsia. Niin, tulostaa 28 .
- Nyt, tulostaa 25 , ja postorder traversal for 25 on valmis.
- Seuraavaksi siirry kohti oikeaa alipuuta 30. 35 on oikea alipuu 30, ja sillä ei ole lapsia. Niin, tulostaa 35 .
- Sen jälkeen, tulostaa 30 , ja postorder traversal for 30 on valmis. Joten, annetun binääripuun vasen alipuu ajetaan.
- Siirry nyt kohti oikeaa alipuuta 40, joka on 50, ja se kulkee myös jälkijärjestyksessä. 45 on luvun 50 vasen alipuu, eikä sillä ole lapsia. Niin, tulostaa 45 ja siirry kohti oikeaa alipuuta 50.
- 60 on 50:n oikea alipuu, joka myös käydään läpi postitse. 55 on 60:n vasen alipuu, jolla ei ole lapsia. Niin, tulostaa 55 .
- Nyt, tulostaa 70, joka on 60:n oikea alipuu.
- Nyt, tulostaa 60, ja postitilauksen läpikulku 60:lle on valmis.
- Nyt, tulostaa 50, ja postitilauksen läpikulku 50:lle on valmis.
- Viimeinkin, tulostaa 40, joka on annetun binääripuun juurisolmu, ja solmun 40 tilauksen jälkeinen läpikulku on suoritettu.
Lopullinen tulos, jonka saamme postorder-läpikäynnin jälkeen, on -
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Postimyynnin läpikulun monimutkaisuus
Postorder traversin aika monimutkaisuus on Päällä) , jossa 'n' on binääripuun koko.
Sitä vastoin postorder-läpiviennin monimutkaisuus on O(1) , jos emme ota huomioon funktiokutsujen pinon kokoa. Muuten postorder-läpiviennin monimutkaisuus on Vai niin) , jossa 'h' on puun korkeus.
Postimyynnin läpikulun toteutus
Katsotaanpa nyt postorder traversalin toteutusta eri ohjelmointikielillä.
Ohjelmoida: Kirjoita ohjelma postorder traversalin toteuttamiseksi C-kielellä.
#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; } Lähtö
Ohjelmoida: Kirjoita ohjelma postorder traversalin toteuttamiseksi C++:ssa.
#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></'
></'> Lähtö
Yllä olevan koodin suorittamisen jälkeen tulos on -
Ohjelmoida: Kirjoita ohjelma postorder traversalin toteuttamiseksi Javassa.
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(); } } Lähtö
linux tiedostot
Yllä olevan koodin suorittamisen jälkeen tulos on -
Eli siinä kaikki artikkelista. Toivottavasti artikkeli on hyödyllinen ja informatiivinen sinulle.