Recorrido por niveles del árbol de búsqueda binaria
El recorrido por niveles del árbol de búsqueda binaria consiste en recorrer nivel por nivel, almacenando los nodos de cada nivel en una cola, y luego realizar operaciones de sacar de la cola (extraer nodos) y poner en la cola (almacenar los nodos del siguiente nivel), logrando así el propósito del recorrido.
Para soportar el recorrido por niveles, se introduce una cola:
-
Si el nodo raíz está vacío, no hay nada que recorrer;
-
Si el nodo raíz no está vacío:
-
Primero, poner el nodo raíz en la cola;
-
Mientras la cola no esté vacía:
- Extraer el nodo al frente de la cola y recorrerlo;
- Si el nodo al frente de la cola tiene hijo izquierdo, poner el hijo izquierdo en la cola;
- Si el nodo al frente de la cola tiene hijo derecho, poner el hijo derecho en la cola;
-
A continuación se muestran los pasos en orden:
(1)Primero se extrae el nodo raíz y se coloca en la cola

(2)Se extrae 29, los nodos hijos izquierdo y derecho entran en la cola

(3)El 17, que está al frente de la cola, sale de la cola; los nodos hijos 14 y 23 entran en la cola.

(4)31 sale de la cola; los nodos hijos 30 y 43 entran en la cola

(5)Finalmente, todos salen de la cola

// Recorrido por niveles del árbol de búsqueda binaria
public void levelOrder(){
// Usamos LinkedList como nuestra cola
LinkedList<Node> q = new LinkedList<Node>();
q.add(root);
while( !q.isEmpty() ){
Node node = q.remove();
System.out.println(node.key);
if( node.left != null )
q.add( node.left );
if( node.right != null )
q.add( node.right );
}
}
...
Código de ejemplo en Java
Descargar el paquete de código fuente:Download
Código del archivo src/ejemplo/binary/LevelTraverse.java:
import java.util.LinkedList;
/**
* Recorrido por niveles
*/
public class LevelTraverse<Key extends Comparable<Key>, Value>{
// Los nodos del árbol son una clase privada; el mundo exterior no necesita conocer la implementación específica de los nodos del árbol de búsqueda binaria
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = right = null;
}
}
private Node root; // Nodo raíz
private int count; // Número de nodos del árbol
// Constructor, por defecto construye un árbol de búsqueda binaria vacío
public LevelTraverse() {
root = null;
count = 0;
}
// Devuelve el número de nodos del árbol de búsqueda binaria
public int size() {
return count;
}
// Devuelve si el árbol de búsqueda binaria está vacío
public boolean isEmpty() {
return count == 0;
}
// Inserta un nuevo par de datos (key, value) en el árbol de búsqueda binaria
public void insert(Key key, Value value){
root = insert(root, key, value);
}
// Comprueba si existe la clave key en el árbol de búsqueda binaria
public boolean contain(Key key){
return contain(root, key);
}
// Busca en el árbol de búsqueda binaria el valor correspondiente a la clave key. Si este valor no existe, devuelve null
public Value search(Key key){
return search( root , key );
}
// Recorrido preorden del árbol de búsqueda binaria
public void preOrder(){
preOrder(root);
}
// Recorrido inorden del árbol de búsqueda binaria
public void inOrder(){
inOrder(root);
}
// Recorrido postorden del árbol de búsqueda binaria
public void postOrder(){
postOrder(root);
}
// Recorrido por niveles del árbol de búsqueda binaria
public void levelOrder(){
// Usamos LinkedList como nuestra cola
LinkedList<Node> q = new LinkedList<Node>();
q.add(root);
while( !q.isEmpty() ){
Node node = q.remove();
System.out.println(node.key);
if( node.left != null )
q.add( node.left );
if( node.right != null )
q.add( node.right );
}
}
//********************
//* Funciones auxiliares del árbol de búsqueda binaria
//********************
// Inserta el nodo (key, value) en el árbol de búsqueda binaria con raíz node, usando un algoritmo recursivo
// Devuelve la raíz del árbol de búsqueda binaria después de insertar el nuevo nodo
private Node insert(Node node, Key key, Value value){
if( node == null ){
count ++;
return new Node(key, value);
}
if( key.compareTo(node.key) == 0 )
node.value = value;
else if( key.compareTo(node.key) < 0 )
node.left = insert( node.left , key, value);
else // key > node->key
node.right = insert( node.right, key, value);
return node;
}
// Comprueba si el árbol de búsqueda binaria con raíz node contiene un nodo con clave key, usando un algoritmo recursivo
private boolean contain(Node node, Key key){
if( node == null )
return false;
if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else // key > node->key
return contain( node.right , key );
}
// Busca el value correspondiente a key en el árbol de búsqueda binaria con raíz node, algoritmo recursivo
// Si el value no existe, devuelve NULL
private Value search(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else // key > node->key
return search( node.right, key );
}
// Realiza un recorrido preorden en el árbol de búsqueda binaria con raíz node, algoritmo recursivo
private void preOrder(Node node){
if( node != null ){
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
}
// Realiza un recorrido inorden en el árbol de búsqueda binaria con raíz node, algoritmo recursivo
private void inOrder(Node node){
if( node != null ){
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
}
// Realiza un recorrido postorden en el árbol de búsqueda binaria con raíz node, algoritmo recursivo
private void postOrder(Node node){
if( node != null ){
postOrder(node.left);
postOrder(node.right);
System.out.println(node.key);
}
}
}