Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Drag0n

A Couple of Questions On Trees...

This topic is 5737 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi! I just read the post about binary trees, so let''s get something straight here: this is NOT for school! I''m just coding some data structures for self-practice. Anyways, I read Ron Pentons tutorials on general and binary trees and didn''t have too much of a problem with them. But I got a couple of additional questions: 1. Traversing the tree uses recursion, certainly the most straightforward method of doing it. But what if I want an iterator for the tree? I can''t use recursion anymore because I only want to move on one step when calling iterator::operator++(). I''m sure I could figure out on my own to get it working, but as far as I thought about it allot of checking would have to be done. Is there a faster way? 2. What is the best way to save a tree (with fixed-length node data) to a file? Thanks in advance! Drag0n ----------------------------- "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to build bigger and better idiots. So far, the universe is winning..." -- Rich Cook My future web presence: Dave''s Programming Resources

Share this post


Link to post
Share on other sites
Advertisement
quote:
1. ... But what if I want an iterator for the tree? I can''t use recursion anymore because I only want to move on one step when calling iterator::operator++().
It can be done with an explicit stack, but I''d be tempted to use something like:

if there is a node to the right of the current node
  move right
  while there is a node to the left of the current node, move left.
  return
else
  while the current node is to the right of its parent, move up *
  move up one more time
  return


* I''d put the conceptual "past-the-end" node above and to the right of the root node, just to simplify this.
quote:
2. What is the best way to save a tree (with fixed-length node data) to a file?
If it''s an auto-balancing BST, I''d just write the pieces of data to the file and let the tree rebalance itself when the data is read back in. For plain, unbalanced BSTs, this is a bit harder. I''d consider using some sort of stack-based system. Suppose that the notation 5(1,6) represents that the value "1" is to the left of "5", and "6" is to the right of "5". Also, suppose that 5(,6) means that "5" only has a child on the right. Then the representation of a small tree might become:

5(1(,2),6(,8(7,9)))

...this isn''t particularly human-readable, but that probably isn''t a requirement here.
quote:
...allot of checking would have to be done.
Oh dear... it''s begun...
Allot is completely different to "a lot"/"alot".

Share this post


Link to post
Share on other sites
quote:
Oh dear... it''s begun... Allot is completely different to "a lot"/"alot".


Sorry, me German!



-----------------------------
"Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to build bigger and better idiots. So far, the universe is winning..." -- Rich Cook

My future web presence: Dave''s Programming Resources

Share this post


Link to post
Share on other sites
quote:
Original post by Drag0n
2. What is the best way to save a tree (with fixed-length node data) to a file?




Preorder listing, for binary trees. First list the root. Then list all of its children on the left side, recursively. Then list all of its children on the right side, recursively.

For an arbitrary binary (not search) tree, a preorder listing that includes a marker for the leaves of the tree is enough to rebuild the tree.

For a binary search tree, that marker isn''t even necessary. You know you''ve hit a leaf when the next value is greater than the current one. Although, if there''s more than just a single tree in the stream, this requires some kind of marker (or tree total length field) to figure out where the tree stops.

For general trees, a generalized preorder listing (root, first child recursively, second child recursively, third child recursively, etc.) that includes the number of children of each node will work, as well. Note that the number of children implicitly acts as a marker for the leaf of a tree, so this form contains all the information needed to rebuild the tree.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!