Creating a binary tree to/from a text file

[samohtvii]

Hi all,

I am having trouble getting a tree to and from a text file.

The text file will hold questions and animals. Each node should hold one question and one animal.
So if you can imagine:

      Does it have 4 legs?
       /               \
 Does it purr?    Does it swim?
   /       \        /       \
 Cat      Dog     fish      NULL

yes being left and no being right.

That is the tree that is created. How would that get read into a file. How can I say in the text file "Don't go down any further past 'does it purr', go back to the right node and put the new node there".

So the file will be saved and can be read back into another run of the program.
How can i reconstruct this tree without knowing what it looked like before.

I hope this makes sense. It's doing my head in trying to think about it.

Ok so what i was thinking was add the nodes in sequence. so the text file would be
Does it have 4 legs?
Does it purr?
Cat
Dog
Does it swim?
fish

Does this require recursive functions?
Now that i think about it that ^above way would work right?

maybe just one node with 'data' and if ends in a question mark its a question and has more branches.

Any thoughts? ideas?

Thanks

[WaltP]

You have to somehow label the nodes:

1   Does it have 4 legs?     initial (1st) question
21Y Does it purr?            2nd level Yes 
31Y Cat                      3rd level Yes
31N Dog                      3rd level No
22Y Does it swim?            2nd level No
32Y fish                     3rd level Yes
32N                          3rd level No

Something along those lines. You'll have to think through the linkages a little more deeply than this.

[m4ster_r0shi]

Ok so what i was thinking was add the nodes in sequence. so the text file would be

Does it have 4 legs?
Does it purr?
Cat
Dog
Does it swim?
fish

What you do here is called printing the tree using preorder traversal.

Does this require recursive functions?

No, but it is greatly simplified if you use recursion to implement it.

Now that i think about it that ^above way would work right?

Yes, but it needs a slight modification. You have to also output the null nodes:

Does it have 4 legs?
Does it purr?
Cat
null
null
Dog
null
null
Does it swim?
fish
null
null
null

What you want to do is called binary tree (de)serialization.
If you google this term, you'll get some interesting results.

[samohtvii]

EDIT:

OK I have mine set-up similar to the example in that link.

struct animalTree {
    char data[100];
    animalTree *left;
    animalTree *right;
};

void fillTree(ifstream& ins, animalTree *&node) //Checks if file data says "NULL"
{
if(!readNext(data, ins)) return;

node = new animalTree(data);
fillTree(ins, node->left);
fillTree(ins, node->right);
}

So it doesn't like the node = new aniaml... line. Do i need a constructor that says like

animalTree(char* x) (data = x);

or something?
and do i ever need to make the struct like animalTree thisIsATree;
Thanks

[samohtvii]

Ok I have it all set-up now works fine. I just do all the filling of the tree and then i want to later on in the program read the data but the i can't get the root back.
I say

animalTree* root;

like i had done before but it seems to return maybe the end of the tree because it outputs garbage. How can i get the root back? :S
Thanks

[m4ster_r0shi]

Could you post the code?

[samohtvii]

Looks like i'm all goos at this stage. Managed to work it all. Thanks for all the help.
That link you gave was a godsend. Exactly what i needed.

Thanks