How to delete terms on plugin deactivate?

I recommend not deleting the terms at the point of deactivation.

Instead why don’t you delete the terms at the point of uninstallation?

You can use the uninstall hook: http://codex.wordpress.org/Function_Reference/register_uninstall_hook

Or bypass that.

The plugin should create a file named ‘uninstall.php’ in the base plugin folder. This file will be called, if it exists, during the uninstall process bypassing the uninstall hook.

This may be easier to manage code wise and sometimes people would like to deactivate a plugin and not lose all their data.