En aquest article, parlarem del recorregut de la comanda prèvia 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.
En el recorregut de preordre, primer es visita el node arrel, després es visita el subarbre esquerre i després es visita el subarbre dret. El procés de recorregut de preordre es pot representar com -
root → left → right
El node arrel sempre es travessa primer en el recorregut de preordre, mentre que és l'últim element del recorregut posterior a l'ordre. El recorregut de preordre s'utilitza per obtenir l'expressió del prefix d'un arbre.
Els passos per dur a terme el recorregut de la comanda prèvia es mostren a continuació:
què és una interfície
- Primer, visiteu el node arrel.
- A continuació, visiteu el subarbre esquerre.
- Finalment, visiteu el subarbre correcte.
La tècnica de recorregut de la comanda prèvia segueix la Arrel Esquerra Dreta política. La preordre del nom en si suggereix que primer es travessa el node arrel.
Algorisme
Ara, anem a veure l'algoritme del recorregut de preordre.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: Write TREE -> DATA Step 3: PREORDER(TREE -> LEFT) Step 4: PREORDER(TREE -> RIGHT) [END OF LOOP] Step 5: END
Exemple de recorregut de pre-ordre
Ara, anem a veure un exemple de recorregut de preordre. Serà més fàcil entendre el procés de travessa de la comanda prèvia utilitzant un exemple.
Els nodes amb color groc encara no es visiten. Ara, travessarem els nodes de l'arbre anterior mitjançant el recorregut de preordre.
- Comenceu amb el node arrel 40. Primer, imprimir 40 i després recorreu recursivament el subarbre esquerre.
- Ara, moveu-vos al subarbre esquerre. Per al subarbre esquerre, el node arrel és 30. Imprimeix 30 , i avança cap al subarbre esquerre de 30.
- Al subarbre esquerre de 30, hi ha un element 25, per tant imprimir 25 , i travessa el subarbre esquerre de 25.
- Al subarbre esquerre de 25, hi ha un element 15 i 15 no té cap subarbre. Tan, imprimir 15 , i moveu-vos al subarbre dret de 25.
- Al subarbre dret de 25, hi ha 28 i 28 no té cap subarbre. Tan, imprimir 28 , i moveu-vos al subarbre dret de 30.
- Al subarbre dret de 30, hi ha 35 que no té cap subarbre. Tan imprimir 35 , i travessa el subarbre dret de 40.
- Al subarbre dret de 40, n'hi ha 50. Imprimeix 50 , i travessa el subarbre esquerre de 50.
- Al subarbre esquerre de 50, hi ha 45 que no tenen cap fill. Tan, imprimir 45 , i travessa el subarbre dret de 50.
- Al subarbre dret de 50, hi ha 60. Imprimeix 60 i travessa el subarbre esquerre de 60.
- Al subarbre esquerre de 60, hi ha 55 que no té cap fill. Tan, imprimir 55 i moveu-vos al subarbre dret de 60.
- Al subarbre dret de 60, n'hi ha 70 que no tenen cap fill. Tan, imprimir 70 i aturar el procés.
Després de completar el recorregut de la comanda prèvia, la sortida final és -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
imatge com a fons en css
Complexitat del recorregut de la comanda prèvia
La complexitat temporal del recorregut de la comanda prèvia és O(n) , on 'n' és la mida de l'arbre binari.
Mentre que, la complexitat espacial del recorregut de la comanda prèvia é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 de la comanda prèvia és O(h) , on 'h' és l'alçada de l'arbre.
Implementació del recorregut de la comanda prèvia
Ara, vegem la implementació del recorregut de preordre en diferents llenguatges de programació.
Programa: Escriu un programa per implementar el recorregut de preordres en llenguatge C.
registre numpy
#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); } 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 Preorder traversal of given binary tree is -
'); traversePreorder(root); return 0; } Sortida
Després de l'execució del codi anterior, la sortida serà -
Programa: Escriu un programa per implementar el recorregut de preordre 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); } int main() { struct node* root = createNode(39); root->left = createNode(29); root->right = createNode(49); root->left->left = createNode(24); root->left->right = createNode(34); root->left->left->left = createNode(14); root->left->left->right = createNode(27); root->right->left = createNode(44); root->right->right = createNode(59); root->right->right->left = createNode(54); root->right->right->right = createNode(69); cout<<'
the preorder traversal of given binary tree is -
'; traversepreorder(root); return 0; } < 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/25/preorder-traversal-14.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder 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 traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(38); bt.root.left = new Node(28); bt.root.right = new Node(48); bt.root.left.left = new Node(23); bt.root.left.right = new Node(33); bt.root.left.left.left = new Node(13); bt.root.left.left.right = new Node(26); bt.root.right.left = new Node(43); bt.root.right.right = new Node(58); bt.root.right.right.left = new Node(53); bt.root.right.right.right = new Node(68); Console.WriteLine('Preorder traversal of given binary tree is - '); bt.traversePreorder(); } } </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/25/preorder-traversal-15.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); 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/25/preorder-traversal-16.webp" alt="Preorder 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 de preordre a Java.
recursivitat java
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } Sortida
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.