1. Introducción
En este artículo, cubriremos la implementación de un árbol binario en Java.
Por el bien de este artículo, usaremos un árbol binario ordenado que contendrá valores int .
2. Árbol binario
Un árbol binario es una estructura de datos recursiva en la que cada nodo puede tener 2 hijos como máximo.
Un tipo común de árbol binario es un árbol de búsqueda binario, en el que cada nodo tiene un valor que es mayor o igual a los valores del nodo en el subárbol izquierdo, y menor o igual que los valores del nodo en el subárbol derecho. árbol.
Aquí hay una representación visual rápida de este tipo de árbol binario:
Para la implementación, usaremos una clase de nodo auxiliar que almacenará valores int y mantendrá una referencia a cada niño:
class Node { int value; Node left; Node right; Node(int value) { this.value = value; right = null; left = null; } }Luego, agreguemos el nodo inicial de nuestro árbol, generalmente llamado raíz:
public class BinaryTree { Node root; // ... }3. Operaciones comunes
Ahora, veamos las operaciones más comunes que podemos realizar en un árbol binario.
3.1. Insertar elementos
La primera operación que vamos a cubrir es la inserción de nuevos nodos.
Primero, tenemos que encontrar el lugar donde queremos agregar un nuevo nodo para mantener el árbol ordenado . Seguiremos estas reglas comenzando desde el nodo raíz:
- si el valor del nuevo nodo es menor que el del nodo actual, vamos al hijo de la izquierda
- si el valor del nuevo nodo es mayor que el del nodo actual, vamos al hijo correcto
- cuando el nodo actual es nulo, hemos llegado a un nodo hoja y podemos insertar el nuevo nodo en esa posición
Primero, crearemos un método recursivo para hacer la inserción:
private Node addRecursive(Node current, int value) { if (current == null) { return new Node(value); } if (value current.value) { current.right = addRecursive(current.right, value); } else { // value already exists return current; } return current; }A continuación, crearemos el método público que inicia la recursividad desde el nodo raíz :
public void add(int value) { root = addRecursive(root, value); }Ahora veamos cómo podemos usar este método para crear el árbol a partir de nuestro ejemplo:
private BinaryTree createBinaryTree() { BinaryTree bt = new BinaryTree(); bt.add(6); bt.add(4); bt.add(8); bt.add(3); bt.add(5); bt.add(7); bt.add(9); return bt; }3.2. Encontrar un elemento
Agreguemos ahora un método para verificar si el árbol contiene un valor específico.
Como antes, primero crearemos un método recursivo que atraviesa el árbol:
private boolean containsNodeRecursive(Node current, int value) { if (current == null) { return false; } if (value == current.value) { return true; } return value < current.value ? containsNodeRecursive(current.left, value) : containsNodeRecursive(current.right, value); }Aquí, buscamos el valor comparándolo con el valor en el nodo actual, luego continuamos en el hijo izquierdo o derecho dependiendo de eso.
A continuación, creemos el método público que comienza desde la raíz :
public boolean containsNode(int value) { return containsNodeRecursive(root, value); }Ahora, creemos una prueba simple para verificar que el árbol realmente contiene los elementos insertados:
@Test public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(6)); assertTrue(bt.containsNode(4)); assertFalse(bt.containsNode(1)); }Todos los nodos agregados deben estar contenidos en el árbol.
3.3. Eliminar un elemento
Otra operación común es la eliminación de un nodo del árbol.
Primero, tenemos que encontrar el nodo a eliminar de una manera similar a como lo hicimos antes:
private Node deleteRecursive(Node current, int value) { if (current == null) { return null; } if (value == current.value) { // Node to delete found // ... code to delete the node will go here } if (value < current.value) { current.left = deleteRecursive(current.left, value); return current; } current.right = deleteRecursive(current.right, value); return current; }Una vez que encontramos el nodo a eliminar, existen 3 casos principales diferentes:
- un nodo no tiene hijos: este es el caso más simple; solo necesitamos reemplazar este nodo con nulo en su nodo padre
- un nodo tiene exactamente un hijo; en el nodo padre, reemplazamos este nodo con su único hijo.
- un nodo tiene dos hijos : este es el caso más complejo porque requiere una reorganización de árbol
Veamos cómo podemos implementar el primer caso cuando el nodo es un nodo hoja:
if (current.left == null && current.right == null) { return null; }Ahora continuemos con el caso cuando el nodo tiene un hijo:
if (current.right == null) { return current.left; } if (current.left == null) { return current.right; }Aquí, devolvemos el elemento secundario no nulo para que pueda asignarse al nodo principal.
Finalmente, tenemos que manejar el caso donde el nodo tiene dos hijos.
Primero, necesitamos encontrar el nodo que reemplazará al nodo eliminado. Usaremos el nodo más pequeño del nodo que se eliminará en el subárbol derecho:
private int findSmallestValue(Node root) { return root.left == null ? root.value : findSmallestValue(root.left); }Luego, asignamos el valor más pequeño al nodo a eliminar y luego lo eliminaremos del subárbol derecho:
int smallestValue = findSmallestValue(current.right); current.value = smallestValue; current.right = deleteRecursive(current.right, smallestValue); return current;Finalmente, creemos el método público que inicia la eliminación desde la raíz :
public void delete(int value) { root = deleteRecursive(root, value); }Ahora, verifiquemos que la eliminación funcione como se esperaba:
@Test public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(9)); bt.delete(9); assertFalse(bt.containsNode(9)); }4. Atravesando el árbol
En esta sección, veremos diferentes formas de atravesar un árbol, cubriendo en detalle las búsquedas en profundidad y en amplitud.
Usaremos el mismo árbol que usamos antes y mostraremos el orden transversal para cada caso.
4.1. Búsqueda en profundidad
La búsqueda en profundidad es un tipo de recorrido que profundiza tanto como sea posible en cada niño antes de explorar al siguiente hermano.
Hay varias formas de realizar una búsqueda en profundidad: en orden, pre-orden y post-orden.
El recorrido en orden consiste en visitar primero el subárbol izquierdo, luego el nodo raíz y finalmente el subárbol derecho:
public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); System.out.print(" " + node.value); traverseInOrder(node.right); } }Si llamamos a este método, la salida de la consola mostrará el recorrido en orden:
3 4 5 6 7 8 9El recorrido de la reserva visita primero el nodo raíz, luego el subárbol izquierdo y finalmente el subárbol derecho:
public void traversePreOrder(Node node) { if (node != null) { System.out.print(" " + node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }Y revisemos el recorrido del pedido anticipado en la salida de la consola:
6 4 3 5 8 7 9El recorrido posterior al pedido visita el subárbol izquierdo, el subárbol derecho y el nodo raíz al final:
public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.value); } }Aquí están los nodos en orden posterior:
3 5 4 7 9 8 64.2. Búsqueda primero en amplitud
Este es otro tipo común de recorrido que visita todos los nodos de un nivel antes de pasar al siguiente nivel .
Este tipo de recorrido también se denomina orden de nivel y visita todos los niveles del árbol comenzando desde la raíz y de izquierda a derecha.
Para la implementación, usaremos una cola para mantener los nodos de cada nivel en orden. Extraeremos cada nodo de la lista, imprimiremos sus valores y luego agregaremos sus hijos a la cola:
public void traverseLevelOrder() { if (root == null) { return; } Queue nodes = new LinkedList(); nodes.add(root); while (!nodes.isEmpty()) { Node node = nodes.remove(); System.out.print(" " + node.value); if (node.left != null) { nodes.add(node.left); } if (node.right != null) { nodes.add(node.right); } } }En este caso, el orden de los nodos será:
6 4 8 3 5 7 95. Conclusión
En este artículo, hemos visto cómo implementar un árbol binario ordenado en Java y sus operaciones más comunes.
El código fuente completo de los ejemplos está disponible en GitHub.