@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 [email protected]. >>>> >> >>>> > >>>> > >>>> > >>>> > -- >>>> > 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 [email protected]. >>>> > >>>> >>> -- >>> 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 [email protected]. >>> >> >> -- 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 [email protected].
