You can use this query to generate the RewriteRules that you will need. Once generated the would go into your .htaccess file and need to be prepended with:
RewriteEngine On
RewriteBase /
The following SQL output should setup rewrite rules for /postname/ to /category/postname/ based on what is in your database now. The trailing forward slash is optional.
SET SESSION group_concat_max_len = 1000000; -- make sure we can hold all the redirects
SELECT GROUP_CONCAT(CONCAT('RewriteRule ^', post_name, '/?$ ', t.slug, "https://wordpress.stackexchange.com/", post_name, '/ [R=301,L]') SEPARATOR '\n') redirects
FROM {$wpdb->posts} p
JOIN {$wpdb->term_relationships} tr ON p.ID = tr.object_id
JOIN {$wpdb->term_taxonomy} tt ON tt.term_taxonomy_id = tr.term_taxonomy_id AND tt.taxonomy = 'category'
JOIN {$wpdb->terms} t ON tt.term_id = t.term_id
The output will be similar to to following:
RewriteRule ^atlanta-falcons/?$ random/atlanta-falcons/ [R=301,L]
RewriteRule ^passion-flower-pistil-negative/?$ photos/passion-flower-pistil-negative/ [R=301,L]
RewriteRule ^crane-takeoff/?$ photos/crane-takeoff/ [R=301,L]