Thread: Saving binary tree data to disk

  1. #1
    Enthusiastic Beginner balazsbotond's Avatar
    Join Date
    Mar 2007
    Location
    Érd, Hungary
    Posts
    20

    Saving binary tree data to disk

    I've made an implementation of this program using a binary tree. It works fine, but I'd like to save my decision tree to the disk because I don't want to lose the result of my "teaching". Do I have to invent my own file format and write a parser for it or is there a more simple method? Where should I start? Any suggestions are welcome.

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    just write it out using any (deterministic) tree traversal method, then you can read it back knowing where everything goes.

    A nice method is to use implied indices. The root is at index 1, then for any node at index i, store the left child at position 2*i and the right child at position 2*i + 1. Then you just have an array representing your tree.

  3. #3
    Enthusiastic Beginner balazsbotond's Avatar
    Join Date
    Mar 2007
    Location
    Érd, Hungary
    Posts
    20
    Perspective, thanks for your advice, it helped a lot.

    I'm trying to do a preorder traversal on my tree and write a bool value and the node text into the file in the order of the traversal. It doesn't work (it creates a file with a single line containing the data for the root). I'm clueless because it works when I'm writing on the console. The only difference is that I'm writing into a different stream. Or is it?

    Include this in the file I posted above:

    Code:
    void PreorderOutput(NodePtr ANode)
    {
        ofstream out_stream;
        
        out_stream.open("data.txt");
        
        out_stream << ANode->IsAnswer << ANode->Text << "\n";
        cout << ANode->IsAnswer << ANode->Text << "\n";
        
        if (!ANode->IsAnswer)
        {
            PreorderOutput(ANode->YesPtr);
            PreorderOutput(ANode->NoPtr);
        }
        out_stream.close();
    }

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    You're creating a new stream every time you recurse into PreorderOutput(). You need to make the stream object a singe instance throughout the recursion. You can do that by making it global or by making it a parameter to PreorderOutput().

    gg

  5. #5
    Enthusiastic Beginner balazsbotond's Avatar
    Join Date
    Mar 2007
    Location
    Érd, Hungary
    Posts
    20
    Oh thanks. I'm a bit tired (it's 6am here - I think I'm getting addicted to programming ).

  6. #6
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> I think I'm getting addicted to programming
    <cartman>"Sweet"

    gg
    Last edited by Codeplug; 12-08-2007 at 10:58 PM.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    The simplest method would be to iterate through the tree, save the current node, save the yes node, save the no node, then move on to the next.
    Note that saving strings using << is fine, but saving a bool using << will probably produce something like 0 or 1 in the file since it stores it as text. Also note that with bools, this isn't a problem, but if you're planning to store other data that is longer than 1 byte (int, for example), then it's better to use istream.write and istream.get since they work with binary data.

    I think operator << will stop reading a string when it hits space or '\0', so length shouldn't be an issue.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Enthusiastic Beginner balazsbotond's Avatar
    Join Date
    Mar 2007
    Location
    Érd, Hungary
    Posts
    20
    Elysia,
    Thanks for your reply.
    I searched Wikipedia for tree traversal and found my algorithm there. I think what you are (and Perspective has been) suggesting is a level order traversal, but it seems to me that although it would also work, preorder traversal is a lot simpler and does effectively the same thing (crawling through the tree in a predictable way). If I save a bool for every node that tells if that node is an end node (or 'leaf' or whatever it is called), it produces an output from which the tree can be recreated in memory using the same algorithm.

    Thx for your advice on the << operator and the istream functions. It made a lot of things clear.
    Last edited by balazsbotond; 12-09-2007 at 05:51 AM.

  9. #9
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I believe that way is kindof like what I suggested. Traverse the yes node, save the answer and if there's another yes node, then call itself and traverse that until NULL.
    After that, traverse the NO node.
    ...And all the way back to root.
    The only problem is loading the list back into memory which might not be so easy.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Enthusiastic Beginner balazsbotond's Avatar
    Join Date
    Mar 2007
    Location
    Érd, Hungary
    Posts
    20
    Finally my little program is running without errors. Thank you for all the advice, you guys are really helpful. I'm uploading the code, so if you have time, please have a look at it. I would welcome any comments on it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. binary tree token problem
    By OldSchool in forum C++ Programming
    Replies: 13
    Last Post: 05-28-2006, 10:42 PM
  2. saving a binary tree??
    By fayte in forum C++ Programming
    Replies: 9
    Last Post: 01-27-2005, 01:32 PM
  3. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM
  4. Building a Binary Search Tree off sorted data
    By BlackCitan in forum C Programming
    Replies: 0
    Last Post: 12-01-2003, 09:52 PM
  5. binary search tree help
    By noob2c in forum C++ Programming
    Replies: 6
    Last Post: 11-09-2003, 02:51 PM