ARBOL BINARIO DE BUSQUEDA 40

Vista previa del material en texto

ÁRBOL BINARIO DE BÚSQUEDA
Dado un nodo, las claves de todos los nodos de su subárbol izquierdo son menores que la clave de ese nodo, mientras que las claves de todos los nodos de su subárbol derecho son mayores.
ÁRBOL BINARIO DE BÚSQUEDA
Clase Nodo:
ÁRBOL BINARIO DE BÚSQUEDA
class Nodo{
Nodo hizq, hder;
int clave;
int dato;
public Nodo()
{hizq=null; hder=null;
 clave=0; dato=0;}
public Nodo(int vc, int vd)
{hizq=null; hder=null;
 clave=vc; dato=vd;}
	hizq	clave	dato	hder
		10	x	
raiz
ÁRBOL BINARIO DE BÚSQUEDA
	hizq	clave	dato	hder
				
30
4
200
400
null
55
100
null
75
300
null
41
500
null
null
85
600
null
null
CLASE ÁRBOL
	Arbol
	raiz
	Constructor por defecto
inicializar()
arbolVacio()
insertar(c,d)
eliminar(cx)
CLASE ÁRBOL
public class arbol 
{ // Campos
 Nodo raiz;
// Constructor por defecto
public arbol() 
{raiz=null; }
// Inicializar
public void inicializar() 
{raiz=null; }
// Verificar si el árbol está vacío
public boolean arbolvacio() 
 { return raiz == null; }
CLASE ÁRBOL
// Insertar, como nodo hoja
public void insertar(int c, int d) 
{Nodo nuevo=new Nodo(c,d);
if(arbolvacio()) {	raiz=nuevo; }
else { Nodo p=raiz, q=null;
 while(p!=null) { q=p;
	 if(p.clave>c) { p=p.hizq; }
	 else {p=p.hder; }
			}
if(q.clave>c) { q.hizq=nuevo; }
else { q.hder=nuevo; }
}
}
raiz
INSERTAR COMO NODO HOJA
	hizq	clave	dato	hder
	null	35	d	null
30
4
200
400
null
55
100
null
75
300
null
41
500
null
null
85
600
null
null
null
nuevo
q
p
p
p
q
q
CLASE ÁRBOL
// Eliminar un nodo con una clave dada
public void eliminar(int cx) 
{ // se busca el nodo a eliminar (con clave cx)
 Nodo p, q;
 q=null; p=raiz;
 while(p!=null && p.clave!=cx) { q=p;
 	 if(p.clave>cx) { p=p.hizq; }
	 else { p=p.hder; }
	 }
 // se elimina el nodo
 if(p==null) System.out.print("Nodo no localizado");
 else { if(p==raiz) { // se elimina el nodo raiz
 raiz=conecta(raiz); }
 else if(q.hder==p) { // se elimina nodo hijo derecho
 q.hder=conecta(q.hder); }
 else { // se elimina nodo hijo izquierdo
 q.hizq=conecta(q.hizq); }
}
CLASE ÁRBOL
public Nodo conecta(Nodo a) 
{ Nodo b=a;
 if(a.hder==null && a.hizq==null) { // Nodo sin hijos 
	 a=null;}
 else if(a.hder==null ) { // Nodo sin hijo derecho
	 a=b.hizq;}
	else if(a.hizq==null ) { // Nodo sin hijo izquierdo 
	 a=b.hder;}
	 else {// Nodo con 2 hijos, su subárbol izquierdo se
 // inserta en la 1ra rama del subárbol derecho
 a=b.hder;
	 Nodo q=null,p=a;
	 while(p!=null) {q=p;
	 p=p.hizq;}
 	 q.hizq=b.hizq;
	 }
 return a;
 }
}
CLASE OPERACIONES
	Operaciones
	
	insertarN(A)
preorden(p)
simetrico(p)
posorden(p)
buscar(A,cb)
CLASE Operaciones
public class Operaciones { 
// Insertar N nodos
public arbol insertarN(arbol a) 
{ System.out.println("No de nodos=");
 int nn=Leer.datoInt();
 for(int i=1;i<=nn;++i) {
 System.out.println("Nodo"+i+":");
 System.out.println("clave");
 int c=Leer.datoInt();
 System.out.println("Dato");
 int d=Leer.dato();
 a.insertar(c,d);
 }
 return a;
}
CLASE Operaciones
// Recorrido en orden previo
public void preorden( Nodo p)
{ if(p!=null) { // Visitar el nodo raíz
		 System.out.println(p.dato);
		 // Visitar el subárbol izquierdo
		 preorden(p.hizq);
		 // Visitar el subárbol derecho
		 preorden(p.hder);
 }
 }
CLASE Operaciones
// Recorrido en orden simétrico
public void simetrico( Nodo p)
{ if(p!=null) { // Visitar el subárbol izquierdo
		 simetrico(p.hizq);
		 // Visitar el nodo raíz
		 System.out.println(p.dato);
		 // Visitar el subárbol derecho
		 simetrico(p.hder);
 }
 }
CLASE Operaciones
// Recorrido en orden posterior
public void posorden( Nodo p)
{ if(p!=null) { // Visitar el subárbol izquierdo
		 posorden(p.hizq);
		 // Visitar el subárbol derecho
		 posorden(p.hder);
		 // Visitar el nodo raíz
		 System.out.println(p.dato);
 }
 }
CLASE Operaciones
// Buscar un nodo, dada su clave
public void buscar(arbol a,int cb)
{ Nodo p=a.raiz;
 while((p!=null)&&(p.clave!=cb)) {
 if(p.clave>cb) { p=p.hizq; }
 else { p=p.hder; }
 }
 if(p==null) { System.out.println("NO LOCALIZADO");}
 else { System.out.println(p.dato); }
 }
}
CLASE Principal
public class Principal {
public static void main(String[] args)
{	Operaciones op=new Operaciones();
	Arbol A=new Arbol();
	A=op.insertarN(A);
	System.out.println("PRE-ORDEN");
	op.preorden(A.raiz);
	System.out.println("SIMETRICO");
	op.simetrico(A.raiz);
	System.out.println("POS-ORDEN");
	op.posorden(A.raiz);
	System.out.println("BUSCAR CLAVE");
	System.out.println("ingrese clave:");
	int cb=Leer.datoInt();
	op.buscar(A, cb);
 System.out.println("clave del nodo a eliminar:");
	int cb=Leer.datoInt();
	A.eliminar(cb);
 op.preorden(A.raiz);
 } }
GRACIAS