Re: [algogeeks] Re: Saving and restoring Binary trees in files
@Don : +1 ..got it ..thanks
On Wed, Nov 13, 2013 at 10:35 PM, Dave wrote:
> @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 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 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 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.
>
--
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.
Re: [algogeeks] Re: Saving and restoring Binary trees in files
@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 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 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 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.
Re: [algogeeks] Re: Saving and restoring Binary trees in files
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 >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 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 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.
Re: [algogeeks] Re: Saving and restoring Binary trees in files
@don : i did not get it , what will be data in file?
On Mon, Nov 11, 2013 at 10:14 PM, Don 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 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 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+unsubscr...@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.
Re: [algogeeks] Re: Saving and restoring Binary trees in files
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 > 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 >
> 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+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Saving and restoring Binary trees in files
@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 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 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+unsubscr...@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+unsubscr...@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.
Re: [algogeeks] Re: Saving and restoring Binary trees in files
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 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+unsubscr...@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+unsubscr...@googlegroups.com.
[algogeeks] Re: Saving and restoring Binary trees in files
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+unsubscr...@googlegroups.com.
