kruncher
29 de Mayo del 2008

Tengo la clase para tratar este árbol binario implementada (la pego aqui abajo), tengo que hacer una función recursiva para crear un árbol binario de expresiones a través de un string pero no lo consigo...
/******************************************/
Clase Arbol binario
/******************************************/
#include <iostream>
using namespace std;

#ifndef ARBIN
#define ARBIN

template <class T>
class arbin {
public:
//constructoras
//construye un arbol binario vacio
arbin();

//crea un nuevo arbol binario a partir de un elemento y dos arboles binarios
arbin(const T & e, const arbin<T> & ai=arbin(), const arbin<T> & ad=arbin());

//modifica un arbin poniendo e como raiz e izqdo y dcho como hijo izquierdo
// y derecho respectivamente
void modificar (const T & e, const arbin<T> & izqdo, const arbin<T> & dcho);

//modica el arbol actual hasta obtener el arbin vacio
void vaciar();

//Copia el arbol binario actual
arbin<T> copiar();

//Devuelve el subarbol izquierdo del árbol, NULL si está vacío
arbin<T> & izquierdo() const;

//Devuelve el subarbol derecho del árbol, NULL si está vacío
arbin<T> & derecho() const;

//Devuelve el elemento de la raiz
const T & datoraiz() const;
T & datoraiz() ;

//Indica si el árbol binario está vacio
bool esvacio () const;

//recorre el arbol en preorden
void preorden() const;

//muestra el arbol en notacion infija
void notacion_infija(char) const;

//muestra el arbol en notacion infija
void notacion_funcional() const;

//Comprueba que el arbin es extendido
bool esExtendido () const;

private:
//nodo del arbol binario
struct Nodo {
T info;
arbin<T> izq;
arbin<T> der;

//constructor
Nodo (T e=T(), arbin<T> iz=arbin(), arbin<T> de=arbin()) {
info=e;
izq=iz;
der=de;
}
//destructor
//~Nodo();
};

typedef Nodo * PNodo;
PNodo raiz; //puntero a la raiz del árbol binario

};

/******************************************/
Main.cpp - Lo que tengo hecho de momento es
/******************************************/
arbin <char> crear_arbol (char *s, int pos){
int tam = strlen (s);
int sig=0;

if (es_entero(s[pos]))
return arbin <char> (s[pos]);

// Al final del arbol binario siempre hay 2 enteros
//return arbin <char> (s[pos],crear_arbol(s,pos+1),crear_arbol(s,pos+2));
if (es_entero(s[pos+1]))
return arbin <char> (s[pos],crear_arbol(s,pos+1),crear_arbol(s,pos+2));
else {
int y=pos+2;
while ((es_entero(s[y])==false) && (y <= tam))
y++;
while ((es_entero(s[y])==true) && (y <= tam))
y++;
cout << "y: " << y;
return arbin <char> (s[pos],crear_arbol(s,pos+1),crear_arbol(s,y));
}
}


Me parece que tengo mal todo, no se como plantear la solución, alguna idea? gracias !

Creo que la cabezera correcta de la función deberia ser:
arbin <char> crear_arbol (char *s, int &pos){}

pero de momento así no he conseguido nada... Un saludo !

kruncher
29 de Mayo del 2008

/******************************************/
Clase Arbol binario COMPLETA
/******************************************/
#include <iostream>
using namespace std;

#ifndef ARBIN
#define ARBIN

