En aquest article, parlarem del recorregut posterior a la comanda a l'estructura de dades.
Les estructures de dades lineals com ara pila, matriu, cua, etc., només tenen una manera de recórrer les dades. Però en una estructura de dades jeràrquica com ara arbre , hi ha diverses maneres de recórrer les dades. Així doncs, aquí parlarem d'una altra manera de recórrer l'estructura de dades de l'arbre, és a dir, recorregut de comandes per correu . El recorregut postordre és una de les tècniques de travessa utilitzades per visitar el node de l'arbre. Segueix el principi LRN (node esquerra-dreta) . La travessa postordre s'utilitza per obtenir l'expressió postfix d'un arbre.
Els passos següents s'utilitzen per realitzar el recorregut posterior a la comanda:
- Travessa el subarbre esquerre cridant la funció de postordre de manera recursiva.
- Travessa el subarbre dret cridant la funció postordre de manera recursiva.
- Accediu a la part de dades del node actual.
La tècnica de recorregut posterior a la comanda segueix la Arrel esquerra dreta política. Aquí, l'arrel esquerra dreta significa que es recorre primer el subarbre esquerre del node arrel, després el subarbre dret i, finalment, es recorre el node arrel. Aquí, el propi nom de Postorder suggereix que el node arrel de l'arbre es creuaria per fi.
Algorisme
Ara, vegem l'algoritme de travessa postordre.
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
Exemple de recorregut de comandes per correu
Ara, anem a veure un exemple de travessa postordre. Serà més fàcil entendre el procés de travessa post-ordre utilitzant un exemple.
Els nodes amb color groc encara no es visiten. Ara, travessarem els nodes de l'arbre anterior mitjançant el recorregut posterior a la comanda.
np.sum
- Aquí, 40 és el node arrel. Primer visitem el subarbre esquerre de 40, és a dir, 30. El node 30 també es travessarà per ordre posterior. 25 és el subarbre esquerre de 30, de manera que també es travessa en ordre posterior. Aleshores 15 és el subarbre esquerre de 25. Però 15 no té cap subarbre, per tant imprimir 15 i avança cap al subarbre dret de 25.
- 28 és el subarbre dret de 25 i no té fills. Tan, imprimir 28 .
- Ara, imprimir 25 , i el recorregut posterior a la comanda per 25 està acabat.
- A continuació, aneu cap al subarbre dret de 30. 35 és el subarbre dret de 30 i no té fills. Tan, imprimir 35 .
- Després d'això, imprimir 30 , i el recorregut posterior a la comanda per 30 està acabat. Per tant, es recorre el subarbre esquerre de l'arbre binari donat.
- Ara, moveu-vos cap al subarbre dret de 40, que és 50, i també es recorrerà per ordre de publicació. 45 és el subarbre esquerre de 50 i no té fills. Tan, imprimir 45 i avança cap al subarbre dret de 50.
- 60 és el subarbre dret de 50, que també es recorrerà per ordre de publicació. 55 és el subarbre esquerre de 60 que no té fills. Tan, imprimir 55 .
- Ara, imprimir 70, que és el subarbre dret de 60.
- Ara, imprimir 60, i s'ha completat el recorregut posterior a la comanda per a 60.
- Ara, imprimir 50, i s'ha completat el recorregut posterior a la comanda per a 50.
- Per fi, imprimir 40, que és el node arrel de l'arbre binari donat i s'ha completat el recorregut posterior a l'ordre per al node 40.
La sortida final que obtindrem després del recorregut posterior a la comanda és:
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Complexitat del recorregut de comandes per correu
La complexitat temporal del recorregut postordre és O(n) , on 'n' és la mida de l'arbre binari.
Mentre que, la complexitat espacial del recorregut postordre és O(1) , si no tenim en compte la mida de la pila per a les trucades de funció. En cas contrari, la complexitat espacial del recorregut posterior a la comanda és O(h) , on 'h' és l'alçada de l'arbre.
Implementació del recorregut de comandes per correu
Ara, vegem la implementació de la travessa postordre en diferents llenguatges de programació.
Programa: Escriu un programa per implementar el recorregut posterior a la comanda en llenguatge 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; } Sortida
Programa: Escriu un programa per implementar el recorregut posterior a la comanda en 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></'
></'> Sortida
Després de l'execució del codi anterior, la sortida serà -
Programa: Escriu un programa per implementar el recorregut posterior a la comanda a 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(); } } Sortida
any inventat per ordinador
Després de l'execució del codi anterior, la sortida serà -
Per tant, això és tot sobre l'article. Espero que l'article us sigui útil i informatiu.