V tem članku bomo razpravljali o prehodu po naročilu v strukturi podatkov.
Linearne podatkovne strukture, kot so sklad, niz, čakalna vrsta itd., imajo samo en način za prečkanje podatkov. Toda v hierarhični strukturi podatkov, kot je npr drevo , obstaja več načinov za pregledovanje podatkov. Torej, tukaj bomo razpravljali o drugem načinu prečkanja strukture drevesnih podatkov, tj. naročanje po pošti . Prehod po naročilu je ena od tehnik prečkanja, ki se uporablja za obisk vozlišča v drevesu. Sledi načelu LRN (levo-desno-vozlišče) . Prehod po vrstnem redu se uporablja za pridobitev postfiksnega izraza drevesa.
Za izvedbo prehoda po naročilu se uporabljajo naslednji koraki:
- Prečkajte levo poddrevo z rekurzivnim klicem funkcije postorder.
- Prečkajte desno poddrevo z rekurzivnim klicem funkcije postorder.
- Dostop do podatkovnega dela trenutnega vozlišča.
Tehnika prehoda po naročilu sledi Levi desni koren politika. Levi desni koren tukaj pomeni, da se najprej prečka levo poddrevo korenskega vozlišča, nato desno poddrevo in na koncu se prečka korensko vozlišče. Tukaj samo ime Postorder nakazuje, da bo korensko vozlišče drevesa končno prečkano.
Algoritem
Zdaj pa si oglejmo algoritem prehoda po naročilu.
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
Primer prečkanja naročila po pošti
Zdaj pa si oglejmo primer prehoda po naročilu. Na primeru bomo lažje razumeli proces prehoda po naročilu.
Vozlišča z rumeno barvo še niso obiskana. Zdaj bomo prečkali vozlišča zgornjega drevesa s prehodom po naročilu.
int v niz c++
- Tu je 40 korensko vozlišče. Najprej obiščemo levo poddrevo 40, tj. 30. Vozlišče 30 bo prav tako prečkalo po vrstnem redu. 25 je levo poddrevo od 30, zato je tudi prečkano po vrstnem redu. Potem je 15 levo poddrevo od 25. Toda 15 nima poddrevesa, torej natisni 15 in se premaknite proti desnemu poddrevesu 25.
- 28 je desno poddrevo 25 in nima otrok. Torej, natisni 28 .
- zdaj, natisni 25 in prehod po naročilu za 25 je končano.
- Nato se pomaknite proti desnemu poddrevesu 30. 35 je desno poddrevo 30 in nima otrok. Torej, natisni 35 .
- Potem, natisni 30 in prehod po naročilu za 30 je končano. Torej se prečka levo poddrevo danega binarnega drevesa.
- Zdaj se premaknite proti desnemu poddrevesu 40, to je 50, in bo tudi prečkalo po vrstnem redu. 45 je levo poddrevo 50 in nima otrok. Torej, natisni 45 in se premaknite proti desnemu poddrevesu 50.
- 60 je desno poddrevo 50, ki bo prav tako prečkano po vrstnem redu. 55 je levo poddrevo 60, ki nima otrok. Torej, natisni 55 .
- zdaj, natisni 70, ki je desno poddrevo 60.
- zdaj, natisni 60, in prečkanje poštnega naročila za 60 je zaključeno.
- zdaj, natisni 50, in prečkanje poštnega naročila za 50 je končano.
- Končno, natisni 40, ki je korensko vozlišče danega binarnega drevesa, in prehod po naročilu za vozlišče 40 je končan.
Končni rezultat, ki ga bomo dobili po prehodu po naročilu, je -
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Zapletenost naročanja po pošti
Časovna zapletenost prehoda po naročilu je O(n) , kjer je 'n' velikost binarnega drevesa.
Medtem ko je prostorska kompleksnost prečkanja po naročilu O(1) , če ne upoštevamo velikosti sklada za klice funkcij. V nasprotnem primeru je prostorska zapletenost prehoda po naročilu O(h) , kjer je 'h' višina drevesa.
Implementacija prečkanja naročil po pošti
Zdaj pa si oglejmo izvedbo prehoda po naročilu v različnih programskih jezikih.
Program: Napišite program za izvajanje prehoda po naročilu v jeziku 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; } Izhod
Program: Napišite program za izvajanje prehoda po naročilu v 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></'
></'> Izhod
Po izvedbi zgornje kode bo rezultat -
Program: Napišite program za izvajanje prehoda po naročilu v Javi.
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(); } } Izhod
kako izvesti skript
Po izvedbi zgornje kode bo rezultat -
Torej, to je vse o članku. Upam, da vam bo članek koristen in informativen.