Archived

This topic is now archived and is closed to further replies.

Saving a tree structure to disk...

This topic is 5175 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey ppl! i would like to get some different ideas for saving and loading a tree like structure to and from disk. my structure looks similiar to this: struct node { bool isDivided; // true is this node has subnodes nodeData *data; // node data node *subNode[8]; // eight subnodes } at the moment i am just recursing the tree and saving each node as i come accross it. So i am not saving the links between the nodes, to load the tree, i am recursing throught the file and creating a tree from scratch. Is there a more efficient way of saving/loading a tree like structure?? Should the links between the nodes be preserved?? Cheers Paul

Share this post


Link to post
Share on other sites
Without making things more complicated, that''s pretty much the way you want to go. It''s always hard to come up with a good approach for storing these types of structures to disk, because it''s the pointers that make them so flexible, and you loose that when it''s time to linearize the data. But as long as you have a consistent file saving/loading system, you''re doing well

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Save each node''s data while traversing the tree breadth-first, so that each piece of data is followed immediately by the data for the eight subnodes below it, making it easy to reconstruct the tree.

This assumes that all eight subNodes exist whenever isDivided is true. If that''s not the case then you''ll need to store information about which of the eight subNodes exist, so that you know where they go (and how many to read back) when reconstructing each node.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Kindly forget that I said "followed immediately", because it''s not true. What I''m trying to say is that you should store the data for each of the eight subNodes before travelling down the tree.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Better yet, forget everything I''ve said so far. An easier approach is to save/load the tree using depth-first traversal, like this:

To save a tree:
Save data of root node.
Save subtrees of root node.

To save subtrees of N:
Save data of (each subnode of N).
Save subtrees of (each subnode of N).

To load a tree:
Create root node.
Load data of root node.
Load subtrees of root node.

To load subtrees of N:
Create subnodes of N.
Load data of (each subnode of N).
Load subtrees of (each subnode of N).

Share this post


Link to post
Share on other sites
lol anonymous poster hehe thanks m8!
thankyou all for your input

One of my friends tried to describe the method thats used for a bsp tree, something to do with paralel arrays, where the first array stores the node and its link to other nodes, and the second array stores data???

is he dreaming? and pardon my ignorance, but whats XML?

Share this post


Link to post
Share on other sites
XML is a text-based system, eXtensible Markup Language, which was developed for data transmission across different computing platforms. The format is inherently defined as a root node (document), which contains child nodes, which can contain child nodes etc...

If parsing speed or storage requirements are not critical, then it's a very good way to store any tree-like data.

It's a web standard, therefore it's specification is found here.

-Nik

EDIT:

quote:
One of my friends tried to describe the method thats used for a bsp tree, something to do with paralel arrays, where the first array stores the node and its link to other nodes, and the second array stores data???


AFAIK raw hard disk data is stored this way, for example.
One array (partition header) contains the file indices and relations, while another array (the rest of disk space) contains the files.

[edited by - Nik02 on October 13, 2003 9:07:07 AM]

Share this post


Link to post
Share on other sites