template <class T>
class arbin {
public:
//constructoras
//construye un arbol binario vacio
arbin();

//crea un nuevo arbol binario a partir de un elemento y dos arboles binarios
arbin(const T & e, const arbin<T> & ai=arbin(), const arbin<T> & ad=arbin());

//modifica un arbin poniendo e como raiz e izqdo y dcho como hijo izquierdo
// y derecho respectivamente
void modificar (const T & e, const arbin<T> & izqdo, const arbin<T> & dcho);

//modica el arbol actual hasta obtener el arbin vacio
void vaciar();

//Copia el arbol binario actual
arbin<T> copiar();

//Devuelve el subarbol izquierdo del árbol, NULL si está vacío
arbin<T> & izquierdo() const;

//Devuelve el subarbol derecho del árbol, NULL si está vacío
arbin<T> & derecho() const;

//Devuelve el elemento de la raiz
const T & datoraiz() const;
T & datoraiz() ;

//Indica si el árbol binario está vacio
bool esvacio () const;

//recorre el arbol en preorden
void preorden() const;

//muestra el arbol en notacion infija
void notacion_infija(char) const;

//muestra el arbol en notacion infija
void notacion_funcional() const;

//Comprueba que el arbin es extendido
bool esExtendido () const;

private:
//nodo del arbol binario
struct Nodo {
T info;
arbin<T> izq;
arbin<T> der;

//constructor
Nodo (T e=T(), arbin<T> iz=arbin(), arbin<T> de=arbin()) {
info=e;
izq=iz;
der=de;
}
//destructor
//~Nodo();
};

typedef Nodo * PNodo;
PNodo raiz; //puntero a la raiz del árbol binario

};

#endif

//IMPLEMENTACIONES
//construye un arbol binario vacio
template <class T>
arbin<T>::arbin() {
raiz=NULL;
}

//crea un nuevo arbol binario a partir de un elemento y dos arboles binarios
template <class T>
arbin<T>::arbin(const T & e, const arbin<T> & izqdo, const arbin<T> & decho) {
raiz= new Nodo(e, izqdo, decho);
}


//modifica un arbin poniendo e como raiz e izqdo y dcho como hijo izquierdo
// y derecho respectivamente
template <class T>
void arbin<T>::modificar (const T & e, const arbin<T> & izqdo, const arbin<T> & dcho) {
if (!esvacio()) {
raiz->info=e;
raiz->izq=izqdo;
raiz->der=dcho;
}
else cout << "Error: arbol binario vacio" << endl;
}


//modica el arbol actual hasta obtener el arbin vacio
template <class T>
void arbin<T>::vaciar() {
if (!esvacio()) {
izquierdo().vaciar();
derecho().vaciar();
delete raiz;
}
}


//Copia el arbol binario actual
template <class T>
arbin<T> arbin<T>::copiar() {
arbin i, d ;
if (!esvacio()) {
if (!izquierdo().esvacio()) i=izquierdo().copiar();
if (!derecho().esvacio()) d=derecho().copiar();
//raiz=new Nodo(raiz->info, i, d);
//return raiz;
arbin x (raiz->info, i, d);
return x;
}
}

//Devuelve el subarbol izquierdo del árbol, NULL si está vacío
template <class T>
arbin<T> & arbin<T>::izquierdo() const {
return raiz->izq;
}

//Devuelve el subarbol derecho del árbol, NULL si está vacío
template <class T>
arbin<T> & arbin<T>::derecho() const {
return raiz->der;
}

//Devuelve el elemento de la raiz
template <class T>
const T & arbin<T>::datoraiz() const {

return raiz->info;
}
template <class T>
T & arbin<T>::datoraiz() {
return raiz->info;
}


//Indica si el árbol binario está vacio
template <class T>
bool arbin<T>::esvacio () const {
return (raiz==NULL);
}

template <class T>
void arbin<T>::preorden() const {
if (!esvacio()) {
cout << raiz->info << " ";
izquierdo().preorden();
derecho().preorden();
}
}

kruncher
29 de Mayo del 2008

SOLUCION

Ya tengo hecho el programa, gracias por la ayuda. Lo pego por si os interesa.

/********************************************/
/* arbin.h
/********************************************/
//Clase ARBOL BINARIO
//Esta la clase arbol binario recursiva con el nodo dentro

#include <iostream>
using namespace std;

#ifndef ARBIN
#define ARBIN

