How to restore a binary tree?

C

click_f2017-02-21 13:52:26

Programming

click_f, 2017-02-21 13:52:26

Let's say we have a linear braceless binary tree entry, which we obtained by prefix / infix / postfix traversal. How can I restore the structure of a binary tree?
Output example, vertices: abcdef...
Do I understand correctly that it will not be possible to restore the tree exactly?

Reply

Answer the question

In order to leave comments, you need to log in

1 answer(s)

M

Mercury13, 2017-02-21
@click_f

If one is prefix / infix / postfix, then, of course, no. And if there are two, the matter is already more interesting (provided, of course, that all nodes are different).
Well, for example, how to restore a tree that was traversed first prefix, then postfix (the most difficult and interesting case). I admit right away: a complete restoration is impossible, because the situations “without left sons” and “without right sons” cannot be distinguished.
If the lengths do not match, STOP: invalid data.
In a prefix bypass, the root is at the beginning, in a postfix bypass, at the end. If they are not the same, STOP: invalid data.
If there is one element in the bypass, everything is clear with this.
The second element of the prefix bypass is the left son. We are looking for it in the postfix bypass. If it is the penultimate one, we have the same situation “the tree has one son”, and we recursively run the algorithm on rounds without a root.
Otherwise, we bite out substrings of the required length (real or virtual), run the algorithm recursively twice.
Example: we have a tree.

     a
  b    c
d  e   f

Prefix bypass abdecf, postfix debfca. The root is a, the left son of b, it is in the postfix bypass in the third position. Recursively run the algorithm on pairs bde/deb and cf/fc.