Binary Tree help please?

So we were given a problem set, and I'm stuck to a pair of problems. Basically, from a preorder, inorder or postorder sequences, we're given two from them and draw a binary tree from it.





I think posting the pic might make it clearer:


http://img174.imageshack.us/img174/6193/...





So, like, for the first one we're given a preorder and inorder set. I've been doing good so far till I narrowed it to four nodes, but from there, I'm completely stuck. I've tried everything. Everything. I still can't draw them. It was worse for the second binary tree.





Is there a standard "procedure" of doing it? So far I've only done them through trial and error and a lot of gut feeling.





===





Another question, in our machine problem we were tasked to make a binary tree generator. A simple question: Do I need to write a BinaryTree struct? We use C. In the sample our book I didn't see a BinaryTree struct, not even a root pointer. How do I initialize a tree by code?

Binary Tree help please?
First off, the first problem in your first question looks wrong, AFAIK. You're using the sequence you call "postorder" as an inorder sequence. Also, if I'd use it as postorder, I'd get stuck too (mostly because the first sequence starts with G, but the second sequence doesn't end with G).





A standard procedure would involve recursive splitting of the sequences. After you find out what the root of the 'current' (sub)tree is, you just split up the sequence into a left and right subtree and solve them separately.





So, for the first problem, let's assume you have a pre- and inorder sequence. You know that G is the root, because preorder starts with it. All symbols before the G in the inorder (WREKNL) are on the left side of G. So on the left side of G, you have WREKNL, on the right side you have ODTAIH.





- Left of G: pre = LWNERK, in = WREKNL. You know that this subtree has L as root. By looking at the inorder, you notice that all other symbols are on the left side of L. So left of L you have WNERK, right of L you have nothing.


- Left of L: pre = WNERK, in = WREKN. The opposite: W is the current node/root, and all other symbols are on the right.


- Right of W: pre = NERK, in = REKN. Current is N, left is ERK, right is none.


- Left of N: pre = ERK, in = REK. Current is E, left is R, right is K.





- Right of G: pre = OITDAH, in = ODTAIH. Current is O, all are right.


- Right of O: pre = ITDAH, in = DTAIH. Current is I, left is DTA, right is H.


- Left of I: pre = TDA, in = DTA. Current is T, left is D, right is A.





And that's it. You should solve the second one likewise, but here you have an inorder and a postorder sequence. You can use the inorder sequence the same way as above, but you'll have to look at the last symbol in the postorder sequence to know what the current node is.





If you have a pre- and postorder sequence, things will work differently. One way to solve it goes as follows:


0) While the sequences are not empty:


1.1) Look at the first symbol X of the preorder sequence.


1.2) Find X in the postorder sequence. Take all symbols up to it as subsequence S_post (and chop off X).


1.3) Take all symbols in S_post from the preorder sequence as S_pre (and chop off X).


1.4) Remember triplet (X, S_pre, S_post).


2) For each triplet (X, S_pre, S_post) we remember, insert node X into the current node and parse S_pre and S_post for that node.





So as an example, lets solve


pre = ABCEDGFHJI


post = EGFDCBJIHA





- Inside roots: A (S_pre = BCEDGFHJI, S_post = EGFDCBJIH) is the only child (well, yeah, it's the root).


- Inside A: B (CEDGF, EGFDC) and H (JI, JI) are children.


- Inside B: C (EDGF, EGFD) is the only child.


- Inside C: E (leaf) and D (GF, GF) are children.


- Inside D: G (leaf) and F (leaf) are children.


- Inside H: J (leaf) and I (leaf) are children.











To answer your second question: you need a struct, because you have more than one fields per item (namely, a left pointer, a right pointer and (optionally) a node/leaf value).