We examine the microstructural and mechanical changes which occur during oscillatory shear flow and reformation after flow cessation of an intermediate volume fraction colloidal gel using rheometry and Brownian Dynamics (BD) simulations. A model depletion colloid-polymer mixture is used, comprising a hard sphere colloidal suspension with the addition of non-adsorbing linear polymer chains. The results reveal three distinct regimes depending on the strain amplitude of oscillatory shear. Large shear strain amplitudes fully break the structure which results in a more homogenous and stronger gel after flow cessation. Intermediate strain amplitudes densify the clusters and lead to highly heterogeneous and weak gels. Shearing the gel to even lower strain amplitudes creates a less heterogonous stronger solid. These three regimes of shearing are connected to the microscopic shear-induced structural heterogeneity. A comparison with steady shear flow reveals that the latter does not produce structural heterogeneities as large as oscillatory shear. Therefore oscillatory shear is a much more efficient way of tuning the mechanical properties of colloidal gels. Moreover, colloidal gels presheared at large strain amplitudes exhibit a distinct nonlinear response characterized largely by a single yielding process while in those presheared at lower rates a two-step yielding process is promoted due to the creation of highly heterogeneous structures.