En este artículo, analizaremos el recorrido de preorden en la estructura de datos. Las estructuras de datos lineales, como pila, matriz, cola, etc., solo tienen una forma de atravesar los datos. Pero en una estructura de datos jerárquica como árbol , hay varias formas de recorrer los datos.
En el recorrido de preorden, primero se visita el nodo raíz, luego el subárbol izquierdo y luego el subárbol derecho. El proceso de recorrido de preorden se puede representar como:
root → left → right
El nodo raíz siempre se atraviesa primero en el recorrido de preorden, mientras que es el último elemento del recorrido de postorden. El recorrido de preorden se utiliza para obtener la expresión de prefijo de un árbol.
Los pasos para realizar el recorrido del pedido anticipado se enumeran a continuación:
seleccionar como
- Primero, visite el nodo raíz.
- Luego, visite el subárbol izquierdo.
- Por último, visite el subárbol derecho.
La técnica transversal de preorden sigue el Raíz Izquierda Derecha política. El propio nombre preorder sugiere que el nodo raíz se atravesaría primero.
Algoritmo
Ahora, veamos el algoritmo de recorrido de preorden.
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
Ejemplo de recorrido de preorden
Ahora, veamos un ejemplo de recorrido de preorden. Será más fácil comprender el proceso de recorrido de preorden con un ejemplo.
Los nodos de color amarillo aún no han sido visitados. Ahora, atravesaremos los nodos del árbol anterior utilizando el recorrido de preorden.
- Comience con el nodo raíz 40. Primero, imprimir 40 y luego recorre recursivamente el subárbol izquierdo.
- Ahora, muévete al subárbol izquierdo. Para el subárbol izquierdo, el nodo raíz es 30. Imprimir 30 y avanza hacia el subárbol izquierdo de 30.
- En el subárbol izquierdo de 30, hay un elemento 25, por lo que imprimir 25 y atraviesa el subárbol izquierdo de 25.
- En el subárbol izquierdo de 25, hay un elemento 15 y 15 no tiene subárbol. Entonces, imprimir 15 y muévase al subárbol derecho de 25.
- En el subárbol derecho de 25, hay 28 y 28 no tiene subárbol. Entonces, imprimir 28 y muévase al subárbol derecho de 30.
- En el subárbol derecho de 30, hay 35 que no tiene subárbol. Entonces imprimir 35 y atraviesa el subárbol derecho de 40.
- En el subárbol derecho de 40, hay 50. Imprimir 50 y atraviesa el subárbol izquierdo de 50.
- En el subárbol izquierdo de 50, hay 45 que no tienen ningún hijo. Entonces, imprimir 45 y atraviesa el subárbol derecho de 50.
- En el subárbol derecho de 50, hay 60. Imprimir 60 y atraviesa el subárbol izquierdo de 60.
- En el subárbol izquierdo de 60, hay 55 que no tiene ningún hijo. Entonces, imprimir 55 y muévase al subárbol derecho de 60.
- En el subárbol derecho de 60, hay 70 que no tienen ningún hijo. Entonces, imprimir 70 y detener el proceso.
Una vez completado el recorrido del pedido anticipado, el resultado final es:
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
conversión de tipos y conversión de tipos en java
Complejidad del recorrido de preorden
La complejidad temporal del recorrido de preorden es En) , donde 'n' es el tamaño del árbol binario.
Considerando que la complejidad espacial del recorrido de preorden es O(1) , si no consideramos el tamaño de la pila para las llamadas a funciones. De lo contrario, la complejidad espacial del recorrido de preorden es Oh) , donde 'h' es la altura del árbol.
Implementación del recorrido de preorden
Ahora, veamos la implementación del recorrido de preorden en diferentes lenguajes de programación.
Programa: Escriba un programa para implementar el recorrido de preorden en lenguaje C.
np estándar
#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; } Producción
Después de la ejecución del código anterior, el resultado será:
Programa: Escriba un programa para implementar el recorrido de preorden 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></'
></'> Producción
Después de la ejecución del código anterior, el resultado será:
Programa: Escriba un programa para implementar el recorrido de preorden en Java.
amontonar ordenar
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(); } } Producción
Después de la ejecución del código anterior, el resultado será:
Entonces, eso es todo sobre el artículo. Espero que el artículo le resulte útil e informativo.