Necesito hacer una funcion find que me busque dentro de un arbol binario de expresion, otro subarbol y devuelva el nodo del arbol, donde comienza.
Por ejemplo, tengo el arbol
+
/ \
* 7
/ \
2 3
Y la subexpresion
*
/ \
2 3
Esta funcion find me devolveria el nodo que contiene el *
Creo que la mejor forma de hacerlo sería recursivamente.
La cabecera de la funcion debe ser algo asi:
pair<subexpresion, bool> find(const expresion & e);
Donde subexpresion es del tipo expresion::node (es el nodo que tiene que devolver)
bool devuelve true o false si lo ha encontrado o no
y expresion es un bintree<dato>
Asi sería el private de mi .h:
class expresion{
private:
class dato{
public:
pair<T,char> dat;
dato(const T &d){
dat.first=d;
dat.second='\0';
}
dato(const char &d){
dat.first=T();//nulo del tipo T
dat.second=d;
}
bool esoperando() const{
return (dat.second=='\0');
}
bool esoperador() const{
return (dat.second!='\0' && !esvariable());
}
bool esvariable() const{
return (dat.second>96 && dat.second<123);
}
T getT() const{
return dat.first;
}
char getchar() const{
return dat.second;
}
};
class subexpresion{
private:
typename bintree<typename expresion<T>::dato>::node subex;
public:
subexpresion(typename bintree<typename expresion<T>::dato>::node & e){
subex=e;
}
};
bintree<typename expresion<T>::dato> arbol;
expresion(const bintree<typename expresion<T>::dato> &e) {arbol = e;};
Gracias por vuestras ayudas y/o sugerencias
