| Árbol_General_C++ |
|
|
|
| Este programa tiene interfaz visual. Realiza las operaciones basicas de los árboles, empleando para elo listas y colas. |
//---------------------------------------------------------------------------
#ifndef NodoH
#define NodoH
template<class T>
class CNodo_Elemento
{
private:
T dato;
CNodo_Elemento<T> * siguiente;
public:
inline CNodo_Elemento();
inline CNodo_Elemento(T);
__property T PDato ={ read = dato, write = dato};
__property CNodo_Elemento<T> * PSiguiente ={ read = siguiente, write = siguiente};
};
template<class T>
CNodo_Elemento<T>::CNodo_Elemento(T x)
{
dato=x;
siguiente=NULL;
};
/*
________________________________________________________________________________ */
template<class T>
CNodo_Elemento<T>::CNodo_Elemento()
{
dato=0;
siguiente=NULL;
};
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
#ifndef ListaH
#define ListaH
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include "Nodo.h"
template<class T>
class CListaSE
{
private:
CNodo_Elemento<T>* cabeza;
int longitud;
public:
CListaSE();
CListaSE( CListaSE<T>*);
void Adicionar(T);
void Insertar( T,int);
void Eliminar(int);
int Buscar(T);
T Obtener(int);
// __property int PLongitud = { read = longitud, write = longitud };
__property int PLongitud = { read = longitud};
__property CNodo_Elemento<T>* PCabeza ={ read = cabeza, write = cabeza};
};
template<class T>
CListaSE<T>::CListaSE()
{
cabeza=NULL;
longitud=0;
}
template<class T>
CListaSE<T>::CListaSE(CListaSE<T> * ptr)
{
this->cabeza= ptr->cabeza;
this->longitud=ptr->longitud;
}
template<class T>
void CListaSE<T>::Adicionar(T x)
{
CNodo_Elemento<T>* nodo=new CNodo_Elemento<T>(x); // creo el nodo a adicionar
if(longitud==0)
{ //si no hay elementos en la lista
cabeza=nodo; //le asigno la direccion del nodo a adicionar
longitud++;
}
else
{
CNodo_Elemento<T>* cursor=cabeza; //creo un cursor para recorrer la lista
while(cursor->PSiguiente!=NULL) // miestras el cursor no llegue al fial
{
cursor=cursor->PSiguiente; // le asigno la direccion del siquiente del nodo al que apunta cursor
} //cursor sale con la direccion del siguiente del ultimo nodo de la lista NULL
cursor->PSiguiente=nodo; // le asigno la direccion del nodo a insertar.
longitud++; // incremento la logitud de la lista
}
}
template<class T>
void CListaSE<T>::Insertar(T x,int pos)
{
if(pos>=1 && pos<=longitud)
{
CNodo_Elemento<T>* nodo=new CNodo_Elemento<T>(x); //creo el nodo que voy a insertar y un cursor
if(pos==1) // si la posicion del nodo que voy a insertar es la primera
{
nodo->PSigiente=cabeza; // le asigno la direccion a la que apunta cabeza
cabeza=nodo; // a cabeza le asigno
longitud++;
}
else
{
CNodo_Elemento<T>*cursor=cabeza;
int pos_cur=1;
while(pos_cur + 1 < pos)
{
cursor=cursor->PSigiente;
pos_cur++;
}
nodo->PSigiente=cursor->PSigiente;
cursor->PSigiente=nodo;
longitud++;
}
}
else
{
Adicionar(x);
}
}
template<class T>
void CListaSE<T>::Eliminar(int pos)
{
if(pos>=1 && pos <=longitud)
{
CNodo_Elemento<T>* cursor=cabeza;
if(pos==1)
{
cabeza=cabeza->PSiguiente;
delete cursor;
}
else
{
CNodo_Elemento<T>* nodo_aux;
int pos_cur=1;
while(pos_cur +1 < pos) //mientras no llegue a la posicion antes del nodo a eliminar
{
cursor=cursor->PSiguiente; //le asigno el valor del puntero siguiente del nodo al que apunta cursor
pos_cur++; //incremento la posicion del cursor
} // cursor sale con la direccion del que se va a eliminar
nodo_aux=cursor->PSiguiente; //le asigno el valor del nodo que se va a eliminar
cursor->PSiguiente=nodo_aux->PSiguiente; // le asigno el valor de siguiente del nodo al que aputo nodo_aux
delete nodo_aux; //elimino el nodo
}
longitud--;
}
}
template<class T>
int CListaSE<T>::Buscar(T num)
{
if(longitud !=0)
{
CNodo_Elemento<T>* cursor=cabeza;
int pos_cur=1;
while (cursor!=NULL)
{
if(cursor->PDato==num)
{
return pos_cur;
}
else
{
cursor=cursor->PSiguiente;
pos_cur++;
}
}
return -1;
}
else
return -1;
}
template<class T>
T CListaSE<T>::Obtener(int pos)
{
if(pos>=1 && pos<=longitud)
{
if(pos==1)
{
return cabeza->PDato;
}
else
{
CNodo_Elemento<T>* cursor=cabeza;
int pos_cur=1;
while(pos_cur!=pos)
{
cursor=cursor->PSiguiente;
pos_cur++;
}
return cursor->PDato;
}
}
/*else
return -1; */
}
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
#ifndef ColaH
#define ColaH
#include "Nodo.h"
template <class T>
class Cola
{
private:
CNodo_Elemento<T>* frente;
CNodo_Elemento<T>* fondo;
int longitud;
public:
Cola();
Cola(int);
Cola(const Cola <T>&);
void Push(T);
bool Is_Empty();
T Frente();
T Fondo();
T Extraer();
~ Cola();
__property int PLongitud ={read = longitud ,write = longitud};
/*EJERCICIO 4 GUIA DE PII*/
bool Esta_en_Cola(T);
};
template<class T>
Cola<T>::Cola()
{
longitud=0;
frente=fondo=NULL;
}
template<class T>
void Cola<T>::Push(T elem)
{
CNodo_Elemento<T>* nodo=new CNodo_Elemento<T>(elem);
if(longitud==0)
{
frente=nodo;
fondo=nodo;
}
else
{
fondo->PSiguiente=nodo;
fondo=nodo;
}
longitud++;
}
template<class T>
bool Cola<T>::Is_Empty()
{
return (fondo==frente);
}
template<class T>
T Cola<T>::Frente()
{
if(longitud==0)
return NULL;
else
return frente->PDato;
}
template<class T>
T Cola<T>::Fondo()
{
if(longitud==0)
return NULL;
else
return fondo->PDato;
}
template<class T>
T Cola<T>::Extraer()
{
if(frente!=NULL)
{
CNodo_Elemento<T>* aux=frente;
frente=frente->PSiguiente;
T dato = aux->PDato;
delete aux;
longitud--;
return dato;
}
/*else
throw "ERROR"; */
}
template<class T>
Cola<T>::~Cola()
{
delete [] frente;
delete [] fondo;
}
/*EJERCICIO 4 GUIA DE PII*/
template<class T>
bool Cola<T>::Esta_en_Cola(T dato)
{
if(frente==fondo)
return false;
else
{
CNodo_Elemento<T>*aux=frente;
while(aux->PDato!=dato)
{
aux=aux->PSoguiente;
}
if(aux->PSiguiente==NULL)
return false;
else
return true;
}
}
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
#ifndef ArbolH
#define ArbolH
#include "Lista.h"
#include "Nodo.h"
#include "Cola.h"
template <class T>
class CArbol
{
private:
T *raiz;
CListaSE< CArbol<T>*>* hijos;
void Mi_Preorden(CArbol<T>*,CListaSE<T>*);
void Mi_PostOrden(CArbol<T>*,CListaSE<T>*);
void Mi_EntreOrden(CArbol<T>*,CListaSE<T>*);
void Mi_A_lo_Ancho(CListaSE<T>*,Cola<CArbol<T>*>*);
public:
CArbol();
CArbol(T);
CArbol(T*,CListaSE< CArbol<T>*>*);
CArbol(const CArbol<T>*);
int Grado();
bool Es_Hoja();
int Peso();
void Podar_Arbol(int );
CListaSE <T>* Pre_Orden();
CListaSE <T>* Post_Orden();
CListaSE <T>* Entre_Orden();
CListaSE <T>* A_lo_Ancho();
CArbol<T>* Padre(T raiz_x);
CArbol<T>* SubArbol(int);
//bool Adicionar_A(T,T);
void Adicionar(T);
__property T* PRaiz={read = raiz,write=raiz};
//CListaSE< CArbol<T>*>* Get_Hijos(){return hijos;}
__property CListaSE< CArbol<T>*>* PHijos ={read=hijos,write=hijos};
bool Buscar(T);
CArbol<T>*Obtener(T);
/*EJERCICIOS GUIA PROGRAMACION*/
void Eliminar_Hermanos_Himpares();
void Eliminar_Impares();
void Podar(int);
};
//______________________________________________________________________________
template<class T>
CArbol<T>::CArbol(T raiz_x)
{
raiz=new T(raiz_x);
hijos= new CListaSE<CArbol<T>* >();
}
template<class T>
CArbol<T>::CArbol()
{
raiz=new T();
hijos=new CListaSE <CArbol<T>*>();
}
template<class T>
CArbol<T>::CArbol(T * rai_x,CListaSE< CArbol<T>*>* hijo_x)
{
*raiz=*raiz_x;
hijos=CListaSE< CArbol<T>*>(*hijos_x);
}
template<class T>
CArbol<T>::CArbol(const CArbol<T>* arbol_x)
{
raiz=arbol_x->raiz;
hijos=arbol_x->hijos;
}
//__________________________RECORRIDOS__________________________________________
template <class T>
void CArbol<T>::Mi_Preorden(CArbol<T>* arbol,CListaSE<T>* L)
{
L->Adicionar(*(arbol->PRaiz));
for(int i=1;i<=arbol->hijos->PLongitud;i++)
{
Mi_Preorden(arbol->hijos->Obtener(i),L);
}
}
template <class T>
CListaSE <T>*CArbol<T>::Pre_Orden()
{
CListaSE<T>* lista=new CListaSE<T>();
Mi_Preorden(this,lista);
return lista;
}
/*
template <class T>
CListaSE <T>*CArbol<T>::Pre_Orden()
{
CListaSE <T>* lista=new CListaSE <T>();
lista->Adicionar(*(this->raiz));
if(this->Es_Hoja())
return lista;
else
{
CListaSE <T>*lista2;
for(int i=1;i<=this->hijos->PLongitud;i++)
{
lista2=(SubArbol(i)->Pre_Orden());
for(int j=1;j<=lista2->PLongitud;j++)
lista->Adiconar(lista2->Obtner(j));
}
return lista;
}
}
*/
template<class T>
void CArbol<T>:: Mi_PostOrden(CArbol<T>* arbol_x,CListaSE<T>* l)
{
for(int i=1;i<=arbol_x->hijos->PLongitud;i++)
Mi_PostOrden(arbol_x->hijos->Obtener(i),l);
l->Adicionar(*(arbol_x->PRaiz));
}
template<class T>
CListaSE <T>* CArbol<T>::Post_Orden()
{
CListaSE<T>* lista=new CListaSE<T>();
Mi_PostOrden(this,lista);
return lista;
}
template<class T>
void CArbol<T>::Mi_EntreOrden(CArbol<T>*arbol_x,CListaSE<T>*l)
{
if(arbol_x->Es_Hoja())
l->Adicionar(*(arbol_x->PRaiz));
else
{
Mi_EntreOrden(arbol_x->SubArbol(1),l);
l->Adicionar(*(arbol_x->PRaiz));
for(int i=2;i<=arbol_x->Grado();i++)
Mi_EntreOrden(arbol_x->SubArbol(i),l);
}
}
template<class T>
CListaSE <T>*CArbol<T>::Entre_Orden()
{
CListaSE<T>*lista=new CListaSE<T>();
Mi_EntreOrden(this,lista);
return lista;
}
template<class T>
void CArbol<T>::Mi_A_lo_Ancho(CListaSE<T>* lista,Cola<CArbol<T>*>* cola)
{
if(this!=NULL)
{
if(cola->PLongitud==0)
cola->Push(this);
for(int i=1;i<=cola->Frente()->Grado();i++)
cola->Push(cola->Frente()->PHijos->Obtener(i));
lista->Adicionar(*(cola->Extraer()->PRaiz));
for(int j=1;j<=Grado();j++)
PHijos->Obtener(j)->Mi_A_lo_Ancho(lista,cola);
}
}
template<class T>
CListaSE <T>* CArbol<T>::A_lo_Ancho()
{
CListaSE <T>* lista=new CListaSE<T>();
Cola<CArbol<T>*>*cola=new Cola<CArbol<T>*>();
Mi_A_lo_Ancho(lista,cola);
return lista;
}
//______________________________________________________________________________
template <class T>
int CArbol<T>::Grado()
{
return this->hijos->PLongitud;
}
template <class T>
bool CArbol<T>::Es_Hoja()
{
return this->hijos->PLongitud==0;
}
template <class T>
void CArbol<T>::Podar(int sub)
{
if(sub<=Grado())
this->PHijos->Eliminar(sub);
}
template <class T>
CArbol<T>* CArbol<T>::SubArbol(int pos)
{
return this->hijos->Obtener(pos);
}
template <class T>
int CArbol<T>::Peso()
{
if(hijos->PLongitud==0)
return 0; //Condicion inicial
else
{
int max=1+SubArbol(1)->Peso();
for(int i=2; i<=hijos->PLongitud;i++)
{
int peso=1+SubArbol(i)->Peso(); //llama recursiva
if(peso>max)
max=peso;
}
return max;
}
}
template <class T>
void CArbol<T>::Adicionar(T dato)
{
CArbol<T>* arbol=new CArbol<T>(dato);
hijos->Adicionar(arbol);
}
template <class T>
bool CArbol<T>::Buscar(T dato)
{
CListaSE<T>* lista=this->Pre_Orden();
for(int i=1;i<=lista->PLongitud;i++)
if(lista->Obtener(i)==dato)
return true;
return false;
}
template <class T>
CArbol<T>* CArbol<T>::Obtener(T dato)
{
if(this->Buscar(dato) && *this->PRaiz==dato)
return this;
else
{
if(this->Buscar(dato))
{
if(*this->PRaiz==dato && Es_Hoja() )
return this;
else
{ for(int i=1;i<=hijos->PLongitud;i++)
if(this->SubArbol(i)->Obtener(dato))
break;
}
}
}
}
/*MIO*/
/*template <class T>
CArbol<T>* CArbol<T>::Obtener(T dato)
{
if(this->Buscar(dato))
{
if(Es_Hoja() && *this->PRaiz==dato)
{
return this;
}
else
{
if(*this->PRaiz==dato && !Es_Hoja() )
return this;
else
{ for(int i=1;i<=hijos->PLongitud;i++)
if(this->SubArbol(i)->Obtener(dato))
break;
}
}
}
} */
/*alian*/
/*
template<class T>
CArbol<T>* CArbol<T>::Obtener(T dato)
{
if(this->Buscar(dato))
{
if((*this->PRaiz==dato) && (this->Es_Hoja()))
return this;
else
if(*this->PRaiz==dato && (!this->Es_Hoja()))
return this;
else
{
if(!this->Es_Hoja() && (*this->PRaiz!=dato))
{
for(int i=1;i<=this->Grado();i++)
{
if(this->SubArbol(i)->Obtener(dato)) //si obtengo un arbol no continuo el ciclo
break;
else //si no encuentro el arbol, continuo el ciclo
continue;
}
}
}
}
} */
template <class T>
void CArbol<T>::Eliminar_Hermanos_Himpares()
{
if(!Es_Hoja())
{ int i=1;
bool flag=true;
while(i<=Grado())
{
if(flag)
{
hijos->Eliminar(i);
flag=false;
}
else
{
flag=true;
i++;
}
}
}
}
template <class T>
void CArbol<T>::Eliminar_Impares()
{
if(!Es_Hoja())
{
Eliminar_Hermanos_Himpares();
for(int i=1;i<=Grado();i++)
hijos->Obtener(i)->Eliminar_Impares();
}
}
template <class T>
CArbol<T>* CArbol<T>::Padre(T raiz_x)
{
if(Buscar(raiz_x))
{
if(!this->Es_Hoja())
{
CListaSE<T>*ancho=this->A_lo_Ancho();
if(ancho->Buscar(raiz_x))
return this;
else
{
for(int i=1;i<=this->Grado();i++)
{
this->SubArbol(i)->Padre(raiz_x);
break;
}
}
}
}
}
//---------------------------------------------------------------------------
#endif
|
|
| |
| Terminos de Uso |
|
1 - Copiar o Descargarse este contenido implica aceptar los terminos aqui detallados.
2 - Usted puede utilizar este contenido en sus propios programas y puede compilarlo en un programa y modificarlo a su gusto.
3 - Usted NO PUEDE redistribuir este contenido tal como se presenta aqui sin el permiso del autor original del mismo.
4 - Usted seguirá cualquier restricción adicional del copyright que el autor pudo haber puesto en la descripción del contenido.
|
|
|
|
|
