You could probably do this using the Easy Populate module (EP version 1.2.5.4)

Install the module.

Run it to EXPORT a full list of products

Delete the products in your database.

In your Easy Populate "spreadsheet", add the sub-categories before you re-load the data into the webshop.