Ground-penetrating radar (GPR) has vast application potential for the root system testing of fruit trees and ancient trees. The clutter in GPR B-scan image often obscures the tree roots, thus reduces the accuracy of tree-root localization algorithm. A tree-root localization method combining robust deep autoencoder (RDAE), direct least square (DLS) and frequency-wavenumber migration (FKM) was proposed. Firstly, after performing time-zero correction, a GPR B-scan image was decomposed into its low-rank and sparse components by RDAE. The low-rank component represented the clutter, and the sparse component represented the response of the tree roots. Secondly, the dielectric constant of soil was estimated by fitting the target echo’s hyperbolic curve with the direct least square method. Finally, the migration velocity was calculated according to the dielectric constant of soil, and then the migration velocity was taken as the input of frequency-wave number migration to get the radius and depth information of the tree-root. Experimental results showed that compared with the common clutter suppressed methods, including mean subtraction (MS), singular value decomposition (SVD), and robust principal component analysis (RPCA), RDAE had a better visual effect and higher signal-to-clutter ratio and improvement factor on both numerical simulated data and real GPR data. The root-mean-square relative error (RMSRE) value of the estimated dielectric constant of soil was 3.84%. The maximum radius relative error and the maximum depth relative error were 8.5% and 8.7%, respectively. The proposed method can meet the practical requirements of the tree-root non-destructive testing and provide decision support for tree health management and transplantation.