recorrido en orden se define como un tipo de técnica de recorrido de árbol que sigue el patrón Izquierda-Raíz-Derecha, tal que:
- El subárbol izquierdo se recorre primero.
- Luego se atraviesa el nodo raíz de ese subárbol.
- Finalmente, se atraviesa el subárbol derecho.
recorrido en orden
Algoritmo para el recorrido en orden del árbol binario
El algoritmo para el recorrido en orden se muestra a continuación:
Orden (raíz):
- Siga los pasos 2 a 4 hasta root! = NULL
- En orden (raíz -> izquierda)
- Escribir raíz -> datos
- En orden (raíz -> derecha)
- Finalizar bucle
¿Cómo funciona el recorrido en orden del árbol binario?
Considere el siguiente árbol:
ls comandos linux
Ejemplo de árbol binario
Si realizamos un recorrido en orden en este árbol binario, entonces el recorrido será el siguiente:
Paso 1: El recorrido irá de 1 a su subárbol izquierdo, es decir, 2, luego de 2 a la raíz de su subárbol izquierdo, es decir, 4. Ahora 4 no tiene subárbol izquierdo, por lo que será visitado. Tampoco tiene ningún subárbol derecho. Entonces no más recorrido desde 4
Se visita el nodo 4
Paso 2: Como el subárbol izquierdo de 2 se visita por completo, ahora lee los datos del nodo 2 antes de pasar a su subárbol derecho.
Se visita el nodo 2
Paso 3: Ahora se atravesará el subárbol derecho de 2, es decir, se moverá al nodo 5. Para el nodo 5 no hay un subárbol izquierdo, por lo que se visita y luego de eso, el recorrido regresa porque no hay un subárbol derecho del nodo 5.
Se visita el nodo 5
Etapa 4: Como está el subárbol izquierdo del nodo 1, se visitará la raíz misma, es decir, el nodo 1.
Se visita el nodo 1
Paso 5: Se visita el subárbol izquierdo del nodo 1 y el propio nodo. Entonces, ahora se atravesará el subárbol derecho de 1, es decir, se moverá al nodo 3. Como el nodo 3 no tiene un subárbol izquierdo, se visita.
Se visita el nodo 3
Paso 6: Se visita el subárbol izquierdo del nodo 3 y el propio nodo. Así que recorra hasta el subárbol derecho y visite el nodo 6. Ahora el recorrido finaliza cuando se atraviesan todos los nodos.
Se recorre el árbol completo.
Entonces el orden de recorrido de los nodos es 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Programa para implementar el recorrido en orden del árbol binario:
A continuación se muestra la implementación del código del recorrido en orden:
C++
aws redes sociales
// C++ program for inorder traversals> #include> using> namespace> std;> // Structure of a Binary Tree Node> struct> Node {> >int> data;> >struct> Node *left, *right;> >Node(>int> v)> >{> >data = v;> >left = right = NULL;> >}> };> // Function to print inorder traversal> void> printInorder(>struct> Node* node)> {> >if> (node == NULL)> >return>;> >// First recur on left subtree> >printInorder(node->izquierda);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->bien); } // Código del controlador int main() { struct Nodo* raíz = nuevo Nodo(1); raíz->izquierda = nuevo Nodo(2); raíz->derecha = nuevo Nodo(3); raíz->izquierda->izquierda = nuevo Nodo(4); raíz->izquierda->derecha = nuevo Nodo(5); raíz->derecha->derecha = nuevo Nodo(6); // Llamada a función cout<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
Java
// Java program for inorder traversals> import> java.util.*;> // Structure of a Binary Tree Node> class> Node {> >int> data;> >Node left, right;> >Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Main class> class> GFG {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >System.out.print(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> main(String[] args)> >{> >Node root =>new> Node(>1>);> >root.left =>new> Node(>2>);> >root.right =>new> Node(>3>);> >root.left.left =>new> Node(>4>);> >root.left.right =>new> Node(>5>);> >root.right.right =>new> Node(>6>);> >// Function call> >System.out.println(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> // This code is contributed by prasad264> |
>
>
Python3
par c ++
# Structure of a Binary Tree Node> class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Function to print inorder traversal> def> printInorder(node):> >if> node>is> None>:> >return> ># First recur on left subtree> >printInorder(node.left)> ># Now deal with the node> >print>(node.data, end>=>' '>)> ># Then recur on right subtree> >printInorder(node.right)> # Driver code> if> __name__>=>=> '__main__'>:> >root>=> Node(>1>)> >root.left>=> Node(>2>)> >root.right>=> Node(>3>)> >root.left.left>=> Node(>4>)> >root.left.right>=> Node(>5>)> >root.right.right>=> Node(>6>)> ># Function call> >print>(>'Inorder traversal of binary tree is:'>)> >printInorder(root)> |
>
>
C#
constructor de Python
// C# program for inorder traversals> using> System;> // Structure of a Binary Tree Node> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Class to store and print inorder traversal> public> class> BinaryTree {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >Console.Write(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> Main()> >{> >Node root =>new> Node(1);> >root.left =>new> Node(2);> >root.right =>new> Node(3);> >root.left.left =>new> Node(4);> >root.left.right =>new> Node(5);> >root.right.right =>new> Node(6);> >// Function call> >Console.WriteLine(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> |
>
>
iterando una lista en java
JavaScript
// JavaScript program for inorder traversals> // Structure of a Binary Tree Node> class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // Function to print inorder traversal> function> printInorder(node) {> >if> (node ===>null>) {> >return>;> >}> > >// First recur on left subtree> >printInorder(node.left);> > >// Now deal with the node> >console.log(node.data);> > >// Then recur on right subtree> >printInorder(node.right);> }> // Driver code> const root =>new> Node(1);> root.left =>new> Node(2);> root.right =>new> Node(3);> root.left.left =>new> Node(4);> root.left.right =>new> Node(5);> root.right.right =>new> Node(6);> // Function call> console.log(>'Inorder traversal of binary tree is: '>);> printInorder(root);> |
>
>Producción
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Explicación:
Cómo funciona el recorrido en orden
Análisis de complejidad:
Complejidad del tiempo: O(N) donde N es el número total de nodos. Porque atraviesa todos los nodos al menos una vez.
Espacio Auxiliar: O(1) si no se considera ningún espacio de pila de recursividad. De lo contrario, O(h) donde h es la altura del árbol
- En el peor de los casos, h puede ser lo mismo que norte (cuando el árbol es un árbol torcido)
- En el mejor de los casos, h puede ser lo mismo que calma (cuando el árbol es un árbol completo)
Casos de uso de Inorder Traversal:
En el caso de BST (árbol de búsqueda binaria), si en algún momento es necesario obtener los nodos en orden no decreciente, la mejor manera es implementar un recorrido en orden.
Artículos relacionados:
- Tipos de recorridos de árboles
- Recorrido iterativo en orden
- Construir un árbol binario a partir del recorrido en preorden y en orden
- Recorrido de Morris para recorrido en orden del árbol
- Recorrido en orden sin recursividad