It seems that you think that we want to perform classification with VAEs or that images that we pass to the encoder fall into more than one category. The other answer already points out that VAEs are not typically used for classification but for generation tasks, so let me try to answer the main question.
The variational auto-encoder (VAE) and the (deterministic) auto-encoder both have an encoder and a decoder and they both convert the inputs to a latent representation, but their inner workings are different: a VAE is a generative statistical model, while the AE can be viewed just as a data compressor (and decompressor).
In an AE, given an input $\mathbf{x}$ (e.g. an image), the encoder produces one latent vector $\mathbf{z_x}$, which can be decoded into $\mathbf{\hat{x}}$ (another image which should be similar or related to $\mathbf{x}$). Compactly, this can be presented as $\mathbf{\hat{x}}=f(\mathbf{z_x}=g(\mathbf{x}))$, where $g$ is the encoder and $f$ is the decoder. This operation is deterministic: so, given the same $\mathbf{x}$, the same $\mathbf{z_x}$ and $\mathbf{\hat{x}}$ are produced.
In a VAE, given an input $\mathbf{x} \in X$ (e.g. an image), more than one latent vector, $\mathbf{z_{x}}^i \in Z$, can be produced, because the encoder attempts to learn the probability distribution $q_\phi(z \mid x)$, which can be e.g. $\mathcal{N}(\mu, \sigma)$, which we can sample from, where $\mu, \sigma = g_\theta(\mathbf{x})$. In practice, $g_\theta$ is a neural network with weights $\phi$. We can sample latent vectors $\mathbf{z_{x}}^i$ from $\mathcal{N}(\mu, \sigma)$, which should be "good" representations of a given $\mathbf{x}$.
Why is it useful to learn $q_\phi(z \mid x)$? There are many uses cases. For example, given multiple corrupted/noisy versions of an image, you can reconstruct the original uncorrupted image. However, note that you can use the AE also for denoising. Here you have a TensorFlow example that illustrates this. The difference is is that, again, given the same noisy image, the model will always produce the same reconstructed image. You can also use the VAE for drug design [1]. See also this post.
