@Don: Excellent solution. It requires little extra data to be stored, and
it is easy to implement.
Dave
On Wednesday, November 13, 2013 9:31:47 AM UTC-6, Don wrote:
> The data file contains the pre-order traversal. For each node indicate the
> contents of the node and two bits to indicate if it has a left and/or right
> subtree. I did this with a tree containing strings. Each node was one line
> in the file, with the first character being 'A' if the node is a leaf, 'B'
> if it has only a left subtree, 'C' if it has only a right subtree, and 'D'
> if it has both left and right subtrees. Then you read the line, store the
> string minus the first character, and recursively build the left and then
> right subtree, as appropriate.
>
> Don
>
> On Monday, November 11, 2013 1:20:05 PM UTC-5, atul007 wrote:
>>
>> @don : i did not get it , what will be data in file?
>>
>>
>> On Mon, Nov 11, 2013 at 10:14 PM, Don <dond...@gmail.com> wrote:
>>
>>> Save in preorder, tagging each node with two bits indicating if that
>>> node has a left and right subtree.
>>>
>>> Then rebuild like this:
>>>
>>> Tree rebuild()
>>> {
>>> Tree result = readNode();
>>> Tree->left = hasLeftSubtree ? rebuild() : 0;
>>> Tree->right = hasRightSubtree ? rebuild() : 0;
>>> return result;
>>>
>>> }
>>>
>>> On Friday, November 8, 2013 1:00:35 PM UTC-5, atul007 wrote:
>>>
>>>> @don : it is not BST , it is binary tree ...so your approach will
>>>> not work in this case.
>>>>
>>>> @kumar : save pre-order and in-order traversal with some delimiter in
>>>> b/w traversals.
>>>>
>>>> pre-order : a b c d e
>>>> in-order : c b e a d
>>>>
>>>> write in file :-
>>>>
>>>> a b c d e # c b e a d
>>>>
>>>> now use pre-order and in-order traversal to re-create binary tree.
>>>>
>>>> 2) consider null node as "#" ..now write in file preorder traversal.
>>>>
>>>> for eg : a b c # # # d # #
>>>>
>>>> 3) save level order traversal of binary tree, where each level uses
>>>> "#" to distinguish between levels and "*" to mark null nodes
>>>> eg : a # b c # e *
>>>> a - level 1
>>>> b c - level 2
>>>> e NULL - level 3
>>>>
>>>> shortcoming in 2 and 3 is use of character that can be part of tree
>>>> itself.So if node can contain "#" then you have to use some other
>>>> character to distinguish.
>>>>
>>>> for solution 1 , you can write traversal in 2 lines instead of using
>>>> "#"
>>>>
>>>> On 11/8/13, Vishnu <vish...@gmail.com> wrote:
>>>> > 1) save the nodes(value, left and right pointer) in pre-order
>>>> traversal
>>>> > 2) also save pointers of all node in same order
>>>> >
>>>> > to restore
>>>> > 1) create new N nodes
>>>> > 2) do pointer mapping from old -> new
>>>> > 3) restore nodes and replace old pointers to new
>>>> >
>>>> >
>>>> > On Fri, Nov 8, 2013 at 8:50 PM, Don <dond...@gmail.com> wrote:
>>>> >
>>>> >> Save it in pre-order.
>>>> >> Rebuild by inserting nodes in the order they occur in the file.
>>>> >>
>>>> >>
>>>> >> On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote:
>>>> >>>
>>>> >>> What is the effective way to save and restore the binary trees to
>>>> files
>>>> >>> effectively?
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>> Regards,
>>>> >>> Kumar Raja.
>>>> >>>
>>>> >> --
>>>> >> You received this message because you are subscribed to the Google
>>>> Groups
>>>> >> "Algorithm Geeks" group.
>>>> >> To unsubscribe from this group and stop receiving emails from it,
>>>> send an
>>>> >> email to algogeeks+...@googlegroups.com.
>>>> >>
>>>> >
>>>> >
>>>> >
>>>> > --
>>>> > Thanks,
>>>> > Vishnu
>>>> >
>>>> > --
>>>> > You received this message because you are subscribed to the Google
>>>> Groups
>>>> > "Algorithm Geeks" group.
>>>> > To unsubscribe from this group and stop receiving emails from it,
>>>> send an
>>>> > email to algogeeks+...@googlegroups.com.
>>>> >
>>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+...@googlegroups.com.
>>>
>>
>>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
