i asked my professor to give me an old homework from another semester. And its about building a family tree and then finding the kinship between two nodes given. The family tree is about namekians (Dragon ball z) so every namekian has a single father.
The thing is that the input its something like this:
First name is the parent Second name is the child
Iolin Lyre
Iolin Piyano
Batu Iolin
Batu Okiat
Ollusc Xylo
Organa Murd
Piccoro Ollusc
Piccoro Rombone
Rombone Organa
So i must have two trees, one with Piccoro as the leader (he is always the leader of one tree) and another with unknown leader.
The thing is that i have trouble when i try to create the trees, i know i have two roots, but as you can see the input is not in order so ill have nodes without parent until i read and create its parent. For example, i create Ollusc and its child Xylo, and then Organa and Murd, but i only have one root to represent that tree (Also i dont know if they are in the same tree or not) so i dont know how to "save" those nodes to connect them later, same happens with Organa and Rombone, Organa will be somewhere until i create Rombone and then connect him with Organa.
Batu------>NULL
/ \
Iolin--->Okiat->NULL
/ \
Lyre-->Piyano->NULL
Piccoro-----> NULL
/ \
Ollusc--->Rombone->NULL
/ /
Xylo->NULL Organa->NULL
/
Murd->NULL
I thought about saving nodes into a Queue or maybe a Stack because i dont know how much nodes will be floating somewhere until i connect them, but save them into a queue and then what?, because when i think about my next step i don't know what to do. Maybe store a node into the queue until a node Parent appears, and then take that node from queue, but queue its FIFO and doesnt help too much i think, because what if i need to take the second node or maybe the third instead of the front one. So maybe store them into a aux list? I should add a node to a list,Queue,stack if they have no parent and they are not the root right? or should i add the root to the list,Queue,Stack? Because i'm using root to build the tree In the first Tree my root its Iolin until batu appears and i change it to batu In the second tree Root will be always Piccoro, but its a little difficult to build a tree starting with piccoro because i dont know his childs
What do you think? what should i do? Do you have better or other ideas?
int main(int argc, char const *argv[])
{
FILE *fpInput,*fpOutput;
fpInput = fopen("input.in","r");
fpOutput = fopen("output.out","w");
if ((fpInput == NULL)){ printf("Open File Error\n"); exit(1); }
// To read a line of the file
char *fpInputString;
char *parentInput, *childInput;
// Because i dont know the number of lines that comes next, read until a number is found
// That number is the number of consult of kinship about namekians
fpInputString = inputString(fpInput,5);
while ((strlen(fpInputString) != 1) && (strlen(fpInputString) != 2) && (strlen(fpInputString) != 3))
{
parentInput = strtok(fpInputString," ");
childInput = strtok(NULL,"\0");
fpInputString = inputString(fpInput,5);
}
fclose(fpInput);
fclose(fpOutput);
return 0;
}
InputString Function reads a whole line from a file
tree.h
// Struct of a node
struct treeNode
{
// Name
char *name;
// Pointers
struct treeNode *parent;
struct treeNode *firstChild;
struct treeNode *nextSibling;
struct treeNode *prevSibling;
};
I'll be very thankful if you help me, i know it can be hard to understand me or my code
But i really want to learn new things about coding, i don't know if this homework will be better if i do it in c++ because c doesn't have STL
Aucun commentaire:
Enregistrer un commentaire