Programa Recorrido Arbol

public class Test
{
public static void main(String args[])
  {
  CArbolBinarioDeBusqueda arbolbb=new CArbolBinarioDeBusqueda();
  String nombre;
  double nota;
  int i=0,cod;
  System.out.println("Introducir datos. Finalizar con Ctrl+z.");
  System.out.println("nombre: ");
  while((nombre=Leer.dato())!=null)
 {
  System.out.print("nota: ");
  nota=Leer.datoDouble();
  cod=arbolbb.insertar(new CDatos(nombre,nota));
  if(cod==CArbolBinarioDeBusqueda.YA_EXISTE)
  {
  CDatos datos=(CDatos)arbolbb.buscar(new CDatos(nombre,nota));
   if(nota>=0)
   datos.asignarNota(nota);
    else
   {
   if(arbolbb.borrar(new CDatos(nombre,nota))==null)
  System.out.println("nodo borrado porque no existe");
  else
  System.out.println("nodo borrado");
 }
  }
  System.out.print("nombre: ");
  }
   System.out.println("\n");
               
  System.out.println("\nArbolInorden: ");
 arbolbb.visitarInorden();
 System.out.println("\nArbol posorden: ");

 arbolbb.visitarPosorden();

 System.out.println("\nArbol preorden: ");

 arbolbb.visitarPreorden();
                }
}

SeudoCodigo Recorrido Arbol

 

Mapa Conceptual Arboles

Para ver imagen completa presione clic Aquí ...............

Arbol B+

Arbol B+

     Caracteristicas:

• Nodos internos solo contienen las claves o apuntadores
• Todas las hojas se encuentran al mismo nivel
• Nodos hojas se encuentran ligadas como una lista enlazada para permitir la busqueda mas eficiente 
• El minimo numero de Claves es 2

EJEMPLO:

Construir TB+[37,48,55,61,73,77,80,87,92]

Arbol B

Arbol B

   Caracteristicas:

•  Conserva las caracteristivas del arbol binario, AVL, ABB
  
• Se busca la clave a insertar
• Si no esta en el arbol se comienza a insertar
• ¿ Esta llena la Pagina?
• Se divide la pagina en 2 paginas el mismo nivel , extrayendo la clave media 
• Con esta medida se sube por el camino de busqueda y se comienza el proceso nuevamente

EJEMPLO: 

Construir el arbol B  TB=[55,77,37,48,61,73,80,87,87,92]

Recorridos

Preorden

void preorder (){
System.out.println(d);
if (izq != null)
izq.preorder();
if (der != null)
der.preorder();
}

Postorden

void postorder (){
if (izq != null)
izq.postorder();
if (der != null)
der postorder();
der.System.out.println(d);
}

Inorden

void inorder (){
if (izq != null)
izq.inorder();
System.out.println(d);
if (der != null)
der.inorder();
}

Algoritmo Basico

Algoritmo Basico

• Tamaño (número de nodos)
• Profundidad de un nodo
• Altura
• Recorridos
• Euler
• Pre-, in- y post-orden
• Suponemos árboles binarios para simplifica

Clase Nodo binario

Class NodoB {
Object d;
NodoB izq;
NodoB der;
NodoB() {this(null);}
NodoB(Object o) {this(o,null,null);}
NodoB(Object o, NodoB i, NodoB d)
{d=o; izq=i; der=d;}
static int size ( NodoB a){...;}
static int height (NodoB a){...;}
void preorder (NodoB a){...;}
void inorder (NodoB a){...;}
void postorder (NodoB a){...;}
}

Clase Árbol binario

protected NodoB raiz;
ArbolB() {raiz=null;}
ArbolB(Object o){raiz=new NodoB(o);}
public int size()
{return NodoB.size(raiz);}
public int height()
{return NodoB.height(raiz);}
public void preorder ()
p p {if (raiz!=null) raiz.preorder();}
public void inorder ()
{if (raiz!=null) raiz.inorder();}
public void postorder ()
{if (raiz!=null) raiz.postorder();}
}

 Tamaño

static int size (NodoB a){
if (a==null)
return 0;
else
return 1+size(a.izq)+size(a.der);
}

Altura

 
static int height (NodoB a){
if (a==null)
return (-1);
else
return 1+Math.max(height(a.izq),
height(a.der));
}

Estructuras Recursivas

ÁRBOLES

Árboles: Es un conjunto de nodos, en cada nodo hay información.

Características:

• Árbol vacio T = 0
• Raíz: se desprenden los subárboles.
• Longitud: cantidad de ramas o aristas desde la raíz hasta el nodo de referencia.
• Profundidad: niveles de árbol, desde la raíz hasta nodo más profundo.
• Grado: la cantidad de ramas en una sola raíz.
• Recorrido: ancho, preorden, inorden y postorden.
• Tamaño: el número de nodos que tiene el árbol.
• Árbol binario: es cuando el grado del árbol es 2.
• Árbol de busqueda: contiene un factor de equilibrio dado por la altura del hijo derecho menos (-) el hijo izquierdo. FE <= 1

Operaciones árboles

• Buscar
• Insertar
• Eliminar

"recorrido inorden es el que ordena un árbol"

"árbol de busqueda organizado AVAL"

"árbol degenerado: que queda todo hacia un solo lado"

IMPLEMENTACIÓN DE ÁRBOLES BINARIOS

• arreglo: estructura estática.
• como estructuras ligadas se debe definir el tamaño del arreglo y NUNCA cambiarlo.
• overflow: desborde de información.

Árboles multicaminos

• árboles B
• árboles B+

Características

• árboles binarios
• AVL
• ABB

1. Nodo padre: mínimo un elemento y max. de 2n
2. páginas intermedias, almacenar entre n (mínimo) y un max. de 2n.
3. Todas las hojas deben tener la misma altura.

ÁRBOL B+

características:

• Nodos internos solo contienen claves o apuntadores
• Todas las hojas se encuentran al mismo nivel
• Nodos hoja, se encuentran ligadas como una lista enlazada para permitir la busqueda más eficiente.
• El mínimo número de claves es 2.

operaciones:

• Buscar
• Insertar
• Eliminar