writiing/reading a tree in a file

[jgd]

how can i read/write a binary tree sturcture from/in a txt file?

[Ganon11]

For reading, it depends on how the data is stored.

For writing, it depends on how you want to write the data.

For both, is the data in the text file going to be sorted? Is it going to be the root value first, then the root's children, etc.? Specify these things, show us what you've thought of so far, and we'll help you out.

[jgd]

actually i want to build a tree by asking user to enter the value of node and asking him whether it is to be stored to left or right of current node.

for each leaf node there will be a path (consisting of left/right directions ) from root to that node. such information is to be stored in a file. and later this file is to be read.

path can be of the form:-

"hello", "RIGHT", "LEFT".
here, value ""HELLO" is stored in root's right child's left postion.


i m thinking of storing each node's path in a vector of strings. first element of the vector will store value of that leaf node and other elements will store the values as "left" or "right" word for directions.

storing that value in a file. the value of next node path can be stored in another vector. so, i hav 2 create a dynamically increasing array of vectors.


in this case how can i store the strings on a flie?

[Ganon11]

So basically you'll have a vector of vectors of strings? This seems unnecessarily complicated...

As far as storing the strings in the file...your file for reading may look like this:

name
my LEFT
is RIGHT
name LEFT LEFT
Ganon11 RIGHT RIGHT

This would be the tree:

    name
    /  \
  my    is
  /      \
hello   Ganon11

So each line is a different node, the first element is the content, and the remaining elements describe the path to that node. However, this might have problems. For instance, what if a file to be read contains:

name
hello LEFT RIGHT

Wait, name's left child doesn't exist, so how can you have a right child?

You may want to consider an alternate way of implementing this...look into a Binary Search Tree, perhaps? Or, depending on your project, other data structures entirely.

[jgd]

actually, my code will be such that like it creates a node first and then inserts that in a particular position. So there wont be a node of invalid path. The file is kind of a database to search for leaf node with a particular path. I can also use any other data structure. But the requirements of the tree construction requires me to stick to this plan only. There should be some other way out of that also. But, I need to stick to this way only. how can I implement that?

So basically you'll have a vector of vectors of strings? This seems unnecessarily complicated...

As far as storing the strings in the file...your file for reading may look like this:

name
my LEFT
is RIGHT
name LEFT LEFT
Ganon11 RIGHT RIGHT

This would be the tree:

    name
    /  \
  my    is
  /      \
hello   Ganon11

So each line is a different node, the first element is the content, and the remaining elements describe the path to that node. However, this might have problems. For instance, what if a file to be read contains:

name
hello LEFT RIGHT

Wait, name's left child doesn't exist, so how can you have a right child?

You may want to consider an alternate way of implementing this...look into a Binary Search Tree, perhaps? Or, depending on your project, other data structures entirely.

[Ganon11]

Hmmm...I don't know your project, so I can't tell if there's a better alternative available. This just seems inherently messy to me.

[jgd]

ok! so can u plz tell me how do u write read tree in a file by usign any of your methods. plz describe any of the storing method that u r using.

[Ganon11]

Are you focusing on reading a file to retrieve a tree, or on taking an existing tree and saving it in a file?

[jgd]

my program needs to have two parts.

first to ask user to enter data's values and "yes" and "no" values to store in a particular format.

then in second part, I need to search a particular data value, by asking user the "yes-no" option path. . .


can u plz help me with that. . . ???

[Ganon11]

OK, this sounds a LOT more do-able. I would just use a basic Binary Tree structure, except that instead of a node having left, right, and element, make it yes, no, and element. The element I presume is a string? This won't be too hard, and I'm sure there's simple Binary Tree code somewhere on the internet.

[jgd]

can't you help me in that code. can u plz gimme the code for the logic with which you are asking me to code. that will be a great help.

OK, this sounds a LOT more do-able. I would just use a basic Binary Tree structure, except that instead of a node having left, right, and element, make it yes, no, and element. The element I presume is a string? This won't be too hard, and I'm sure there's simple Binary Tree code somewhere on the internet.

[jgd]

actually you get it right this time. This is what I actually want to code. Can u help me in coding???

can't you help me in that code. can u plz gimme the code for the logic with which you are asking me to code. that will be a great help.

[Ganon11]

Sure, what code do you have so far?

[jgd]

actually i hav made a tree by user input.
Each node is a having an element of string & two pointers Y and N.

I want to store this tree in a file such that in future when required, this file can be read and same tree can be constructed once again.

I can have any format for storing that. But, I am out of ideas.

Can you help in format idea and coding?

[jgd]

i have stored my tree in a vector of strings in preorder format. how can i build a tree from that vector of strings??? gimme code if possible

plz help
thanx in advance

[Ganon11]

If you have the strings in pre-order format, then let's say you have this vector:

[1][2][3][4][5][6][7]

which represents this tree:

            1
         /     \
       2        3
      / \      / \
     4  5     6  7

Then, in the vector, the children of vector[0] are vector[1] and vector[2], the children of vector[1] are vector[3] and vector[4], the children of vector[2] are vector[6] and vector[7]. In general, this means that the children of vector[n] are vector[2n+1] and vector[2n+2].

You'll have to put in empty spots, though, if your tree is not complete (i.e. a node has 1 child, instead of the example, where there are only full nodes or leaf nodes).