Foros del Web » Programación » C/C++ »

[SOLUCIONADO] Problema en Arbol?

Estas en el tema de Problema en Arbol? en el foro de C/C++ en Foros del Web. Hola amigos, estoy intentando llenar 1 Arbol de tres nodos a lo maximo, tengo 1 funcion para insertar los nodos al arbol: void SkillTree::AddSkill(char* name,char* ...
  #1 (permalink)  
Antiguo 13/03/2013, 15:52
Avatar de cronopiomx  
Fecha de Ingreso: mayo-2012
Ubicación: Programing Cloud
Mensajes: 276
Antigüedad: 2 años, 5 meses
Puntos: 28
Problema en Arbol?

Hola amigos, estoy intentando llenar 1 Arbol de tres nodos a lo maximo, tengo 1 funcion para insertar los nodos al arbol:

void SkillTree::AddSkill(char* name,char* desc,int level,char* parentName)
{
Skill item(name, desc,level); //el nombre es unico
TreeNode* parent = treeContains(root, parentName);

if (parent!=NULL)
{
if ( parent->left == NULL )
parent->left = new TreeNode(item);
else if ( parent->middle == NULL )
parent->middle = new TreeNode(item);
else if ( parent->right == NULL )
parent->right = new TreeNode(item);
}
}

para buscar cualquier nodo en el arbol:
TreeNode* SkillTree::treeContains( TreeNode *root, char* parentName )
{
if (root==NULL) {
return NULL;
}
else if ( strcmp(parentName, root->item.getName())==0 ) {
return root;
}
else if ( root->left!=NULL && strcmp(parentName,root->left->item.getName())==0)
{
return treeContains( root->left, parentName );
}
else if (root->middle !=NULL && strcmp(parentName , root->middle->item.getName())==0) {
return treeContains( root->middle, parentName );
}
else if (root->right!=NULL && strcmp(parentName , root->right->item.getName())==0) {
return treeContains( root->right, parentName );
}
return NULL;
}

para imprimir el resultado:

void SkillTree::inorderPrint( TreeNode *root ) {
if ( root != NULL )
{
cout<<root->item.getName() << " -- " <<root->item.getDescription() <<" [Lvl: " <<root->item.getLevel() <<"]\n";
inorderPrint( root->left );
inorderPrint( root->middle );
inorderPrint( root->right );
}
}
---------------------------------------------------------------------------
en la funcion main()

SkillTree student("Student");
student.Display(cout) ; //llama al metodo inorderPrint

student.AddSkill("Alphabet","Mastery of letters and sounds",0);
student.Display(cout);

student.AddSkill("Reading","The ability to read all manner of written material",1,"Alphabet");
student.AddSkill("Writing","The ability to put your thoughts on paper",1,"Alphabet");
student.Display(cout);

student.AddSkill("Speed Reading Level 1","Read any text twice as fast as normal",5,"Reading");
student.AddSkill("Speed Reading Level 2","Read any text four times as fast as normal",10,"Speed Reading Level 1");
student.AddSkill("Memorization","Memorize average sized texts",10,"Reading");
student.AddSkill("Massive Memorization","Memorize large sized texts",20,"Memorization");
student.AddSkill("Spell Writing","The ability to write spells",5,"Writing");
student.AddSkill("History","The ability to write (and rewrite) history",10,"Writing");
student.AddSkill("Written Creation","The ability to write things into reality",20,"History");
student.Display(cout);
---------------------------------------------------------------

El resultado que obtengo es :
Skill Tree: Student
Empty
Skill Tree: Student
- Alphabet -- Mastery of letters and sounds [Lvl: 0]
Skill Tree: Student
- Alphabet -- Mastery of letters and sounds [Lvl: 0]
- Reading -- The ability to read all manner of written material [Lvl: 1]
- Writing -- The ability to put your thoughts on paper [Lvl: 1]
Skill Tree: Student
- Alphabet -- Mastery of letters and sounds [Lvl: 0]
- Reading -- The ability to read all manner of written material [Lvl: 1]
- Speed Reading Level 1 -- Read any text twice as fast as normal [Lvl: 5]
- Memorization -- Memorize average sized texts [Lvl: 10]
- Writing -- The ability to put your thoughts on paper [Lvl: 1]
- Spell Writing -- The ability to write spells [Lvl: 5]
- History -- The ability to write (and rewrite) history [Lvl: 10]
Press any key to continue . . .

y Necesito:

Skill Tree: Student
Empty
Skill Tree: Student
- Alphabet -- Mastery of letters and sounds [Lvl: 0]
Skill Tree: Student
- Alphabet -- Mastery of letters and sounds [Lvl: 0]
- Reading -- The ability to read all manner of written material [Lvl: 1]
- Writing -- The ability to put your thoughts on paper [Lvl: 1]
Skill Tree: Student
- Alphabet -- Mastery of letters and sounds [Lvl: 0]
- Reading -- The ability to read all manner of written material [Lvl: 1]
- Speed Reading Level 1 -- Read any text twice as fast as normal [Lvl: 5]
- Speed Reading Level 2 -- Read any text four times as fast as normal [Lvl: 10]
- Memorization -- Memorize average sized texts [Lvl: 10]
- Massive Memorization -- Memorize large sized texts [Lvl: 20]
- Writing -- The ability to put your thoughts on paper [Lvl: 1]
- Spell Writing -- The ability to write spells [Lvl: 5]
- History -- The ability to write (and rewrite) history [Lvl: 10]
- Written Creation -- The ability to write things into reality [Lvl: 20]

que problema tengo?

Última edición por cronopiomx; 13/03/2013 a las 15:53 Razón: sleep
  #2 (permalink)  
Antiguo 14/03/2013, 09:41
Avatar de cronopiomx  
Fecha de Ingreso: mayo-2012
Ubicación: Programing Cloud
Mensajes: 276
Antigüedad: 2 años, 5 meses
Puntos: 28
Pregunta Respuesta: Problema en Arbol?

Hola amigos, aqui lo he puesto todo en el main, facil para compilar, estoy implementando 1 ejercicio que requiere 1 Arbol, este arbol solo debe tener 3 nodos, el caso es que tengo 1 funcion ( treeContains() ) que dado 1 char* name, me tiene que bucar el nodo que yo le diga, el caso es que me busca mal, tengo 1 salida de datos que es la correcta y me muestra los todos los datos de otra forma erronea, que puede ser???

Este es mi codigo:???
Código:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cassert>
using namespace std;

class Skill {
  private:
	  char *name;
	  char *description;
	  int level;
  
  public:	
Skill(){ }
~Skill(){ }
Skill(char * name, char* desc, int level)
{
	this->name = name;
	this->description = desc;
	this->level = level;
}
char* getName(){	return this->name;}
char* getDescription() { return this->description;}
int getLevel(){	return this->level;}
};

struct TreeNode {
    Skill item;         // The data in this node.
    TreeNode *left;      // Pointer to the left subtree.
    TreeNode *right;     // Pointer to the right subtree.
    TreeNode *middle;     // Pointer to the right subtree.    

    TreeNode (Skill sk) 
    {        
		item = sk;
        left = NULL;
        right = NULL;
        middle = NULL;
    }
};


class SkillTree {

  private:
	TreeNode* root; 
	char Title[100];

  public:

	SkillTree ():root(NULL) { }
    ~SkillTree (){ }
    SkillTree(char ch[]):root(NULL)
    {
	  strcpy(this->Title, ch);
    }
    bool Empty()
    {
	  if (this->root==NULL)
	 	return true;
	   return false;
    }
TreeNode* treeContains( TreeNode *root, char* parentName ) 
{	
     if (root==NULL) {
        return NULL;
    }
	 if ( strcmp(parentName, root->item.getName())==0 ) {     
        return root;
    }
	 if ( root->left!=NULL && strcmp(parentName,root->left->item.getName())==0) 
	{
        return treeContains( root->left, parentName );
    }
	 if (root->middle !=NULL && strcmp(parentName , root->middle->item.getName())==0)  {
		return treeContains( root->middle, parentName );
    }
	 if (root->right!=NULL && strcmp(parentName , root->right->item.getName())==0) {
        return treeContains( root->right, parentName );         
    }
	return root;
}
	
void AddSkill(char* name,char* desc,int level)
{
	Skill item(name, desc,level);	
	if(root==NULL) 
	{
		this->root = new TreeNode(item);
		
	}
}
void AddSkill(char* name,char* desc,int level,char* parentName)
{
	Skill item(name, desc,level);	
	TreeNode* parent = treeContains(root, parentName);
	
	if (parent!=NULL)
	{
		if ( parent->left == NULL )
			parent->left = new TreeNode(item);
		else if ( parent->middle == NULL )
			parent->middle = new TreeNode(item);
		else if ( parent->right == NULL )
			parent->right = new TreeNode(item);
	}
}	

void inorderPrint( TreeNode *root ) {
    if ( root != NULL )
    {  		
		
		cout<<root->item.getName() << " -- " <<root->item.getDescription() <<" [Lvl: " <<root->item.getLevel() <<"]\n"; 
        inorderPrint( root->left ); 
		inorderPrint( root->middle );
        inorderPrint( root->right );       
    }
}

void Display(ostream& out)
{
	out<<"Skill Tree: "<< Title <<"\n";
	if (Empty()) 
	{
		out<<"  Empty\n";
	}
	else 
	{
		inorderPrint(root);
	}
}
};

int main ()
{ 
	SkillTree student("Student");
	student.Display(cout)	;

	student.AddSkill("Alphabet","Mastery of letters and sounds",0);
	student.Display(cout);

	student.AddSkill("Reading","The ability to read all manner of written material",1,"Alphabet");
	student.AddSkill("Writing","The ability to put your thoughts on paper",1,"Alphabet");
	student.Display(cout);

	student.AddSkill("Speed Reading Level 1","Read any text twice as fast as normal",5,"Reading");	
	student.AddSkill("Speed Reading Level 2","Read any text four times as fast as normal",10,"Speed Reading Level 1");
	student.AddSkill("Memorization","Memorize average sized texts",10,"Reading");
	student.AddSkill("Massive Memorization","Memorize large sized texts",20,"Memorization");
	student.AddSkill("Spell Writing","The ability to write spells",5,"Writing");
	student.AddSkill("History","The ability to write (and rewrite) history",10,"Writing");
	student.AddSkill("Written Creation","The ability to write things into reality",20,"History");
	student.Display(cout);
	
	system("pause");
}
y mi salida esperada

Skill Tree: Student
Empty
Skill Tree: Student
- Alphabet -- Mastery of letters and sounds [Lvl: 0]
Skill Tree: Student
- Alphabet -- Mastery of letters and sounds [Lvl: 0]
- Reading -- The ability to read all manner of written material [Lvl: 1]
- Writing -- The ability to put your thoughts on paper [Lvl: 1]
Skill Tree: Student
- Alphabet -- Mastery of letters and sounds [Lvl: 0]
- Reading -- The ability to read all manner of written material [Lvl: 1]
- Speed Reading Level 1 -- Read any text twice as fast as normal [Lvl: 5]
- Speed Reading Level 2 -- Read any text four times as fast as normal [Lvl: 10]
- Memorization -- Memorize average sized texts [Lvl: 10]
- Massive Memorization -- Memorize large sized texts [Lvl: 20]
- Writing -- The ability to put your thoughts on paper [Lvl: 1]
- Spell Writing -- The ability to write spells [Lvl: 5]
- History -- The ability to write (and rewrite) history [Lvl: 10]
- Written Creation -- The ability to write things into reality [Lvl: 20]
  #3 (permalink)  
Antiguo 14/03/2013, 12:14
 
Fecha de Ingreso: julio-2012
Mensajes: 291
Antigüedad: 2 años, 3 meses
Puntos: 21
Respuesta: Problema en Arbol?

Me da a mi que un profesor ha mandado ejercicios sobre arboles (no eres el primero que pregunta una cosa parecida).

Lo primero es, que no es obligatorio crear un constructor/destructor. Por lo que estás líneas:

Código C++:
Ver original
  1. Skill(){ }
  2. ~Skill(){ }

No harían falta, el propio compilador te los crea por defecto.

Tampoco es imprescindible usar el operador this para acceder a parametros dentro de la propia clase:

Código C++:
Ver original
  1. Skill(char * name, char* desc, int level)
  2. {
  3.     this->name = name;
  4.     this->description = desc;
  5.     this->level = level;
  6. }

Podría simplificarse a :

Código C++:
Ver original
  1. Skill(char * Name, char* Desc, int Level)
  2. {
  3.     name = name;
  4.     description = desc; // Precaución, estas asignando punteros no contenidos.
  5.     level = level;
  6. }

Lo mismo con:

Código C++:
Ver original
  1. char* getName(){    return name;}
  2. char* getDescription() { return description;}
  3. int getLevel(){ return level;}

Y bueno el código es muy largo pero creo que has liado algo con los char* (eso de pasar punteros a funciones y clases no me gusta nada). Creo que sería más comodo usar strings:

Código C++:
Ver original
  1. string name = "Texto";

Además la comparación entre dos strings es inmediata:

Código C++:
Ver original
  1. if (texto1 == texto2)
  2. {
  3.  // Tal y tal
  4. }

La funcion strcmp es muy propensa a errores, es necesario que ambas cadenas tengan un caracter vacío '\0' al final o la función fallará.

Última edición por amchacon; 14/03/2013 a las 12:35
  #4 (permalink)  
Antiguo 15/03/2013, 07:43
Avatar de cronopiomx  
Fecha de Ingreso: mayo-2012
Ubicación: Programing Cloud
Mensajes: 276
Antigüedad: 2 años, 5 meses
Puntos: 28
Respuesta: Problema en Arbol?

Hola, gracias por la respuesta, el uso de punteros esta bien y funciona, el problema era en la función TreeContains(), ese metodo estaba mal por las siguientes razones:

1. Primero compruebas si es la raiz, de ser correcto retornas el nodo.

2. Si no es la raiz, compruebas que si es el izquierdo, el del medio o el derecho. El problema es que si no es ninguno de ellos, retornas NULL y no estas caminando por dentro del arbol.

lo he arreglado y lo he solucionado, pongo a disposicion el codigo del método TreeContains().

saludos
Cronos

Código:
TreeNode* SkillTree::treeContains( TreeNode *root, char* parentName ) {	
     if (root==NULL) {
        return NULL;
    }
	 if ( strcmp(parentName, root->item->getName())==0 ) {     
        return root;
    }
	 if ( root->left!=NULL ) 
	{
        TreeNode * aux= treeContains( root->left, parentName );
        if(aux!=NULL)
            return aux;
    }
	 if (root->middle !=NULL )  {
		 TreeNode * aux= treeContains( root->middle, parentName );
		
		if(aux!=NULL)
            return aux;
    }
	 if (root->right!=NULL ) {
        TreeNode * aux= treeContains( root->right, parentName );
        
        if(aux!=NULL)
            return aux;         
    }
	return NULL;
}

Etiquetas: int
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 14:30.
SEO by vBSEO 3.3.2