Traversing trees

This is a discussion on Traversing trees within the C Programming forums, part of the General Programming Boards category; I've created an ADT for a quad tree in C. I'm using this quad tree to represent an image. I'm ...

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    2

    Traversing trees

    I've created an ADT for a quad tree in C. I'm using this quad tree to represent an image.

    I'm using a preorder traversal algorithm which recursively scans through the tree and prints nodes and RGB values to file.

    I'm storing the quad-tree in file as the following for an example:

    RB255255255B255255255B255255255B255255255

    R - Tree root
    B - Tree branch
    then the RGB values

    How could I read back this data from the file and create a the same tree? Is this possible?

    Does this make sense?

    Thank you,
    James Ed.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Assuming you have some way to denote the end of a tree, empty leaf/branch, whatever you want to call it, read it in the same way you read it out.
    Code:
    thisroot = this data
        read branch 1
        ...
        read branch 4
    Recursively do that until you run out of file. You will have to have some way to let it know when it's reached the end of the line so it will return though.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    For a text based data storage, either you must separate the data values (of Red, Green and Blue, etc) by something you can search for, like whitespace or punctation. Otherwise you can't extract the values because in your example all values are merged together. Well it works if you know the number of characters used for each value, like three digits, etc.
    You may also consider storing your data in a binary format, using a struct to store the data and make functions to serialize the data to disk. As you are working with image data, which is normaly large (maby?) it could be both more efficient in storage and speed to read/write the data, as with the text version you must convert text values into binary values, which is a bit inefficient.
    Bobby Fischer Live Radio Interviews http://home.att.ne.jp/moon/fischer/

  4. #4
    Registered User
    Join Date
    Dec 2005
    Posts
    2
    I haven't really used binary before when writing to files.

    I have two UDTs: one for holding the RGB values of the pixel, and the other for storing pointers to trees.

    I understand how the pixel can be written to file using something like this:

    Code:
    fwrite(&pixel, sizeof(pixel), 1, fp);
    But what would the traversal algorithm be for each pixel within the tree as only leaf nodes have pixel values.

    How would I store a node in the binary file?

    Thank you for your help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Trees
    By masterg in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2008, 12:42 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. AVL Trees
    By kwigibo in forum C Programming
    Replies: 2
    Last Post: 04-17-2002, 05:46 PM
  5. traversing binary trees or partial trees
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-05-2001, 08:19 PM

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