Decision Trees (DTs) provide an attractive classification scheme because clinicians responsible for making reliable decisions can easily interpret them. Bayesian averaging over DTs allows clinicians to evaluate the class posterior distribution and therefore to estimate the risk of making misleading decisions. The use of Markov Chain Monte Carlo (MCMC) methodology of stochastic sampling makes the Bayesian DT technique feasible to perform. The Reversible Jump (RJ) extension of MCMC allows sampling from DTs of different sizes. However, the RJ MCMC process may become stuck in a particular DT far away from the region with maximal posterior. This negative effect can be mitigated by averaging the DTs obtained in different starts. In this paper we describe a new approach based on an adaptive sampling scheme. The performances of Bayesian DT techniques with the restarting and adaptive strategies are compared on a synthetic dataset as well as on some medical datasets. By quantitatively evaluating the classification uncertainty, we found that the adaptive strategy is superior to the restarting strategy.