En aquest article, parlarem del recorregut de l'arbre a l'estructura de dades. El terme 'travessa d'arbres' significa recórrer o visitar cada node d'un arbre. Hi ha una única manera de recórrer l'estructura de dades lineal, com ara la llista enllaçada, la cua i la pila. Mentre que, hi ha diverses maneres de recórrer un arbre que s'enumeren de la següent manera:
- Travessa de comanda prèvia
- Travessa en ordre
- Travessa postal
Per tant, en aquest article, parlarem de les tècniques esmentades anteriorment per travessar un arbre. Ara, comencem a discutir les maneres de travessar els arbres.
Travessa de comanda prèvia
Aquesta tècnica segueix la política 'arrel esquerra dreta'. Vol dir que es visita el primer node arrel després que el subarbre esquerre es travessa recursivament i, finalment, es recorre recursivament el subarbre dret. Com que el node arrel es recorre abans (o abans) del subarbre esquerre i dret, s'anomena travessa de preordre.
Així, en un recorregut de preordre, cada node es visita abans dels dos subarbres.
Les aplicacions del recorregut de comanda prèvia inclouen:
- S'utilitza per crear una còpia de l'arbre.
- També es pot utilitzar per obtenir l'expressió prefixada d'un arbre d'expressions.
Algorisme
Until all nodes of the tree are not visited Step 1 - Visit the root node Step 2 - Traverse the left subtree recursively. Step 3 - Traverse the right subtree recursively.
Exemple
Ara, vegem l'exemple de la tècnica de travessa de preordre.
Ara, comenceu a aplicar el recorregut de la comanda prèvia a l'arbre anterior. Primer, travessem el node arrel A; després d'això, moveu-vos al seu subarbre esquerre B , que també es recorrerà en preordre.
Per tant, per al subarbre esquerre B, primer, el node arrel B es recorre per si mateix; després d'això, el seu subarbre esquerre D es travessa. Des del node D no té fills, moveu-vos al subarbre dret I . Com que el node E tampoc té cap fill, s'ha completat el recorregut del subarbre esquerre del node arrel A.
15 de 100.00
Ara, moveu-vos cap al subarbre dret del node arrel A que és C. Per tant, per al subarbre dret C, primer el node arrel C s'ha travessat per si mateix; després d'això, el seu subarbre esquerre F es travessa. Des del node F no té fills, moveu-vos al subarbre dret G . Com que el node G tampoc té cap fill, s'ha completat el recorregut del subarbre dret del node arrel A.
agrupació
Per tant, es recorren tots els nodes de l'arbre. Per tant, la sortida del recorregut de la comanda prèvia de l'arbre anterior és -
A → B → D → E → C → F → G
Per saber més sobre el recorregut de la comanda prèvia a l'estructura de dades, podeu seguir l'enllaç Travessa de comanda prèvia .
Travessa postal
Aquesta tècnica segueix la política d''arrel esquerra-dreta'. Vol dir que es recorre el primer subarbre esquerre del node arrel, després travessa recursivament el subarbre dret i, finalment, es recorre el node arrel. Quan el node arrel es travessa després (o publica) el subarbre esquerre i dret, s'anomena travessa postordre.
Així, en un recorregut posterior a la comanda, cada node es visita després dels dos subarbres.
Les aplicacions de la travessa posterior a la comanda inclouen:
- S'utilitza per eliminar l'arbre.
- També es pot utilitzar per obtenir l'expressió postfix d'un arbre d'expressions.
Algorisme
Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Traverse the right subtree recursively. Step 3 - Visit the root node.
Exemple
Ara, vegem l'exemple de la tècnica de travessa postordre.
Ara, comenceu a aplicar el recorregut posterior a l'ordre a l'arbre anterior. Primer, recorrem el subarbre esquerre B que es recorrerà en postordre. Després d'això, travessarem el subarbre dret C en postordre. I, finalment, el node arrel de l'arbre anterior, és a dir, A , es recorre.
Per tant, per al subarbre esquerre B, primer, el seu subarbre esquerre D es travessa. Des del node D no té fills, travessa el subarbre dret I . Com que el node E tampoc té cap fill, aneu al node arrel B. Després de travessar el node B, es completa el recorregut del subarbre esquerre del node arrel A.
Ara, moveu-vos cap al subarbre dret del node arrel A que és C. Per tant, per al subarbre dret C, primer el seu subarbre esquerre F es travessa. Des del node F no té fills, travessa el subarbre dret G . Com que el node G tampoc té fills, per tant, finalment, el node arrel del subarbre dret, és a dir, C, es travessa. S'ha completat el recorregut del subarbre dret del node arrel A.
Finalment, travessa el node arrel d'un arbre donat, és a dir, A . Després de travessar el node arrel, es completa el recorregut posterior a l'ordre de l'arbre donat.
Per tant, es recorren tots els nodes de l'arbre. Per tant, la sortida del recorregut posterior a l'ordre de l'arbre anterior és -
D → E → B → F → G → C → A
clau d'inserció del portàtil
Per saber més sobre el recorregut postordre a l'estructura de dades, podeu seguir l'enllaç Travessa postal .
Travessa en ordre
Aquesta tècnica segueix la política 'arrel esquerra dreta'. Significa que es visita el primer subarbre esquerre després de travessar aquest node arrel i, finalment, es recorre el subarbre dret. A mesura que el node arrel es recorre entre el subarbre esquerre i dret, s'anomena inorder traversal.
Així, en el recorregut en ordre, cada node es visita entre els seus subarbres.
Les aplicacions de l'Inorder traversal inclouen:
- S'utilitza per obtenir els nodes BST en ordre creixent.
- També es pot utilitzar per obtenir l'expressió prefixada d'un arbre d'expressions.
Algorisme
Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Visit the root node. Step 3 - Traverse the right subtree recursively.
Exemple
Ara, vegem l'exemple de la tècnica de travessa Inorder.
Ara, comenceu a aplicar el recorregut en ordre a l'arbre anterior. Primer, travessem el subarbre esquerre B que es recorrerà en ordre. Després d'això, travessarem el node arrel A . I finalment, el subarbre correcte C es recorre en ordre interior.
Per tant, per al subarbre esquerre B , primer, el seu subarbre esquerre D es travessa. Des del node D no té fills, així que després de travessar-lo, node B es recorrerà, i finalment, el subarbre dret del node B, és a dir I , es recorre. El node E tampoc té cap fill; per tant, es completa el recorregut del subarbre esquerre del node arrel A.
multithreading java
Després d'això, travessa el node arrel d'un arbre determinat, és a dir, A .
Finalment, moveu-vos cap al subarbre dret del node arrel A que és C. Per tant, per al subarbre dret C; primer, el seu subarbre esquerre F es travessa. Des del node F no té fills, node C es recorrerà, i finalment, un subarbre dret del node C, és a dir, G , es recorre. El node G tampoc té fills; per tant, es completa el recorregut del subarbre dret del node arrel A.
A mesura que es recorren tots els nodes de l'arbre, es completa el recorregut en ordre de l'arbre donat. La sortida del recorregut en ordre de l'arbre anterior és -
D → B → E → A → F → C → G
Per saber més sobre el recorregut en ordre en l'estructura de dades, podeu seguir l'enllaç Travessia de l'ordre .
Complexitat de les tècniques de travessa d'arbres
La complexitat temporal de les tècniques de travessa d'arbres discutides anteriorment és O(n) , on 'n' és la mida de l'arbre binari.
Mentre que la complexitat espacial de les tècniques de travessa d'arbres discutides anteriorment é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 d'aquestes tècniques és O(h) , on 'h' és l'alçada de l'arbre.
Implementació de Tree traversal
Ara, anem a veure la implementació de les tècniques comentades anteriorment utilitzant diferents llenguatges de programació.
Programa: Escriu un programa per implementar tècniques de travessa d'arbres en C.
q3 mesos
#include #include 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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(root->right); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(root->right); } /*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(36); root->left = createNode(26); root->right = createNode(46); root->left->left = createNode(21); root->left->right = createNode(31); root->left->left->left = createNode(11); root->left->left->right = createNode(24); root->right->left = createNode(41); root->right->right = createNode(56); root->right->right->left = createNode(51); root->right->right->right = createNode(66); printf('
The Preorder traversal of given binary tree is -
'); traversePreorder(root); printf('
The Inorder traversal of given binary tree is -
'); traverseInorder(root); printf('
The Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } Sortida
Programa: Escriu un programa per implementar tècniques de recorregut d'arbres en C#.
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 traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } 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 Preorder traversal of given binary tree is - '); bt.traversePreorder(); Console.WriteLine(); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); Console.WriteLine(); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } Sortida
Programa: Escriu un programa per implementar tècniques de travessa d'arbres 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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->right); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); cout<<' '<element<right); } *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 preorder traversal of given binary tree is -
'; traversepreorder(root); cout<<'
inorder traverseinorder(root); postorder traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/17/tree-traversal-inorder-6.webp" alt="Tree Traversal"> <p> <strong>Program:</strong> Write a program to implement tree traversal techniques in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class Tree { Node root; /* root of the tree */ Tree() { root = null; } /*function to print the nodes of given binary in Preorder*/ void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } /*function to print the nodes of given binary in Inorder*/ void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } /*function to print the nodes of given binary in Postorder*/ void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { Tree pt = new Tree(); 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 Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println('
'); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); 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/17/tree-traversal-inorder-7.webp" alt="Tree Traversal"> <h2>Conclusion</h2> <p>In this article, we have discussed the different types of tree traversal techniques: preorder traversal, inorder traversal, and postorder traversal. We have seen these techniques along with algorithm, example, complexity, and implementation in C, C++, C#, and java.</p> <p>So, that's all about the article. Hope it will be helpful and informative to you.</p> <hr></'
></'></'></'> Sortida
Després de l'execució del codi anterior, la sortida serà -
Conclusió
En aquest article, hem parlat dels diferents tipus de tècniques de travessa d'arbres: travessa prèvia, travessa en ordre i travessa postorde. Hem vist aquestes tècniques juntament amb algorisme, exemple, complexitat i implementació en C, C++, C# i Java.
Per tant, això és tot sobre l'article. Espero que us sigui útil i informatiu.