Saving a binary search tree in a file
This pseudo-code is meant to save a binary search tree then restore it to a balanced shape:
readTree(inputFile, n)
if (n > 0){
treeNode = anew node with
null child references;
set treeNode抯 left child to
readTree(inputFile, n/2);
Read item from file into
treeNode抯 item
set treeNode抯 right child to
readTree(inputFile, (n-1)/2);
}
Can someone help me to write this in java? So far i know the parameters of the readTree() method is BufferedReader inputFile and int n, and the return type is TreeNode. But the problem im having is once i've finished with the if statemnt what do i return? Because i can't make a global root TreeNode.
[868 byte] By [
meth0da] at [2007-10-2 3:13:01]
Ok let me try to make it more specific. I have a text file which contains 10 lines of data which are numbers, ie:
10
20
30 etc...
I want to know how to read the data from the file and make a balanced binary search tree out of it. Now the pseudo-code above is what i was given to implement this but i find it vague myself. Hope this is more specific.
I think there must be more to your homework than you have described! I cannot find any logic that creates a binary tree from the algorithm you provided. The algorithm has much in common with the definition of a 'heap' but I cannot see how it would create a binary tree given the ordered set of values you have given!
Someone else will have to help because I don't think i can.
When that data is sorted to start with, there's no need to 'physically'
build a balanced, complete tree out of it. Storing all that data in an
ArrayList will do. The conceptual root of the tree can be found at
location 0. The children of a node i can be found at locations 2*i+1
and 2*i+2 if those values are < n where n is the total number of nodes
in the conceptual tree ...
kind regards,
Jos
JosAHa at 2007-7-15 21:40:06 >
> I figured it out. Thanks for you post ppl. Much appreciated. What i did
> was create two BufferedReaders, one that reads thru the data and
> checks how many lines there are and th other just reads thru the
> data. The number of lines corresponds to the number of nodes in the
> tree. After that it was all sweet.
One more minor nitpick: it isn't needed to go through that file twice;
once is enough if you use an ArrayList, i.e. don't use a fixed size
array for this.
kind regards,
Jos
JosAHa at 2007-7-15 21:40:06 >
Hey, im pretty new to java and programming in general i was wondering how to make a decision tree persistent by using preorder traversal to read a file in and inorder to reconstruct the tree, and then i know id use the above to save it
