A Multi-tenant cellular network is a paradigm where the physical infrastructure of the network is leased by various big industries, e.g., power utilities and transportation. Hence, a major challenge in a multi-tenant cellular network is the efficient allocation of the physical spectrum to various tenants with broadly distinct Quality-of-Service (QoS) requirements and communications traffic characteristics. In this paper, we approach this issue by presenting a versatile spectrum sharing scheme, which may be deployed to model any spectrum sharing strategy between various tenants in a multi-tenant cellular network. The proposed spectrum sharing scheme is based upon a queuing system that considers the various communications traffic characteristics of the tenants. In addition, by using the developed queuing system, mathematical expressions for the blocking probability and spectrum utilisation are derived.We then propose an optimal spectrum planning scheme, referred to as Reservation-Based Sharing (RBS) policy, that maximises the spectrum utilisation by allocating the spectrum resources to various tenants according to their traffic loads. The computational complexity of the optimal RBS policy is reduced by developing a learning automata technique, referred to as pursuit learning based RBS policy. By using real traffic parameters for various tenants, the results show that the simulation and analytical results match well, ensuring the accuracy of the proposed analytical model. Moreover, the results indicate that the proposed pursuit learning based RBS policy firmly matches the optimal solution and delivers a higher spectrum utilisation that increases linearly with the number of tenants.