Saving trees in files

This is a discussion on Saving trees in files within the C++ Programming forums, part of the General Programming Boards category; but if we say that nodes to the right of its parent are "greater than" the parent and nodes that ...

  1. #16
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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 .
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  2. #17
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,793
    Quote 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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #18
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    ok, if the tree is not always full or balanced than my previously suggested indexing method wont work... so go for the obvious solution...

    a tree is nothing but a particular type of graph, store adjacency lists
    so from your OP you'd get..

    A: B C
    B: D
    C: E F
    E: G H

  4. #19
    Registered User
    Join Date
    Feb 2004
    Posts
    35
    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]
    Last edited by MortalMonkey; 08-29-2004 at 01:27 PM.

  5. #20
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    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?
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. saving name characters to files
    By clonedhero in forum C Programming
    Replies: 5
    Last Post: 01-16-2008, 02:20 PM
  2. Saving numbers to files
    By cpudaman in forum C++ Programming
    Replies: 5
    Last Post: 01-10-2008, 12:05 AM
  3. Help with loading files into rich text box
    By blueparukia in forum C# Programming
    Replies: 3
    Last Post: 10-19-2007, 12:59 AM
  4. Folding@Home Cboard team?
    By jverkoey in forum A Brief History of Cprogramming.com
    Replies: 398
    Last Post: 10-11-2005, 08:44 AM
  5. Batch file programming
    By year2038bug in forum Tech Board
    Replies: 10
    Last Post: 09-05-2005, 03:30 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21