Uno de los temas sobre desarrollo de software que todos los desarrolladores de software deberían conocer y que por lo mismo es cuestionado en una gran parte de las entrevistas es el manejo de arboles binarios, en este post entraremos en detalle en este tema y lo analizaremos paso a paso.
Introducción
En este ejemplo se mostrará como desarrollar un árbol binario balanceado en Java, esto significa que los datos serán ordenados en tiempo de inserción de acuerdo a lo siguiente:
- Si el valor a insertar es menor al valor del nodo se insertará a la izquierda
- Si el valor a insertar es mayor al valor del nodo se insertará a la derecha
La clase a desarrollar será de acuerdo al siguiente diagrama:
Analizando la clase
El siguiente paso será analizar la clase a desarrollar, para esto expliquemos a detalle cada uno de los componentes:
- Atributos
- value: Cada nodo contendrá un valor almacenado
- left : Cada nodo tendrá una rama izquierda
- right : Cada nodo tendrá una rama derecha
- Métodos
- add : Permite agregar un nuevo valor al árbol binario
- find : Permite buscar un valor en el árbol binario
- printInOrder : Permite imprimir el árbol en modo In order
- printPreOrder : Permite imprimir el árbol en modo Pre Order
- printPosOrder : Permite imprimir el árbol en modo Pos Order
Creando el árbol
Para crear el árbol solo debemos crear una clase llamada Node (Nodo), veamos el código necesario para definir los atributos a utilizar:
public class Node {
private Integer value;
private Node left;
private Node right;
public Node(Integer value) {
this.value = value;
}
//... Getters y setters
}
Agregar un valor nuevo
Para agregar un valor nuevo al árbol la lógica será la siguiente:
- Si el valor a agregar es menor al del nodo actual se insertará del lado izquierdo
- Si el valor a agregar es mayor al del nodo actual se insertará del lado derecho
Recordemos que cada nodo puede tener solo 2 nodos hijos, por lo tanto si el nodo actual contiene un 10 y el valor a insertar es un 7 este se insertará del lado izquierdo, si ya hay un valor insertado del lado izquierdo se ejecutará la misma lógica con el valor insertado hasta llegar a un nodo izquierdo o derecho nulo, veamos el código:
public class Node {
...// El código anterior
public void add(Integer value) {
if (value < this.value) {
if (left != null) {
left.add(value);
} else {
left = new Node(value);
}
} else {
if (right != null) {
right.add(value);
} else {
right = new Node(value);
}
}
}
}
Como se puede observar en el código se utiliza recursividad para agregar los nodos en caso de que ya existan en el árbol.
Buscar un valor
La lógica para buscar un valor en el árbol es muy similar que para insertarlo, en el código que se mostrará se utilizará la clase Optional agregada en Java 8, veamos el código:
import java.util.Optional;
public class Node {
...// El código anterior
public Optional<Node> find(Integer value) {
if (value == this.value) {
return Optional.of(this);
} else if (value < this.value) {
if (this.left != null) {
return this.left.find(value);
} else {
return Optional.empty();
}
} else {
if (this.right != null) {
return this.right.find(value);
} else {
return Optional.empty();
}
}
}
}
Como se puede ver es necesario importar la clase Optional del paquete java.util.
Imprimir los valores del árbol binario
Para imprimir los valores es necesario iterar el árbol utilizando recursividad y existen 3 formas de hacerlo:
- In order: Imprime el valor del nodo izquierdo, después el del nodo contenedor y al final el del nodo derecho
- Pre order: Imprime el valor del nodo contenedor, después el del nodo izquierdo y al final el del nodo derecho
- Pos order: Imprime el valor del nodo izquierdo, después el del nodo derecho y al final el del nodo contenedor
Veámoslo en código:
public class Node{
...// El código anterior
public void printInOrder(){
if(left!=null){
left.printInOrder();
}
System.out.println(value);
if(right!=null){
right.printInOrder();
}
}
public void printPreOrder(){
System.out.println(value);
if(left!=null){
left.printPreOrder();
}
if(right!=null){
right.printPreOrder();
}
}
public void printPosOrder(){
if(left!=null){
left.printPreOrder();
}
if(right!=null){
right.printPreOrder();
}
System.out.println(value);
}
}
Todo el código junto
Si unimos el código anterior queda del siguiente modo:
import java.util.Optional;
/**
* @author raidentrance
*
*/
public class Node {
private Integer value;
private Node left;
private Node right;
public Node(Integer value) {
this.value = value;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public void add(Integer value) {
if (value < this.value) {
if (left != null) {
left.add(value);
} else {
left = new Node(value);
}
} else {
if (right != null) {
right.add(value);
} else {
right = new Node(value);
}
}
}
public Optional<Node> find(Integer value) {
if (value == this.value) {
return Optional.of(this);
} else if (value < this.value) {
if (this.left != null) {
return this.left.find(value);
} else {
return Optional.empty();
}
} else {
if (this.right != null) {
return this.right.find(value);
} else {
return Optional.empty();
}
}
}
public void printInOrder() {
if (left != null) {
left.printInOrder();
}
System.out.println(value);
if (right != null) {
right.printInOrder();
}
}
public void printPreOrder() {
System.out.println(value);
if (left != null) {
left.printPreOrder();
}
if (right != null) {
right.printPreOrder();
}
}
public void printPosOrder() {
if (left != null) {
left.printPreOrder();
}
if (right != null) {
right.printPreOrder();
}
System.out.println(value);
}
@Override
public String toString() {
return "Node [value=" + value + ", left=" + left + ", right=" + right + "]";
}
}
Probando el árbol
Para probar el árbol que creamos, utilizaremos una clase nueva llamada TreeTest, veamos el código:
import java.util.Optional;
/**
* @author raidentrance
*
*/
public class TreeTest {
public static void main(String[] args) {
Node root = new Node(10);
root.add(5);
root.add(15);
root.add(8);
Optional<Node> result = root.find(11);
if (result.isPresent()) {
System.out.println(result.get());
} else {
System.out.println("Value not found");
}
result = root.find(8);
if (result.isPresent()) {
System.out.println(result.get());
} else {
System.out.println("Value not found");
}
System.out.println("Print in order");
root.printInOrder();
System.out.println("Print pos order");
root.printPosOrder();
System.out.println("Print pre order");
root.printPreOrder();
}
}
Producirá la siguiente salida:
Value not found Node [value=8, left=null, right=null] Print in order 5 8 10 15 Print pos order 5 8 15 10 Print pre order 10 5 8 15
Si te gusta el contenido compártelo y no olvides seguirnos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.
Autor: Alejandro Agapito Bautista
Twitter: @raidentrance
Contacto:raidentrance@gmail.com
devs4j 
La persona autora de este artículo se ha confundido de conceptos. Ha mezclado los de árbol binario (AB) y árbol de búsqueda binaria (ABB).
Un ABB es un subconjunto de AB porque tiene la restricción de que los nodos situados en el lado izquierdo deben tener el valor de su raíz menor que el de su padre. Si es mayor, el nodo debe estar situado a su derecha.
En cambio, cuando se inserta un nodo en un AB, el nodo tiene que ir donde se le indique el criterio de inserción. Por ejemplo: si yo digo que los pares van a la izquierda, en un AB los nodos pares irán a la izquierda y así sucesivamente.
Es en un ABB donde sí se tiene en cuenta el valor de la raíz del nodo a insertar. Si este tiene 8 y el padre tiene 7, entonces el nodo irá a parar al hijo derecho.
Además, el diagrama de clases debe representar la estructura de herencia siguiente:
Árbol <- AB <- ABB
Me gustaMe gusta
tengo un problema con el optional y es que dicen que el of y el empty no existe
Me gustaMe gusta
Porque tu impresion en POSTORDER no muestra los valores ascendentemente?
Me gustaMe gusta
es por el primer nodo que creas xd
Me gustaMe gusta
Si el primer nodo que creas en el main es mayor que todos, si te saldrá ascendentemente, de lo contrario, el primer nodo creado del arbol (osea la raiz) será el final de mostrar posorden
Me gustaMe gusta