• Jueves 28 de Marzo de 2024, 18:47

Autor Tema:  Problema en Arbol con tres nodos?  (Leído 1812 veces)

cronopiomx

  • Nuevo Miembro
  • *
  • Mensajes: 2
    • Ver Perfil
Problema en Arbol con tres nodos?
« en: Jueves 14 de Marzo de 2013, 16:38 »
0
Hola amigos, 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: [Seleccionar]
#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]

cronopiomx

  • Nuevo Miembro
  • *
  • Mensajes: 2
    • Ver Perfil
Re:Problema en Arbol con tres nodos?
« Respuesta #1 en: Viernes 15 de Marzo de 2013, 14:49 »
0
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: [Seleccionar]
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;
}