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.
alexfdezgil
Posts: 2
Joined: Wed Mar 13, 2013 7:44 pm
Gender: None specified

Problema con Recorrido de Arboles?

Postby alexfdezgil » Wed Mar 13, 2013 7:48 pm

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
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: Problema con Recorrido de Arboles?

Postby ymondelo20 » Wed Mar 13, 2013 10:42 pm

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: Wed Mar 13, 2013 7:44 pm
Gender: None specified

Re: Problema con Recorrido de Arboles?

Postby alexfdezgil » Sat Mar 16, 2013 9:43 pm

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


Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest