Se define un árbol binario como un conjunto finito de elementos (nodos) que bien esta vacío o esta formado por una raíz con dos arboles binarios disjuntos, es decir, dos descendientes directos llamados subarbol izquierdo y subarbol derecho.
Los árboles binarios (también llamados de grado 2 )tienen una especial importancia.
Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.
Arbol binario de búsqueda
Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subarbol izquierdo, y menor que todas las claves del subarbol derecho se dice que este árbol es un árbol binario de búsqueda.
/************************************
// clase NodoArbolBinario
//************************************
public class NodoArbolBinario {
private int info = 0;
private NodoArbolBinario derecho = null;
private NodoArbolBinario izquierdo = null;
public NodoArbolBinario ( int x ) {
this.info = x;
this.derecho = null;
this.izquierdo = null;
}
public NodoArbolBinario getDerecho(){
return this.derecho;
}
public void setDerecho(NodoArbolBinario derecho){
this.derecho = derecho;
}
public int getInfo(){
return this.info;
}
public void setInfo(int info){
this.info = info;
}
public NodoArbolBinario getIzquierdo(){
return this.izquierdo;
}
public void setIzquierdo(NodoArbolBinario izquierdo){
this.izquierdo = izquierdo;
}
}
//************************************
// clase ArbolBinario
//************************************
public class ArbolBinario {
private NodoArbolBinario raiz = null;
private NodoArbolBinario padre = null;
private boolean centinela = false, sw = false;
public ArbolBinario () {
}
public NodoArbolBinario adicionar( int x ) {
NodoArbolBinario p = new NodoArbolBinario ( x ), r = null;
if ( this.raiz == null ) {
this.raiz = p;
}
else {
NodoArbolBinario q = raiz;
while ( q != null ) {
r = q;
if ( x >= q.getInfo() ) {
q = q.getDerecho();
}
else {
q = q.getIzquierdo();
}
}
}
if ( x >= r.getInfo() ) {
r.setDerecho( p );
}
else {
r.setIzquierdo( p );
}
return p;
}
public ArbolBinario arbolSuma(ArbolBinario tree){
ArbolBinario res = new ArbolBinario();
arbolSuma(res,tree.raiz);
return res;
}
private int arbolSuma(ArbolBinario res, NodoArbolBinario p){
if ( p == null ){
return 0;
}
else {
int sum = p.getInfo();
NodoArbolBinario aux = res.adicionar(sum);
sum += arbolSuma(res, p.getIzquierdo() );
sum += arbolSuma(res, p.getDerecho() );
aux.setInfo(sum);
return sum;
}
}
}
No hay comentarios:
Publicar un comentario