Thread: Binary Tree - Reading From and Writing to a File

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    1

    Binary Tree - Reading From and Writing to a File

    Hello. I was curious if anyone had any suggestions for writing a random binary tree(no specific height, unbalanced) to a file, that would make it extremely easy to read from a file? Currently, I have an extremely simply recursive function that writes it to a file in inorder. Of course, the problem with that is that I can't just simple read it back, or else the height of my tree could be altered. Should I write it to a file in two orders, and develop an algorithm that compares the orders to make the correct tree? Or is there something easier?

    Thanks,
    Ctank02

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Using two different orderings works (we had someone here not too terribly long ago who was reconstructing trees from inorder and postorder). I also think that you can make preorder work for you, if you are willing to print a NIL or some sentinel value for an empty node:
    Code:
        1
      2   3
    4  5 6 7
      8
    might come out as 1 2 4 nil nil 5 8 nil nil nil 3 6 nil nil 7 nil nil. You should be able to reconstruct the tree from that.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Do you need to maintain the exact same parent/child relationships when loading from the file? If so, use the preorder with sentinels tabstop suggested.

    If it would be okay for the tree to be more balanced when you read it in than it was when you wrote it out, then that can be accomplished rather easily by simply writing it out inorder and building a linked list that you process back into a tree after loading.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed