Thread: Saving trees in files

but if we say that nodes to the right of its parent are "greater than" the parent and nodes that are left of its parent are "less than" the parent, then doesn't the first tree demonstrate that C is "greater than" A and B, and as demonstrated by the second tree that C is "less than" both A and B. These two trees contradict eachother if the meanings of A, B, and C are the same in both trees.

The tree I have is in no way sorted, so A < B < C does not hold. Sorry if I didn't mention this, but I thought it was implied by *NOT* saying it was a sorted tree...

you expect to read the data from a file and restore an incomplete structure. That's not really going to work well unless you save the data with corresponding structure locations that a specialized rebuild algorithm can use to place the nodes correctly

Well, I am storing it in a way it can be completely reconstructed, using these special characters. At least I'm pretty sure it can, which was one of the reasons for this post.

Well, to me it seems that you wanna do the hard work instead of letting your program do all the processing. I mean why you want a tree in your file?

Does it really matter why? I have an arbitrary not neccessarily balanced, not neccessarily sorted, not neccessarily full binary tree. I want to be able to save it to a file then load and reconstruct it EXACTLY as it was at a later time. This tree-in-file thing is NOT a substitute for having a tree of real pointers and nodes in memory. It's for storage.

If you must have a concrete situation it's for a huffman tree for data compression, to create uniquely decodable prefix codes.


Thanks for your trust LloydUzari, I'll go with your advice and follow my advice to avoid other confusing advice .

Originally Posted by Magos

The tree I have is in no way sorted, so A < B < C does not hold. Sorry if I didn't mention this, but I thought it was implied by *NOT* saying it was a sorted tree...

Ok... I always think of the nodes having some order relative to one another when I think of trees. Nevermind then.

There are many ways to store a tree, here's one:
Store them in clumps of three, first the current node ID, then the left node ID, then the right node ID.

This tree

Code:

    A
   / \
  B   C
 /   / \
D   E   F
       / \
      G   H

would then be stored as

Code:

ABC BDX CEF EXX FGH GXX HXX

(spaces just for clarity) where X is a null ID.


It's pretty much the raw data, not very compact at all, but you won't have to worry about corrupt headers.
You could also store the elements in any order you wanted, and use XAI to mark two roots (or XAA if you're just sticking with one).
Traversing backwards through this structure isn't very intuitive though.



[edit]
Whops, didn't see page 2. This is in essence what Perspective said.
[/edit]

I had an idea. Given the tree:

Code:

    A
   / \
  B   C
 /   / \
D   E   F
       / \
      G   H

Put:
ABDACECFGFH
(broken up)
ABD-A-CE-C-FG-F-H


In other words, traverse down the left, then back up to the first branch to the right and traverse down that branch's left, back up to the first right branch on that one, etc... Does that make sense? Anyway, that way if you have say a dead left branch at the start of the tree, you won't have to fill up all the lower levels on the left with 'dead' characters. Of course, it might be somewhat difficult to implement, but then which tree algorithm was ever easy?