#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Location
    delhi
    Posts
    4
    Rep Power
    0

    Unhappy writting binary tree to a file


    This is the first time i am doin some serious programming in streams and writting objects to file.

    How do i write a binary tree object to a file ? I cant find a way :( . How are records maintained while using any sort of tree ..

    Thanx
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Location
    Singapore
    Posts
    31
    Rep Power
    12
    Dont really understand what u are asking for though...but maybe this helps

    I guess u are wondering how tree structures is stored in a file and wonder how to retrieve these records in a tree data structure into memory....

    if that is the case,

    When commiting to a file, the record data does not need to reflects the tree structure, u will just reconstruct the tree based on some value each time u read in the file.
    Hence the file does NOT store any data structure metadata.
    U can construct the tree, by reading in the records sequentially from the file.

    In otherwords, ur file does not need to know what data structures ur appn is using. It can be a B+ tree, Binary tree, a linked list, a table, a stack...etc, it does not matter coz that is ur appn responsibility not ur file.

    u might want search out or read up on data structures programming... many sites and programming books cover it.

    Hope this helps, Sorrie if i misunderstood ur problem...
  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Location
    delhi
    Posts
    4
    Rep Power
    0
    yeah siddy ! u got my problem. But i am not satisfied with ur answer. because every time you load the file u r asking me to make a binary tree. Wat i asked was to store the tree and laod as it is from the file ??
  6. #4
  7. Doggie
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2003
    Location
    Seattle, WA
    Posts
    751
    Rep Power
    13
    If you must store the tree exactly as it is in memory, then try this:

    give each element of your tree an extra value to store a record number. (a long should work)

    starting at the leaf nodes, write that to your file and mark it's record number sequentially. You're recording them first because they don't point to any other nodes.

    As you write nodes that point to other nodes, instead of storing the pointer, you'll store the record number of the node it points to.

    As you read the file back in, you'll rebuild your tree from the bottom up with the root being the last node read in.

    example: ('->' means 'points to')
    tree:
    c->a,e
    a->b
    e->d,f
    Code:
       c
     /   \
    a     e
     \   / \
      b d   f
    write your leafs and record ids:
    b(1)
    d(2)
    f(3)

    write other nodes,record ids, and pointed to record ids:
    a(4)->(1)
    e(5)->(2,3)
    c(6)->(4,5)

    When you read them back in, it may be easier to create an array of pointers, create each node, and assign the pointers to the element in the array.

    ie:
    read in leafs:
    b,d,f

    next:
    a->1
    add a to array
    (b,d,f,a)
    add pointer
    (b,d,f,a->b) (b is element 1, so use that pointer)

    next:
    e->2,3
    add e to array
    (b,d,f,a->b,e)
    add pointers
    (b,d,f,a->b,e->d,f) (d,f are elements 2,3)

    repeat until no more elements to read, last element read is your root.

IMN logo majestic logo threadwatch logo seochat tools logo