It may depend on the country, but I would say in most places it is probably legal, if not particularly fair (to you).
It's quite possible that at the point you got moved, there was not enough budget for your post, so instead of making your role redundant (and thereby you) they moved you (under the guise of a restructure). Then perhaps they had a new revenue stream come in that meant they could afford that post again. If this is the case I can't see they've done anything too untoward.
Again depending on the country, some employers have strict guidelines around making posts redundant (and redeploying elsewhere). For instance, if a job becomes redundant, then the role is abolished and nobody can be employed in that role after the redundancy. There may be need to be a minimum time that the role is not in operation - which again depends on country and business type (ie public/private sector)
However, there are a few key points that need to be considered for the moral/ethical question of whether this is ok or not, that might help considering if probably legal or not.
Was the job advertised internally or externally? (either internally first and then external, or just straight to external)
Would you have been able to apply for the job yourself? (and if so, why didn't you? did you just not see it)
If the answers to both of these is yes, then I think everything is probably above board.
If either question is a no, then that's where it could start to get shaky (at least morally/ethically, if not legally)