Problema con Recorrido de Arboles?

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
alexfdezgil
Posts: 2
Joined: 5 years ago
Gender: None specified

Problema con Recorrido de Arboles?

Post by alexfdezgil » 5 years ago

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

Code: Select all

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);
}
}

Code: Select all

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:

Code: Select all

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);
---------------------------------------------------------------
Mi salida 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 . . .

Salida Esperada, que no obtengo:

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?



User avatar
ymondelo20
Posts: 1968
Joined: 6 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: Problema con Recorrido de Arboles?

Post by ymondelo20 » 5 years ago

Un poco tediosa de entender la salida esa :D
Creo que el Método ---:: treeContains ---:: en realidad no deberia preguntar por el nombre, para hacer la llamada recursiva...
en todo caso debe llamar siempre, y chequear, se se devuelve algo distinto del NULL, para esa rama. Por supuesto, también puedes pensar una implementación más eficiente del árbol.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

alexfdezgil
Posts: 2
Joined: 5 years ago
Gender: None specified

Re: Problema con Recorrido de Arboles?

Post by alexfdezgil » 5 years ago

Yonny, 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, gracias,

s2
alex

Code: Select all

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;
}

Post Reply

Return to “Algorithms”