That’s expected. WP doesn’t build in redirects from old permalink structures to new, since the before and the after could be so many different ways. You’ll need to add your own redirects, which will have to be done one by one, since there’s no way for the server to tell what category any given post is in.
If you’re using Apache, you can do this in .htaccess, above WP’s own rules. You’ll want 301 permanent redirects, and in .htaccess you set that up with the old relative path, followed by the new absolute path.
Redirect 301 /apples/ https://example.com/fruit/apples/