RESERVA DE RECORRIDO DEL ÁRBOL BINARIO - TECHCODEVIEW.COM

recorrido de preorden se define como un tipo de recorrido del árbol que sigue la política Raíz-Izquierda-Derecha donde:

Primero se visita el nodo raíz del subárbol.

Luego se recorre el subárbol izquierdo.

Por último, se recorre el subárbol derecho.

recorrido de preorden

Algoritmo para el recorrido anticipado del árbol binario

El algoritmo para el recorrido de preorden se muestra a continuación:

Reserva (raíz):

Siga los pasos 2 a 4 hasta root! = NULL

Escribir raíz -> datos

Reservar (raíz -> izquierda)

Reservar (raíz -> derecha)

Finalizar bucle

¿Cómo funciona el recorrido de pedido anticipado del árbol binario?

Considere el siguiente árbol:

Ejemplo de árbol binario

Si realizamos un recorrido de preorden en este árbol binario, el recorrido será el siguiente:

Paso 1: Al principio se visitará la raíz, es decir, el nodo 1.

Se visita el nodo 1

Paso 2: Después de esto, recorra el subárbol izquierdo. Ahora se visita la raíz del subárbol izquierdo, es decir, se visita el nodo 2.

Se visita el nodo 2

Paso 3: Nuevamente se recorre el subárbol izquierdo del nodo 2 y se visita la raíz de ese subárbol, es decir, el nodo 4.

Se visita el nodo 4

Etapa 4: No hay ningún subárbol de 4 y se visita el subárbol izquierdo del nodo 2. Entonces, ahora se atravesará el subárbol derecho del nodo 2 y se visitará la raíz de ese subárbol, es decir, el nodo 5.

Se visita el nodo 5

Paso 5: Se visita el subárbol izquierdo del nodo 1. Entonces, ahora se atravesará el subárbol derecho del nodo 1 y se visitará el nodo raíz, es decir, el nodo 3.

Se visita el nodo 3

Paso 6: El nodo 3 no tiene subárbol izquierdo. Entonces se atravesará el subárbol derecho y se visitará la raíz del subárbol, es decir, el nodo 6. Después de esto no queda ningún nodo que aún no haya sido atravesado. Así termina el recorrido.

Se visita el árbol completo

Entonces el orden de recorrido de los nodos es 1 -> 2 -> 4 -> 5 -> 3 -> 6 .

Programa para implementar el recorrido de pedido anticipado del árbol binario

A continuación se muestra la implementación del código del recorrido del pedido anticipado:

C++

  // C++ program for preorder 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 preorder traversal void printPreorder(struct Node* node) {  if (node == NULL)  return;  // Deal with the node  cout  < < node->datos < < ' ';  // Recur on left subtree  printPreorder(node->izquierda);  // Recurre en el subárbol derecho printPreorder(nodo->derecha); } // 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 < < 'Preorder traversal of binary tree is: 
';  printPreorder(root);  return 0; }

Java

  // Java program for preorder traversals class Node {  int data;  Node left, right;  public Node(int item) {  data = item;  left = right = null;  } } class BinaryTree {  Node root;  BinaryTree() {  root = null;  }  // Function to print preorder traversal  void printPreorder(Node node) {  if (node == null)  return;  // Deal with the node  System.out.print(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void main(String[] args) {  BinaryTree tree = new BinaryTree();  // Constructing the binary tree  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.right = new Node(6);  // Function call  System.out.println('Preorder traversal of binary tree is: ');  tree.printPreorder(tree.root);  } }

Python3

  # Python program for preorder traversals # Structure of a Binary Tree Node class Node: def __init__(self, v): self.data = v self.left = None self.right = None # Function to print preorder traversal def printPreorder(node): if node is None: return # Deal with the node print(node.data, end=' ') # Recur on left subtree printPreorder(node.left) # Recur on right subtree printPreorder(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('Preorder traversal of binary tree is:') printPreorder(root)

  // C# program for preorder 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 print preorder traversal public class BinaryTree {  // Function to print preorder traversal  public static void printPreorder(Node node)  {  if (node == null)  return;  // Deal with the node  Console.Write(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(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(  'Preorder traversal of binary tree is: ');  printPreorder(root);  } } // This code is contributed by Susobhan Akhuli

JavaScript

  // Structure of a Binary Tree Node class Node {  constructor(v) {  this.data = v;  this.left = null;  this.right = null;  } } // Function to print preorder traversal function printPreorder(node) {  if (node === null) {  return;  }  // Deal with the node  console.log(node.data);  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right); } // Driver code function main() {  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('Preorder traversal of binary tree is:');  printPreorder(root); } main();

Producción

Preorder traversal of binary tree is: 1 2 4 5 3 6

Explicación:

Cómo funciona el recorrido de preorden

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, Oh) 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 recorrido de pedidos anticipados:

Algunos casos de uso de recorrido de preorden son:

Esto se utiliza a menudo para crear una copia de un árbol.
También resulta útil obtener la expresión del prefijo de un árbol de expresiones.

Artículos relacionados:

Tipos de recorrido de árbol
Recorrido iterativo de preorden
Compruebe si la matriz dada puede representar el recorrido del pedido anticipado de BST
Preorden desde recorridos en orden y postorden
Encuentre el enésimo nodo en el recorrido de preorden de un árbol binario
Recorrido previo al pedido de un árbol N-ario