PARBOL BINARIO DE BUSQUEDA 3

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)
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 OPERACIONES
	Operaciones
	suma, may
	insertarN(A)
preorden(p)
simetrico(p)
posorden(p)
buscar(A,cb)
promedio(A)
mayorPositivo(A)
CLASE Operaciones
public class Operaciones { 
int suma, may, c;
public Operaciones()
{ suma=0; may=-1; c=0;} 
// 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 Operaciones
// promedio
public void sumatoria( Nodo p)
{ if(p!=null) { // Visitar el nodo raíz
		 suma = suma + p.dato;
 ++c;
		 // Visitar el subárbol izquierdo
		 sumatoria(p.hizq);
		 // Visitar el subárbol derecho
		 sumatoria(p.hder);
 }
 }
public void promedio(arbol a)
{ sumatoria(a.raíz);
 double prom = (double)suma/c;
 System.out.println(“promedio=“+prom)
}
CLASE Operaciones
// mayor
public void mayor( Nodo p)
{ if(p!=null) { // Visitar el nodo raíz
		 if(p.dato>0 && p.dato>may) may=p.dato;
		 // Visitar el subárbol izquierdo
		 mayor(p.hizq);
		 // Visitar el subárbol derecho
		 mayor(p.hder);
 }
 }
public void mayorPositivo(arbol a)
{ mayor(a.raíz);
 if(may<0) System.out.println(“No hay positivos”);
 else System.out.println(“mayor positivo=“+may)
}
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);
	op.promedio(A);
 op.mayorPositivo(A);
 } }
GRACIAS