Diferencia entre revisiones de «Árbol binario»
Deshecha la edición 26718688 de 186.28.180.165 (disc.) |
|||
| Línea 459: | Línea 459: | ||
}else{ |
}else{ |
||
System.out.println(dato); |
System.out.println(dato); |
||
} |
|||
} |
|||
==== Recorrido en postorden ==== |
==== Recorrido en postorden ==== |
||
Revisión del 03:25 28 may 2009
En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener mas de dos hijos (de ahi el nombre "binario"). Si algun hijo tiene como referencia a null, es decir que no almacena ningun dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
Definición de teoría de grafos
.png)
En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos.
Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.
Tipos de árboles binarios
- Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
- Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
- Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura)
- A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
Especificación en Maude
Definiremos en Maude un módulo, para ver como se especifica un Árbol Binario con sus operaciones más básicas:
fmod ÁRBOL-BINARIO{X::TRIV} is
sorts ArbolBNV{X}ArbolB{X}.
subsort ArbolBNV{X}<ArbolB{X}.
***generadores
op crear:->ArbolB{X}[ctor].
op arbolBinario:X$EltArbolB{X}ArbolB{X}->
***constructores
ops hijoIzq hijoDer:ArbolBNV{X}->ArbolB{X}
***selectores
op raiz:ArbolBNV{X}->X$Elt.
***variables
var R:X$Elt.
vars I D:ArbolB{X}.
***ecuaciones
eq raiz(arbolBinario(R,I,D))=R.
eq hijoIzq(arbolBinario(R,I,D))=I.
eq hijoDer(arbolBinario(R,I,D))=D.
endfm
Aquí definiremos un nuevo módulo para incorporar operaciones útiles y básicas en un Árbol Binario:
fmod ÁRBOL-BIN-OPS-1{X::TRIV}is
protecting ÁRBOL-BINARIO{X}.
protecting NAT.
***selectores
ops numElemsaltura:ArbolB{X}->Nat.
op igualForma:ArbolB{X}ArbolB{X}->Bool[comm].
***variables
vars N M:Nat.
vars R R2 R3:X$Elt.
vars I I2 D D2:ArbolB{X}.
var A:ArbolBNV{X}.
***ecuaciones
eq numElems(crear)=0.
eq numElems(arbolBinario(R,I,D))=1+numElems(I)+numElems(D).
eq altura(crear)=0.
eq altura(arbolBinario(R,I,D))=1+max(altura(I),altura(D)).
eq igualForma(crear,crear)=true.
eq igualForma(crear,A)=false.
eq igualForma(arbolBinario(R,I,D),arbolBinario(R2,I2,D2))=
igualForma(I,I2)andigualForma(D,D2).
endfm
Y aquí encontramos operaciones más avanzadas para comprobar ciertos estados del Árbol Binario:
fmod ÁRBOL-BIN-OPS-3{X::TRIV} is
protecting ÁRBOL-BINARIO{X}.
protecting ÁRBOL-BIN-OPS-1{X}.
protecting INT.
***selectores
ops esLleno? esCompleto?:ArbolB{X}->Bool.
ops esEquilibrado? esTotEqui?:ArbolB{X}->Bool.
***variables
vars R:X$Elt.
vars ID:ArbolB{X}.
***ecuaciones
eq esLleno?(crear)=true.
eq esLleno?(arbolBinario(R,I,D))=altura(I)==altura(D)and
esLleno?(I) and esLleno?(D).
eq esCompleto?(crear)=true.
eq esCompleto?(arbolBinario(R,I,D))=(altura(I)==altura(D) and
esLleno?(I) and esCompleto?(D)) or
(altura(I)==(altura(D)+1) and
esCompleto?(I) and esLleno?(D)).
eq esEquilibrado?(crear)=true.
eq esEquilibrado?(arbolBinario(R,I,D))=sd(altura(I),altura(D))<=1and
esEquilibrado?(I) and esEquilibrado?(D)
eq esTotEqui?(crear)=true.
eq esTotEqui?(arbolBinario(R,I,D))=sd(numElems(I),numElems(D))<=1and
esTotEqui?(I) and esTotEqui?(D).
endfm
Especificación en Java
Funciones básicas de un árbol binario numérico, aparte de los hijos vamos a poner un dato para tener la información de descendencia:
public class ArbolBinarioNumerico {
private ArbolBinarioNumerico hijoDerecho; private ArbolBinarioNumerico hijoIzquierdo; private ArbolBinarioNumerico padre; private int dato;
public ArbolBinarioNumerico(int t){
hijoDerecho=null;
hijoIzquierdo=null;
padre=null;
dato=t;
}
public ArbolBinarioNumerico getHijoDerecho() {
return hijoDerecho;
}
public void setHijoDerecho(ArbolBinarioNumerico hijo) {
if(!(esta(hijo.getDato()))){
this.hijoDerecho = hijo;
hijoDerecho.setPadre(this);
}
}
public void setHijoDerecho(int dato) {
ArbolBinarioNumerico aux=new ArbolBinarioNumerico(dato);
if(!(esta(aux.getDato()))){
this.hijoDerecho = aux;
hijoDerecho.setPadre(this);
}
}
public ArbolBinarioNumerico getHijoIzquierdo() {
return hijoIzquierdo;
}
public void setHijoIzquierdo(ArbolBinarioNumerico hijo) {
if(!(esta(hijo.getDato()))){
this.hijoIzquierdo = hijo;
hijoIzquierdo.setPadre(this);
}
}
public void setHijoIzquierdo(int dato) {
ArbolBinarioNumerico aux=new ArbolBinarioNumerico(dato);
if(!(esta(aux.getDato()))){
this.hijoIzquierdo = aux;
hijoIzquierdo.setPadre(this);
}
}
public int getDato() {
return dato;
}
public void setDato(int dat) {
dato = dat;
}
public boolean esHoja(){
if ((hijoDerecho==null)&&(hijoIzquierdo==null)){
return true;
}else {return false;
}
}
public int padre(){
ArbolBinarioNumerico aux=null;
if (super.getClass()==ArbolBinarioNumerico.class){
try {
aux = (ArbolBinarioNumerico) super.clone();
} catch (CloneNotSupportedException ex) {
Logger.getLogger(ArbolBinarioNumerico.class.getName()).log(Level.SEVERE, null, ex);
}
return aux.getDato();
}
return -1;
}
public int altura(){
int iz=0;
int de=0;
if(esHoja()){
return 1;
}else{
if (getHijoIzquierdo()!=null) iz=getHijoIzquierdo().altura();
if (getHijoDerecho()!=null) de=getHijoDerecho().altura();
if((iz>=de)&&(getHijoIzquierdo()!=null)){
return (1+getHijoIzquierdo().altura());
}else{
if((de>=iz)&&(getHijoDerecho()!=null)){
return (1+getHijoDerecho().altura());
}else{
return 0;
}
}
}
}
public int cantNodos(){
int aux1=0,aux2=0;
if (esHoja()){
return 1;
}else{
if(getHijoIzquierdo()!=null) aux1=getHijoIzquierdo().cantNodos();
if(getHijoDerecho()!=null) aux2=getHijoDerecho().cantNodos();
return(1+aux1+aux2);
}
}
public void dispose(){
getHijoDerecho().dispose();
getHijoIzquierdo().dispose();
dispose();
}
public ArbolBinarioNumerico getPadre(){
return padre;
}
public void setPadre(ArbolBinarioNumerico p){
padre=p;
}
public int profundidad(){
if (getPadre()!=null){
return 1+getPadre().profundidad();
}else{
return 0;
}
}
public int aridad(){
int iz=0;
int de=0;
if (!this.esHoja()) {
if(this.getHijoIzquierdo()!=null){
iz=getHijoIzquierdo().aridad();
}
//System.out.println(dato);
if(this.getHijoDerecho()!=null){
de=this.getHijoDerecho().aridad();
}
}else{
return 1;
}
return iz+de;
}
public void caminos(ListaInt aux){
if(esHoja()){
aux.insert(getDato());
System.out.println("Camino");
aux.imprimirLista();
aux.delete(getDato());
}else{
aux.insert(getDato());
if(getHijoIzquierdo()!=null){
getHijoIzquierdo().caminos(aux);
}
if(getHijoDerecho()!=null){
getHijoDerecho().caminos(aux);
}
aux.delete(getDato());
}
}
public boolean camListaIgual(ListaInt lista){
if((lista==null)||(lista.esVacia())){
return false;
}else{
if(getDato()==lista.first()){
if (esHoja()){
if(lista.size()==1){
return true;
}else{
return false;
}
}else{
lista.delete(lista.first());
if ((getHijoIzquierdo()!=null)&&(getHijoDerecho()!=null)){
return getHijoIzquierdo().camListaIgual(lista)||getHijoDerecho().camListaIgual(lista);
}else{
if (getHijoIzquierdo()==null){
return getHijoDerecho().camListaIgual(lista);
}else{
return getHijoIzquierdo().camListaIgual(lista);
}
}
}
}else{
return false;
}
}
}
public boolean esta(int valor){
if(getDato()==valor){
return true;
}else{
if(esHoja()){
return false;
}else{
if((getHijoIzquierdo()!=null)&&(getHijoDerecho()!=null)){
return getHijoIzquierdo().esta(valor)||getHijoDerecho().esta(valor);
}else{
if(getHijoIzquierdo()!=null){
return getHijoIzquierdo().esta(valor);
}else{
return getHijoDerecho().esta(valor);
}
}
}
}
}
Implementación en C
Un árbol binario puede declararse de varias maneras. Algunas de ellas son:
Estructura con manejo de memoria dinámica:
typedef struct tArbol
{
int clave;
struct tArbol *hIzquierdo, *hDerecho;
} tArbol;
Estructura con arreglo indexado:
typedef struct tArbol
{
int clave;
int hIzquierdo, hDerecho;
};
tArbol árbol[NUMERO_DE_NODOS];
En el caso de un árbol binario casi-completo (o un árbol completo), puede utilizarse un sencillo arreglo de enteros con tantas posiciones como nodos deba tener el árbol. La información de la ubicación del nodo en el árbol es implícita a cada posición del arreglo. Así, si un nodo está en la posición i, sus hijos se encuentran en las posiciones 2i+1 y 2i+2, mientras que su padre (si tiene), se encuentra en la posición truncamiento((i-1)/2) (suponiendo que la raíz está en la posición cero). Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia, particularmente durante un recorrido en preorden. La estructura para este caso sería por tanto:
int árbol[NUMERO_DE_NODOS];
Recorridos sobre árboles binarios
Recorridos en profundidad
el método de este recorrido es tratar de encontrar de la cabecera a la raíz en nodo de unidad binaria
Especificación en Maude de los recorridos preorden,inorden,postorden
Especificaremos antes en Maude las operaciones de recorrido en preorden, inorden y postorden:
fmod ÁRBOL-BIN-REC-PROF{X::TRIV} is
protecting ÁRBOL-BINARIO{X}.
protecting LISTA-GENERICA{X}.
protecting INT.
***selectores
ops preOrden inOrden posOrden:ArbolB{X}->ListaGen{X}.
***variables
var R:X$Elt.
vars ID:ArbolB{X}.
***ecuaciones
eq preOrden(crear)=crear.
eq preOrden(arbolBinario(R,I,D))=cons(R,preOrden(I))::preOrden(D).
eq inOrden(crear)=crear.
eq inOrden(arbolBinario(R,I,D))=inOrden(I)::cons(R,inOrden(D)).
eq posOrden(crear)=crear.
eq posOrden(arbolBinario(R,I,D))=posOrden(I)::posOrden(D)::cons(R,crear).
endfm
Ahora pasamos a ver la implementación de los distintos recorridos:
Recorrido en preorden
En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.
void preorden(tArbol *a)
{
if (a != NULL) {
tratar(a); //Realiza una operación en nodo
preorden(a->hIzquierdo);
preorden(a->hDerecho);
}
}
Implementación en pseudocódigo de forma iterativa:
push(s,NULL); //insertamos en una pila (stack) el valor NULL, para asegurarnos de que esté vacía
push(s,raíz); //insertamos el nodo raíz
MIENTRAS (s <> NULL) HACER
p = pop(s); //sacamos un elemento de la pila
tratar(p); //realizamos operaciones sobre el nodo p
SI (I(p) <> NULL) //preguntamos si p tiene árbol derecho
ENTONCES push(s,D(p));
FIN-SI
SI (D(p) <> NULL) //preguntamos si p tiene árbol izquierdo
ENTONCES push(s,I(p));
FIN-SI
FIN-MIENTRAS
En Java:
public void preOrden(){
if (!esHoja()){
System.out.println(dato);
if(getHijoIzquierdo()!=null){
getHijoIzquierdo().preOrden();
}
if (getHijoDerecho()!=null){
getHijoDerecho().postOrden();
}
}else{
System.out.println(dato);
}
}
Recorrido en postorden
En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.
void postorden(tArbol *a)
{
if (a != NULL) {
postorden(a->hIzquiedo);
postorden(a->hDerecho);
tratar(a); //Realiza una operación en nodo
}
}
en Java:
public void postOrden(){
if(!esHoja()){
if (getHijoIzquierdo()!=null){
getHijoIzquierdo().postOrden();
}
if (getHijoDerecho()!=null){
getHijoDerecho().postOrden();
}
System.out.println(dato);
}else{
System.out.println(dato);
}
}
Recorrido en inorden
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4 y 9.
Pseudocódigo:
funcion inorden(nodo)
inicio
si(existe(nodo))
inicio
inorden(hijo_izquierdo(nodo));
tratar(nodo); //Realiza una operación en nodo
inorden(hijo_derecho(nodo));
fin;
fin;
Implementación en C:
void inorden(tArbol *a)
{
if (a != NULL) {
inorden(a->hIzquierdo);
tratar(a); //Realiza una operación en nodo
inorden(a->hDerecho);
}
}
en Java:
public void inorden(){
if (!this.esHoja()) {
if(this.getHijoIzquierdo()!=null){
this.getHijoIzquierdo().inorden();
}
System.out.print(dato);
if(this.getHijoDerecho()!=null){
this.getHijoDerecho().inorden();
}
}else{
System.out.print(dato);
}
}
Recorridos en amplitud (o por niveles)
En este caso el recorrido se realiza en orden por los distintos niveles del árbol. Así, se comenzaría tratando el nivel 1, que sólo contiene el nodo raíz, seguidamente el nivel 2, el 3 y así sucesivamente. En el árbol de la figura el recorrido en amplitud sería: 2, 7, 5, 2, 6, 9, 5, 11 y 4.
Al contrario que en los métodos de recorrido en profundidad, el recorrido por niveles no es de naturaleza recursiva. Por ello, se debe utilizar una cola para recordar los subárboles izquierdos y derecho de cada nodo.
Pseudocódigo:
encolar(raiz);
mientras(cola_no_vacia())
inicio
nodo=desencolar(); //Saca un nodo de la cola
visitar(nodo); //Realiza una operación en nodo
encolar_nodos_hijos(nodo); //Mete en la cola los hijos del nodo actual
fin;
Implementación en C:
void amplitud(tArbol *a)
{
tCola cola;
tArbol *aux;
if (a != NULL) {
crearCola(cola);
encolar(cola, a);
while (!colavacia(cola)) {
desencolar(cola, aux);
visitar(aux); //Realiza una operación en nodo
if (aux->hIzquierdo != NULL) encolar(cola, aux->hIzquierdo );
if (aux->hDerecho!= NULL) encolar(cola, aux->hDerecho);
}
}
}
Implementación en Java:
public void amplitud(NodoArbol a) //SE RECIBE LA RAÍZ DEL ÁRBOL
{
Cola cola, colaAux; //DEFINICIÓN DE 2 VARIABLES DE TIPO COLA
NodoArbol aux; //DEFINICIÓN AUX DE TIPO NODOARBOL
if (a != null) //SI EL ÁRBOL CONTIENE NODOS...
{
cola=new Cola(); //SE INSTANCIA EL OBJETO COLA
colaAux=new Cola(); //SE INSTANCIA EL OBJETO COLAAUX
cola.push(a); //SE INSERTA EL NODOARBOL "A" (RAÍZ) COMO PRIMER NODO EN LA COLA
while (cola.colavacia()!=1) //MIENTRAS HAYAN ELEMENTOS EN LA COLA...
{
colaAux.push(aux=cola.pop()); /*EL ELEMENTO EXTRAÍDO DE LA COLA PRINCIPAL ES ASIGNADO
A AUX Y A SU VEZ INSERTADO EN LA COLA AUXILIAR*/
if (aux.izq != null) //SI EL HIJO IZQUIERDO DEL NODO ACTUAL EXISTE
{
cola.push(aux.izq); //SE INSERTA ESE HIJO COMO ELEMENTO SIGUIENTE EN LA COLA
}
if (aux.der!= null) //SI EL HIJO DERECHO DEL NODO ACTUAL EXISTE
{
cola.push(aux.der); //SE INSERTA ESE HIJO COMO ELEMENTO SIGUIENTE EN LA COLA
}
}
colaAux.print(); //POR ÚLTIMO SE IMPRIME LA COLA AUXILIAR
}
}
NOTA: Para hacer un recorrido en anchura, la idea es ir guardando en una cola los hijos del nodo que se están visitando y el siguiente a visitar es el próximo nodo de la cola.
Métodos para almacenar árboles binarios
Los árboles binarios pueden ser construidos a partir de lenguajes de programación de varias formas. En un lenguaje con registros y referencias, los árboles binarios son construidos típicamente con una estructura de nodos y punteros en la cual se almacenan datos, cada uno de estos nodos tiene una referencia o puntero a un nodo izquierdo y a un nodo derecho denominados hijos. En ocasiones, también contiene un puntero a un único nodo. Si un nodo tiene menos de dos hijos, algunos de los punteros de los hijos pueden ser definidos como nulos para indicar que no dispone de dicho nodo. En la figura adjunta se puede observar la estructura de dicha implementación.
Los árboles binarios también pueden ser almacenados como una estructura de datos implícita en arreglos, y si el árbol es un árbol binario completo, este método no desaprovecha el espacio en memoria. Tomaremos como notación la siguiente: si un nodo tiene un índice i, sus hijos se encuentran en índices 2i + 1 y 2i + 2, mientras que sus padres (si los tiene) se encuentra en el índiceArchivo:Inidice.JPG(partiendo de que la raíz tenga índice cero). Este método tiene como ventajas el tener almacenados los datos de forma más compacta y por tener una forma más rápida y eficiente de localizar los datos en particular durante un preoden transversal. Sin embargo, desperdicia mucho espacio en memoria.
Codificación de árboles n-arios como árboles binarios
Hay un mapeo uno a uno entre los árboles generales y árboles binarios, el cual en particular es usado en Lisp para representar árboles generales como árboles binarios. Cada nodo N ordenado en el árbol corresponde a un nodo N 'en el árbol binario; el hijo de la izquierda de N’ es el nodo correspondiente al primer hijo de N, y el hijo derecho de N' es el nodo correspondiente al siguiente hermano de N, es decir, el próximo nodo en orden entre los hijos de los padres de N.
Esta representación como árbol binario de un árbol general, se conoce a veces como un árbol binario primer hijo/siguiente hermano, o un árbol doblemente encadenado.
Una manera de pensar acerca de esto es que los hijos de cada nodo estén en una lista enlazada, encadenados junto con el campo derecho, y el nodo sólo tiene un puntero al comienzo o la cabeza de esta lista, a través de su campo izquierdo.
Por ejemplo, en el árbol de la izquierda, la A tiene 6 hijos (B, C, D, E, F, G). Puede ser convertido en el árbol binario de la derecha.
Un ejemplo de transformar el árbol n-ario a un árbol binario Cómo pasar de árboles n-arios a árboles FLOFO.
El árbol binario puede ser pensado como el árbol original inclinado hacia los lados, con los bordes negros izquierdos representando el primer hijo y los azules representado los siguientes hermanos.
Las hojas del árbol de la izquierda serían escritas en Lisp como:
(((M N) H I) C D ((O) (P)) F (L))
Que se ejecutará en la memoria como el árbol binario de la derecha, sin ningún tipo de letras en aquellos nodos que tienen un hijo izquierdo.