234 Tree stored in binary file

[Joshua Schweigert]

Hello,
How would I store a 234 tree in a binary file?
I've never worked with trees or binary files before so it is very confusing.

Thanks.

[LB]

Do you know how to iterate every node in a tree?

Also, to say you have never worked with binary files is to say you have never used a computer. Besides quantum computers, all computers are binary and all data and files are binary - all that changes is how you interpret the data. Binary files are nothing special or difficult ;)

[Joshua Schweigert]

I do not, these are all new concepts to me and are very overwhelming hence why I need help. I need to read 32 bit positive integers from a text file into a 234 tree stored in a binary file. I'm confused how to read and write to the file and also how you interpret the data in the binary file to know which which is the root, which nodes are full, which are left and which are right, ect.

Thanks for any help.

[Joshua Schweigert]

Also this is the node format:

struct b_tree_node
  {
  int  num_keys;      // number of keys in this node
  int  key_val[3];    // key values (0 to num_keys - 1)
  int  child[4];      // child file addresses (0 to num_keys)
                      // [record index, not byte address]
  // may need filler to force zeros in any padding of the struct
  }

[LB]

That is definitely not a good format. Don't jump in so quickly, sit back and do some review first.

[Joshua Schweigert]

I've been trying to look around and understand binary files mire but its confusing as hell. Also that's the struct I have to use... Which sucks if its a bad format to learn with.

[JLBorges]

> How would I store a 234 tree in a binary file?

Don't.

Store the information in a text file; one b_tree_node per line.

[Joshua Schweigert]

I need to use a binary file to understand them as well as the tree.

[Smac89]

Store the information just like you would if you are storing in a heap data structure.

for example take the tree:

          24
      /        \
    20         30
 /     \     /     \
10     23  26       35

To store this as an array:

24 20 30 10 23 26 35
[1  2  3  4  5  6  7]

Where each node t at position p has a child at position 2p and position 2p + 1

Then when you read that from a file (binary file or whatever you have), you simply call insert for each value you read and the same binary tree is reconstructed.

Hopefully this helps

I believe this method has a name; it is called level order traversal. So basically still the same thing:
http://www.geeksforgeeks.org/level-order-tree-traversal/

[Joshua Schweigert]

I guess what I'm confused about is how you are supposed to interpret, from a binary file, what values are in which node to reconstruct the tree. I also need to be able to split nodes, as this is a 234 tree, and it just adds to my confusion. How exactly are things stored in a binary file? Such as a structure? How would you write a structure to a binary file, then read it back to a "temporary" structure? I guess that might help if I can figure that out.

Thanks!

[LB]

Joshua Schweigert wrote:

I guess what I'm confused about is how you are supposed to interpret, from a binary file, what values are in which node to reconstruct the tree.

Smac89 wrote:

Where each node t at position p has a child at position 2p and position 2p + 1

Then when you read that from a file (binary file or whatever you have), you simply call insert for each value you read and the same binary tree is reconstructed.

The order doesn't even matter if your insert function is written correctly ;)

[Smac89]

I think this is what you are looking for:
http://www.codingunit.com/c-tutorial-binary-file-io

EDIT
Also try not to get to verbal. Everyone commenting on your posts is trying to help.

[LB]

Joshua Schweigert wrote:

L B do me a favor and get the fuck off of my posts you annoying little shit.

I don't know what I did to offend you, but since you asked nicely, I'll stop helping you permanently.

[JLBorges]

Something like this:

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

struct node
{
    std::vector<int> keys ;
    std::vector<int> children ;
};

const std::string lead_in = "keys: " ;
const std::string seperator = " child_indices: " ;

std::ostream& operator<< ( std::ostream& stm, const node& n )
{
    stm << lead_in ;
    for( int key : n.keys ) stm << key << ' ' ;
    stm << seperator ;
    for( int child : n.children ) stm << child << ' ' ;
    return stm << '\n' ;
}

std::istream& operator>> ( std::istream& stm, node& n )
{
    n = node() ;

    std::string line ;
    std::getline( stm, line ) ;

    std::istringstream strstm(line) ;
    std::string lead ;
    strstm >> lead ; // extract the seperator
    // verify that lead == lead_in
    
    int v ;
    while( strstm >> v ) n.keys.push_back(v) ;

    strstm.clear() ;
    std::string sep ;
    strstm >> sep ; // extract the seperator
    // verify that sep == seperator

    while( strstm >> v ) n.children.push_back(v) ;

    return stm ;
}

int main()
{
    const std::vector<node> b_tree =
    {
        { { 1234, 5678 }, { 1, 2 } },          // #0
        { { 2345, 8321, 4578 }, { 3 } },       // #1
        { { 1000, 8765 }, { 4, 5, 6 } },       // #2
        { { 2134, 6789, 1238, 5555 }, { 7 } }, // #3
        { { 8855 }, {} },                      // #4
        { { 9927, 5610 }, {} },                // #5
        { { 1617, 5821, 5000 }, {} },          // #6
        { { 7299 }, {} }                       // #7
    };

    std::stringstream file ;
    for( const node& n : b_tree ) file << n ;

    std::cout << "file contains:\n" << file.str() ;

    file.seekg(0) ;
    std::vector<node> cpy ;
    node n ;
    while( file >> n ) cpy.push_back(n) ;

    static const auto eq = [] ( const node& a, const node& b )
    { return a.keys == b.keys && a.children == b.children ; } ;

    std::cout << "**** b_tree equal to cpy? " << std::boolalpha
              << std::equal( b_tree.begin(), b_tree.end(), cpy.begin(), eq ) << '\n' ;
}

http://coliru.stacked-crooked.com/a/f445fa9e20442774

EDIT: Hadn't seen Joshua Schweigert's post when I'd written this.
Or else I wouldn't have bothered.

[Joshua Schweigert]

Just for everyones information, that comment is clearly directed at LB... So Those getting mad, such as JLBorges, no need to get angry.

[Joshua Schweigert]

Also the reason I was so livid towards mr LB was because of his comment on another thread, which he claims was not intended to be rude, but clearly was. Thank you to the others who actually gave me useful information to learn from. All LB did was tell me not to jump to quickly or that the way the program is assigned is a bad way to do it. I'm sorry that I've been trying to get this for the past 2 weeks so you can understand my edginess as its very frustrating when someone just posts something that you cant really learn from.

Again, thank you to all those who ACTUALLY helped me.

[JLBorges]

> I'm sorry that I've been trying to get this for the past 2 weeks so you can understand my edginess

Yes. We do know and empathise with how frustrating it can get.

LB was making an effort to help you. I suppose you realize how frustrating it can get when you genuinely try to help someone, and get insulted for your troubles.

[Joshua Schweigert]

This is not the thread that angered m, so you think I'm getting mad at him for his comments above....that is not the case.

[Smac89]

OT/

Have you tried the information at the link I posted? It seems to address what you need specifically. Note that that method only works for POD types; so struct, int, double, etc

If you are using a class object to represent your tree, then doing a level order traversal of the tree will produce an output such that when you reinsert the values, you will get back the original 234 tree

And as LB mentioned, all files are binary files so simply store the output you get from the level order traversal into a .txt or .bin file and you are set