En este tutorial, aprenderá sobre diferentes técnicas de recorrido de árboles. Además, encontrará ejemplos prácticos de diferentes métodos de cruce de árboles en C, C ++, Java y Python.
Atravesar un árbol significa visitar todos los nodos del árbol. Por ejemplo, es posible que desee agregar todos los valores en el árbol o encontrar el más grande. Para todas estas operaciones, deberá visitar cada nodo del árbol.
Las estructuras de datos lineales como matrices, pilas, colas y listas vinculadas solo tienen una forma de leer los datos. Pero una estructura de datos jerárquica como un árbol se puede atravesar de diferentes maneras.
Cruce de árboles
Pensemos en cómo podemos leer los elementos del árbol en la imagen que se muestra arriba.
Empezando desde arriba, de izquierda a derecha
1 -> 12 -> 5 -> 6 -> 9
Empezando desde abajo, de izquierda a derecha
5 -> 6 -> 12 -> 9 -> 1
Aunque este proceso es algo sencillo, no respeta la jerarquía del árbol, solo la profundidad de los nodos.
En su lugar, usamos métodos transversales que tienen en cuenta la estructura básica de un árbol, es decir
struct node ( int data; struct node* left; struct node* right; )
El nodo de estructura señalado por left y right podría tener otros hijos de left y right, por lo que deberíamos pensar en ellos como subárboles en lugar de subnodos.
Según esta estructura, cada árbol es una combinación de
- Un nodo que transporta datos
- Dos subárboles
Subárbol izquierdo y derecho
Recuerde que nuestro objetivo es visitar cada nodo, por lo que debemos visitar todos los nodos del subárbol, visitar el nodo raíz y visitar también todos los nodos del subárbol derecho.
Dependiendo del orden en el que hagamos esto, puede haber tres tipos de recorrido.
Traversal en orden
- Primero, visite todos los nodos en el subárbol izquierdo
- Entonces el nodo raíz
- Visite todos los nodos en el subárbol derecho
inorder(root->left) display(root->data) inorder(root->right)
Recorrido de reserva
- Visite el nodo raíz
- Visite todos los nodos en el subárbol izquierdo
- Visite todos los nodos en el subárbol derecho
display(root->data) preorder(root->left) preorder(root->right)
Recorrido posorden
- Visite todos los nodos en el subárbol izquierdo
- Visite todos los nodos en el subárbol derecho
- Visita el nodo raíz
postorder(root->left) postorder(root->right) display(root->data)
Visualicemos el recorrido en orden. Partimos del nodo raíz.
Subárbol izquierdo y derecho
Primero atravesamos el subárbol izquierdo. También debemos recordar visitar el nodo raíz y el subárbol derecho cuando este árbol esté terminado.
Pongamos todo esto en una pila para que recordemos.
Apilar
Ahora atravesamos el subárbol apuntado en la PARTE SUPERIOR de la pila.
De nuevo, seguimos la misma regla de orden
Subárbol izquierdo -> raíz -> subárbol derecho
Después de atravesar el subárbol izquierdo, nos quedamos con
Pila final
Dado que el nodo "5" no tiene subárboles, lo imprimimos directamente. Después de eso, imprimimos su padre "12" y luego el hijo derecho "6".
Poner todo en una pila fue útil porque ahora que se ha atravesado el subárbol izquierdo del nodo raíz, podemos imprimirlo e ir al subárbol derecho.
Después de pasar por todos los elementos, obtenemos el recorrido en orden como
5 -> 12 -> 6 -> 1 -> 9
No tenemos que crear la pila nosotros mismos porque la recursividad mantiene el orden correcto para nosotros.
Ejemplos de Python, Java y C / C ++
Python Java C C + # Tree traversal in Python class Node: def __init__(self, item): self.left = None self.right = None self.val = item def inorder(root): if root: # Traverse left inorder(root.left) # Traverse root print(str(root.val) + "->", end='') # Traverse right inorder(root.right) def postorder(root): if root: # Traverse left postorder(root.left) # Traverse right postorder(root.right) # Traverse root print(str(root.val) + "->", end='') def preorder(root): if root: # Traverse root print(str(root.val) + "->", end='') # Traverse left preorder(root.left) # Traverse right preorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Inorder traversal ") inorder(root) print("Preorder traversal ") preorder(root) print("Postorder traversal ") postorder(root)
// Tree traversal in Java class Node ( int item; Node left, right; public Node(int key) ( item = key; left = right = null; ) ) class BinaryTree ( // Root of Binary Tree Node root; BinaryTree() ( root = null; ) void postorder(Node node) ( if (node == null) return; // Traverse left postorder(node.left); // Traverse right postorder(node.right); // Traverse root System.out.print(node.item + "->"); ) void inorder(Node node) ( if (node == null) return; // Traverse left inorder(node.left); // Traverse root System.out.print(node.item + "->"); // Traverse right inorder(node.right); ) void preorder(Node node) ( if (node == null) return; // Traverse root System.out.print(node.item + "->"); // Traverse left preorder(node.left); // Traverse right preorder(node.right); ) public static void main(String() args) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("Inorder traversal"); tree.inorder(tree.root); System.out.println("Preorder traversal "); tree.preorder(tree.root); System.out.println("Postorder traversal"); tree.postorder(tree.root); ) )
// Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // preorderTraversal traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // postorderTraversal traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
// Tree traversal in C++ #include using namespace std; struct Node ( int data; struct Node *left, *right; Node(int data) ( this->data = data; left = right = NULL; ) ); // Preorder traversal void preorderTraversal(struct Node* node) ( if (node == NULL) return; cout left); preorderTraversal(node->right); ) // Postorder traversal void postorderTraversal(struct Node* node) ( if (node == NULL) return; postorderTraversal(node->left); postorderTraversal(node->right); cout left); cout right); ) int main() ( struct Node* root = new Node(1); root->left = new Node(12); root->right = new Node(9); root->left->left = new Node(5); root->left->right = new Node(6); cout << "Inorder traversal "; inorderTraversal(root); cout << "Preorder traversal "; preorderTraversal(root); cout << "Postorder traversal "; postorderTraversal(root);