template <class T>
class arbin {
public:
//constructoras
//construye un arbol binario vacio
arbin();

//crea un nuevo arbol binario a partir de un elemento y dos arboles binarios
arbin(const T & e, const arbin<T> & ai=arbin(), const arbin<T> & ad=arbin());

//modifica un arbin poniendo e como raiz e izqdo y dcho como hijo izquierdo
// y derecho respectivamente
void modificar (const T & e, const arbin<T> & izqdo, const arbin<T> & dcho);

//modica el arbol actual hasta obtener el arbin vacio
void vaciar();

//Copia el arbol binario actual
arbin<T> copiar();

//Devuelve el subarbol izquierdo del &#65533;rbol, NULL si est&#65533; vac
arbin<T> & izquierdo() const;

//Devuelve el subarbol derecho del &#65533;rbol, NULL si est&#65533; vac
arbin<T> & derecho() const;
//Devuelve el elemento de la raiz
const T & datoraiz() const;
T & datoraiz() ;

//Indica si el &#65533;rbol binario est&#65533; vacio
bool esvacio () const;

//recorre el arbol en preorden
void preorden() const;

//muestra el arbol en notacion infija
string notacion_infija() const;

//Comprueba que el arbin es extendido
bool esExtendido () const;

private:
//nodo del arbol binario
struct Nodo {
T info;
arbin<T> izq;
arbin<T> der;

//constructor
Nodo (T e=T(), arbin<T> iz=arbin(), arbin<T> de=arbin()) {
info=e;
izq=iz;
der=de;
}
//destructor
//~Nodo();
};

typedef Nodo * PNodo;
PNodo raiz; //puntero a la raiz del &#65533;rbol binario

};
#endif

//IMPLEMENTACIONES
//construye un arbol binario vacio
template <class T>
arbin<T>::arbin() {
raiz=NULL;
}

//crea un nuevo arbol binario a partir de un elemento y dos arboles binarios
template <class T>
arbin<T>::arbin(const T & e, const arbin<T> & izqdo, const arbin<T> & decho) {
raiz= new Nodo(e, izqdo, decho);
}


//modifica un arbin poniendo e como raiz e izqdo y dcho como hijo izquierdo
// y derecho respectivamente
template <class T>
void arbin<T>::modificar (const T & e, const arbin<T> & izqdo, const arbin<T> & dcho) {
if (!esvacio()) {
raiz->info=e;
raiz->izq=izqdo;
raiz->der=dcho;
}
else cout << "Error: arbol binario vacio" << endl;
}
//modica el arbol actual hasta obtener el arbin vacio
template <class T>
void arbin<T>::vaciar() {
if (!esvacio()) {
izquierdo().vaciar();
derecho().vaciar();
delete raiz;
}
}


//Copia el arbol binario actual
template <class T>
arbin<T> arbin<T>::copiar() {
arbin i, d ;
if (!esvacio()) {
if (!izquierdo().esvacio()) i=izquierdo().copiar();
if (!derecho().esvacio()) d=derecho().copiar();
//raiz=new Nodo(raiz->info, i, d);
//return raiz;
arbin x (raiz->info, i, d);
return x;
}
}

//Devuelve el subarbol izquierdo del &#65533;rbol, NULL si est&#65533; vac
template <class T>
arbin<T> & arbin<T>::izquierdo() const {
return raiz->izq;
}

//Devuelve el subarbol derecho del &#65533;rbol, NULL si est&#65533; vac
template <class T>
arbin<T> & arbin<T>::derecho() const {
return raiz->der;
}
//Devuelve el elemento de la raiz
template <class T>
const T & arbin<T>::datoraiz() const {

return raiz->info;
}
template <class T>
T & arbin<T>::datoraiz() {
return raiz->info;
}


//Indica si el &#65533;rbol binario est&#65533; vacio
template <class T>
bool arbin<T>::esvacio () const {
return (raiz==NULL);
}

template <class T>
void arbin<T>::preorden() const {
if (!esvacio()) {
cout << raiz->info << " ";
izquierdo().preorden();
derecho().preorden();
}
}

template <class T>
string arbin<T>::notacion_infija()const
{
string st;
if(!esvacio())
{
if(!izquierdo().esvacio() && !derecho().esvacio())
return st="("+izquierdo().notacion_infija()+raiz->info+derecho().notacion_infija()+")";
else
return st=raiz->info;
}
}

