The tensor complementarity problem (TCP) is a special instance of nonlinear complementarity problems (NCP) which has attracted a lot of study in recent years due to its wide applications. We introduce two novel kinds of structured tensors based on the monotonicity and P-property, respectively. The solvability of the corresponding tensor complementarity problems is discussed. We show that the solution set is nonempty and compact under some mild conditions. These results are true for the TCPs, but not for the NCPs. Based on the structure of the newly introduced tensor, we propose two classes of smoothing Newton-type algorithms for solving the corresponding tensor complementarity problems. The convergence analyses are established and preliminary numerical results show that the proposed algorithms are efficient and very promising.