I need to find a recursive build tree implementation in java.  Can't figure it out for the life of me.  Some hints are below. But I can't figure it out.

A few more hints on how buildTree() should work.

If the size is 1, it creates the leaf node and simply passes a pointer to it to the calling function (i.e., its parent, as explained shortly).

If the size is >1, then we are at a node that has at least one child. This node must first determine (from the two traversals) how many children it has, and for each of the children, the size of their subtrees (and the corresponding pre start and poststart values), where the size of a child's subtree includes the child itself.

For instance, the initial call the tree with D as root would be:

buildTree(15, 0, 0).

Since, 15>1, this call knows that it must build the node for D (since it is the first in the pre-order and last in post-order, and must now find the number of children that D has. 

Parsing the preorder traversal, the first node after D, i.e., H, is the leftmost child of D. In postorder traversal, all nodes in H's subtree are visited before H, so scanning the postorder traversal from poststart (=0) until we encounter H, we find that H's subtree has 12 nodes, including H. returning to the preorder traversal, the 12 nodes after D are the ones in H's subtree. Hence, the following node (Q) is the second child of D. Returning to the postorder, we similarly realize that Q's subtree contains itself and N. Since the preorder traversal ends at N, we now know that D only has two children, H and Q, and their subtrees are of size 12 and 2, respectively.

Now, for each of the two children, D will call buildTree() recursively, and each call will build the corresponding child and return a pointer to it. Then, D (i.e., the initial buildTree call) will build a node for itself that will include the pointers returned by the two recursive calls as the pointers to each of its two children. Finally, this call will use the child pointers to set the parent pointers at each child to itself.

The first recursive call of buildTree() to construct the subtree rooted at H will be:

buildTree(12, 1, 0)

prestart is set to 1, since this is where the pre-order traversal of H's subtree starts, and poststart is set to 0, since this is where the post-order traversal of the same subtree starts. 

The second call will be:

buildTree(2, 13, 12)

The values of the prestart and poststart arguments in the two calls above are determined while the two traversals are parsed to find D's children.

The recursive calls will only parse the part of the two traversals that are indicated by the prestart an psostart values passed to them. For instance, the first of the two recursive calls above:

buildTree(12, 1, 0)

will realize that the node it needs to build is the one in pretrav[1], i.e., H, and hence, it will only consider the part of posttrav array from position poststart=0 until H is located.

This call, nut then find the children of H, similarly to how this was done for D above. The node following H in pre-order, B, is the leftmost child. Parsing the post-order traversal, we determine that B's subtree has 5 nodes, including B -- and this is the size that will be used when buildTree is called recursively to build B. We then count five nodes down the pre-order traversal, and we find the next (middle) child of H as T. Parsing the post-oirder from B to T we find that T's subtree has three nodes. Returning to pre-order, we count three nodes from T, and we obtain the next child of H, C. Looking then at the post-order, we determine that C's subtree has three nodes, and that H does not have any other child.

This repeats, until we reach leaf nodes.

 

CSC 316– Data StructuresProgramming Project #2 – Family Trees and RelationshipsDue Date:March 2, 2016, 11:59pmProject ObjectivesWith this project you will construct a representation of a family tree from listings of its nodes inpreorder and postorder, then answer questions about relationships of pairs of individuals (nodes)in the tree. The objectives of the project are to:•implement a general tree data structure and the tree ADT operations; and•gain experience with recursion by writing a recursive procedure to construct the tree from itspreorder and postorder traversals.Input and OutputTypical input for the project will be:< D, H, B, G, M, W, F, T, X, Z, C, R, P, Q, N.> G, M, W, F, B, X, Z, T, R, P, C, H, N, Q, D.?D, H.?W, T.?N, F.With this input, your program will construct a representation of the following tree:FDHQNCRPTXZBGMW

Attachments:

• 1495789669-proj2.pdf