////////////// OKk
template <class T>
bool arbin<T>::esExtendido() const {
bool ext=false;

if(esvacio()) {
ext=true;

} else {
if((!izquierdo().esvacio()) && (derecho().esvacio()) || ((izquierdo().esvacio())&& (!derecho().esvacio()))) {
ext=false;
} else {
ext=izquierdo().esExtendido();
ext=derecho().esExtendido();
}
}
return ext;
}

/********************************************/
/* main.cpp
/********************************************/
#include <iostream>
#include "arbin.h"
using namespace std;

bool es_entero (char a) {
if (a=='*' || a=='/' || a=='-' || a=='+')
return false;
return true;
}

float evaluar (const arbin<char> &a) {
if (a.izquierdo().esvacio() && a.derecho().esvacio()) {
return a.datoraiz() - '0';
} else {
switch (a.datoraiz()) {
case '+':
return (evaluar(a.izquierdo()) + evaluar(a.derecho()));
break;
case '-':
return (evaluar(a.izquierdo()) - evaluar(a.derecho()));
break;
case '*':
return (evaluar(a.izquierdo()) * evaluar(a.derecho()));
break;
case '/':
return (evaluar(a.izquierdo()) / evaluar(a.derecho()));
break;
}
}
}

arbin <char> crear_arbol2 (string cadena,int tam, int &pos){
arbin<char> izq,der;
if (pos<tam) {
if (!es_entero(cadena[pos])) {
arbin<char> arb(cadena[pos]);
pos++;
izq = crear_arbol2 (cadena,tam,pos);
pos++;
der = crear_arbol2 (cadena,tam,pos);
arb.modificar(arb.datoraiz(),izq,der);
return arb;
} else {
return arbin<char> (cadena[pos],izq,der);
}
}
}

void notacion_funcional(const arbin<char> & a){
char raiz;
if (!a.esvacio()) {
raiz=a.datoraiz();
switch (raiz) {
case '+':
cout << "suma(";
break;
case '-':
cout << "resta(";
break;
case '*':
cout << "producto(";
break;
case '/':
cout << "division(";
break;
default:
cout << raiz;
break;
}
notacion_funcional(a.izquierdo());
if(raiz=='+' || raiz=='*'|| raiz=='/'||raiz=='-' )
cout << ",";
notacion_funcional(a.derecho());
}
if(raiz=='+' || raiz=='*'|| raiz=='/'||raiz=='-' )
cout<<")";
}

int main () {

string s;
arbin <char> a;
char sig = 's';
int tam;

while (sig!='n') {
cout << "Nueva cadena: ";
cin >> s;
tam= s.length();
cout << endl;
cout << "Longitud: " << tam ;

// PREGUNTA 1
//cout << "****************************************" << endl;
//cout << "Crear arbol: " << endl;
int pos =0;
a = crear_arbol2 (s,tam,pos);
cout << endl;
// PREGUNTA 2
cout << "****************************************" << endl;
cout << "Mostrar arbol: " << endl;
a.preorden();
cout << endl;

// PREGUNTA 3
cout << "****************************************" << endl;
if (a.esExtendido())
cout << "Es Extendido.";
else
cout << "No es Extendido.";
cout << endl;

// PREGUNTA 4 Notacion Infija
cout << "****************************************" << endl;
cout << "Notacion Infija : " << endl;
cout << a.notacion_infija();
cout << endl;

// PREGUNTA 5
cout << "****************************************" << endl;
cout << "Notacion funcional: " << endl;
notacion_funcional (a);
cout << endl;

// PREGUNTA 6
cout << "****************************************" << endl;
cout << "Evaluar arbol: " << evaluar(a);
cout << endl;

////////////////////////////////////////////////////
cout << "Introducir otra cadena? (s/n)? ";
cin >> sig;
cout << endl;

} // Final del while

return 1;
}

/********************************************//********************************************/
/********************************************//********************************************/
Esto es todo, para compilar como supongo q ya sabreis ...
$ g++ main.cpp && ./a.out

Un saludo !