miércoles, 30 de enero de 2013

EJERCICIOS DE ARBOLES EN JAVA


int dato;
NodoBinario Hizq, Hder;
//Constructores
NodoBinario (int Elem){
dato = Elem;
NodoBinario Hizq, Hder = null;
} import java.io.*;
class NodoBinario{

//Insercion de un elemento
public void InsertaBinario (int Elem){
if(Elem < dato){
if (Hizq == null)
Hizq = new NodoBinario(Elem);
else
Hizq.InsertaBinario(Elem);
}
else{
if (Elem > dato){
if (Hder == null)
Hder = new NodoBinario (Elem);
else
Hder.InsertaBinario(Elem);
}
}
}
}
//Definicion de la clase Arbol
class Arbol{
Cola Cola = new Cola();
NodoBinario Padre;
NodoBinario Raiz;
//Constructor
public Arbol(){
Raiz = null;
}
//Insercion de un elemento en el arbol
public void InsertaNodo(int Elem){
if(Raiz == null)
Raiz = new NodoBinario (Elem);
else
Raiz.InsertaBinario (Elem);
}
//Preorden Recursivo del arbol
public void Preorden (NodoBinario Nodo){
if(Nodo == null)
return;
else{
System.out.print (Nodo.dato + ” “);
Preorden (Nodo.Hizq);
Preorden (Nodo.Hder);
}
}
//PostOrden recursivo del arbol
public void PostOrden (NodoBinario Nodo){
if(Nodo == null)
return;
else{
PostOrden (Nodo.Hizq);
PostOrden (Nodo.Hder);
System.out.print (Nodo.dato + ” “);
}
}
//Inorden Recursivo del arbol
public void Inorden (NodoBinario Nodo){
if(Nodo == null)
return;
else{
Inorden (Nodo.Hizq);
System.out.print(Nodo.dato + ” “);
Inorden (Nodo.Hder);
}
}
//Busca un elemento en el arbol
void Busqueda (int Elem, NodoBinario A){
if((A == null) | (A.dato == Elem)){
System.out.print(A.dato + ” “);
return;
}
else{
if(Elem>A.dato)
Busqueda (Elem, A.Hder);
else
Busqueda ( Elem, A.Hizq);
}
}
//Altura del arbol
public int Altura (NodoBinario Nodo){
int Altder = (Nodo.Hder == null? 0:1 + Altura (Nodo.Hder));
int Altizq = (Nodo.Hizq == null? 0:1 + Altura (Nodo.Hizq));
return Math.max(Altder,Altizq);
}
//Recorrido en anchura del arbol
public void Anchura (NodoBinario Nodo){
Cola cola= new Cola();
NodoBinario T = null;
//System.out.print (“El recorrido en Anchura es: “);
if(Nodo != null){
cola.InsertaFinal (Nodo);
while(!(cola.VaciaLista ())){
T = cola.PrimerNodo.datos;
cola.EliminaInicio();
System.out.print(T.dato + ” “);
if (T.Hizq != null)
cola.InsertaFinal (T.Hizq);
if (T.Hder != null)
cola.InsertaFinal (T.Hder);
}
}
System.out.println();
}
}
//Definición de la Clase NodoLista
class NodosListaA{
NodoBinario datos;
NodosListaA siguiente;
//Construtor  Crea un nodo del tipo Object
NodosListaA (NodoBinario  valor){
datos =valor;
siguiente = null;  //siguiente con valor de nulo
}
// Constructor Crea un nodo del Tipo Object y al siguiente nodo de la lista
NodosListaA (NodoBinario valor, NodosListaA signodo){
datos = valor;
siguiente = signodo; //siguiente se refiere al siguiente nodo
}
}
//Definición de la Clase Lista
class Cola{
NodosListaA PrimerNodo;
NodosListaA UltimoNodo;
String Nombre;
//Constructor construye una lista vacia con un nombre de List
public Cola(){
this (“Lista”);
}
//Constructor
public Cola (String s){
Nombre = s;
PrimerNodo = UltimoNodo =null;
}
//Retorna True si Lista Vacía
public boolean VaciaLista() {
return PrimerNodo == null;
}
//Inserta un Elemento al Frente de la Lista
public void InsertaInicio (NodoBinario ElemInser){
if(VaciaLista())
PrimerNodo = UltimoNodo = new NodosListaA (ElemInser);
else
PrimerNodo = new NodosListaA (ElemInser, PrimerNodo);
}
//Inserta al Final de la Lista
public void InsertaFinal(NodoBinario ElemInser){
if(VaciaLista())
PrimerNodo = UltimoNodo = new NodosListaA (ElemInser);
else
UltimoNodo=UltimoNodo.siguiente =new NodosListaA (ElemInser);
}
//Eliminar al Inicio
public void EliminaInicio(){
if(VaciaLista())
System.out.println (“No hay elementos”);
// Restablecer  las referencias de PrimerNodo y UltimoNodo
if(PrimerNodo.equals (UltimoNodo))
PrimerNodo = UltimoNodo = null;
else
PrimerNodo = PrimerNodo.siguiente;
}
//Elimina al final
public void EliminaFinal (){
if(VaciaLista())
System.out.println (“No hay elementos”);
// Restablecer  las referencias de PrimerNodo y UltimoNodo
if (PrimerNodo.equals (UltimoNodo))
PrimerNodo = UltimoNodo = null;
else{
NodosListaA Actual =PrimerNodo;
while (Actual.siguiente != UltimoNodo)
Actual = Actual.siguiente;
UltimoNodo =Actual;
Actual.siguiente = null;
}
}
}
public class ArbolBinario{
public static void main (String[]args)throws IOException
{
BufferedReader entrada =new BufferedReader(new InputStreamReader(System.in));
//creando objeto del arbolito xD
Arbol A = new Arbol();
int b;
for(int j=0;j<6;j++)
{
System.out.println(“Ingresa Datos “);
b=Integer.parseInt(entrada.readLine());
A.InsertaNodo (b);
}
System.out.print(” Preorden es: “);
A.Preorden (A.Raiz);
System.out.println();
System.out.print(” Inorden es: “);
A.Inorden (A.Raiz);
System.out.println();
System.out.print(” Postorden es: “);
A.PostOrden (A.Raiz);
System.out.println();
System.out.println(“La altura del arbol es: ” + A.Altura (A.Raiz));
A.Anchura (A.Raiz)                   





2 Siguiente             
import java.util.Stack; // importamos la clase Stack

public class a
 
{
public static void main (String[] args)
 
{
Stack Pila = new Stack(); // creamos la pila

Pila.push("Hola"); // agregamos la cadena "Hola" al final de la pila

System.out.println(Pila); // mostramos la pila
}
}
-----------------------------

Ahora uno mas complejo:

import java.util.Stack; // importamos la clase Stack

public class a
 
{
public static void main (String[] args)
 
{
Stack Pila = new Stack(); // creamos la pila

Pila.push("Hola"); // agregamos la cadena "Hola" al final de la pila
Pila.push("como"); // agregamos la cadena "como" al final de la pilav
Pila.push("estas"); // agregamos la cadena "estas" al final de la pila
Pila.push("tu"); // agregamos la cadena "tu" al final de la pila
Pila.push("?"); // agregamos la cadena "?" al final de la pila

Object A = Pila.get(2); // el objeto A recibe la cadena que se encuentra en la posicion 2 de la pila, osea "estas"

System.out.println(A); // mostramos el objeto A
 

//-----------------------------------
if(Pila.contains("tu"))
{
System.out.println("La pila si contiene la cadena tu");
}
 
else
{
System.out.println("La pila no contiene la cadena tu");
}

//-----------------------------------
System.out.println(Pila.size()); // imprime el tamaño de la pila

Pila.pop(); // Eliminamos el ultimo objeto de la pila, osea "?"

System.out.println(Pila); // Muestra la pila, ya no deberia tener el elemento "?"

//-----------------------------------
Pila.clear(); // borra todos los elementos de la pila

if(Pila.isEmpty()) // comprueba si la pila esta vacia
{
System.out.println("La pila esta vacia");
}
 
else
{
System.out.println("La pila no esta vacia");
}
}
}
//--------------------

Copia el codigo al JCreator por que aqui no se visualiza bien..
Si tienes problemas avisas....a y con las colas y listas no hay mucha diferencia, se usan practicamente los mismos metodos que te mencione antes, solo que para las listas en ves de crear un objeto de la clase Stack creas un objeto de la clase LinkedList y para las colas la clase Queue.

Pila clase Stack
Cola clase Queue
Lista clase LinkedList
Fuente(s):
yo mismo
ercicio









3 ejercicio

Clase Nodo

1
2
3
4
5
6
7
8
9
10
11
12
class nodo
{
    int dato;
    nodo der;
    nodo izq;
    nodo(int dat)
    {
        this.dato=dat;
        this.der=null;
        this.izq=null;
    }
}

Clase Arbol

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
public class arbol
{
    nodo raiz=null;
    public boolean tieneraiz()
    {
        if(raiz==null) return false;
        else return true;
    }

    public arbol alta(int dat)
    {
        if(!tieneraiz())
        {
            nodo nuevo=new nodo(dat);
            raiz=nuevo;
        }
        else
        {
            boolean izq;
            nodo actual=raiz;
            while(true)
            {
                if(actual.dato<dat) izq=false;
                else izq=true;
                if(!izq)
                {
                    if(actual.der==null)
                    {
                        nodo nuevo=new nodo(dat);
                        actual.der=nuevo;
                        break;
                    }
                    else actual=actual.der;
                }
                else
                {
                    if(actual.izq==null)
                    {
                        nodo nuevo=new nodo(dat);
                        actual.izq=nuevo;
                        break;
                    }
                    else actual=actual.izq;
                }
            }
        }return this;
    }

    public boolean baja(int dat)
    {
        nodo actual=raiz, anterior=raiz, temp;
        while(true)
        {
            if(actual==null) break;
            if(actual.dato==dat) break;
            anterior=actual;
            if(actual.dato<dat) actual=actual.der;
            else actual=actual.der;
        }
        if(actual==null) return false;
        else
        {
            if(actual==raiz)
            {
                temp=actual.izq;
                raiz=raiz.der;
                anterior=raiz;
            }
            else
            if (anterior.der == actual)
            {
                temp=actual.izq;
                anterior=actual.der;
            }
            else
            {
             temp=actual.izq;
             anterior.der=actual.izq;
            }
            actual=new nodo();
            while(actual.izq!=null)
                actual=actual.izq;
            actual.izq=temp;
            return true;
        }
    }

    public void imprimirpreorden()
    {
        ayudantePreorden(raiz);
    }

    public void ayudantePreorden(nodo dat)
    {
        if(dat==null)
                return;
        System.out.printf("%d ",dat.dato);
        ayudantePreorden(dat.der);
        ayudantePreorden(dat.izq);
    }

    public void impririnorden(nodo dat)
    {
        if(dat!=null)
        {
            impririnorden(dat.izq);
            System.out.println(" "+dat.dato);
            impririnorden(dat.der);
        }
    }
}

Clase Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Main {

    
    public static void main(String[] args) {
        java.util.Scanner leer=new java.util.Scanner(System.in);
        arbol x=new arbol();
        int z;
        System.out.print("Ingrese el numero de Datos a capturar: ");
        z=leer.nextInt();
        for(int i=1; i<=z;i++){
        int m;
        System.out.println("Ingrese Dato "+i+":  ");m=leer.nextInt();
        x.alta(m);
        }
        System.out.println("Valores Capturados en PreOrden:");
     x.imprimirpreorden();
        int q;
        System.out.print("\nIngrese dato a borrar: ");q=leer.nextInt();
     x.baja(q);
        System.out.println("\nDespues de borrar el dato "+q+" :");
     x.imprimir();
    }

}











No hay comentarios:

Publicar un comentario en la entrada