## 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:

### Problema con Recorrido de Arboles?

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 unicoTreeNode* 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;}`

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 inorderPrintstudent.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 . . .

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?

ymondelo20
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender:
Contact:

### Re: Problema con Recorrido de Arboles?

Un poco tediosa de entender la salida esa
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:

### Re: Problema con Recorrido de Arboles?

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