For $k\geq 0$, a $k$-generalized Markov number is an integer which appears in some positive integer solution to the $k$-generalized Markov equation $x^2 + y^2 + z^2 + k(yz + zx + xy) = (3 + 3k)xyz$. In this paper, we discuss a combinatorial structure of generalized Markov numbers. To investigate this structure in detail, we use two families of matrices: the $k$-generalized Cohn matrices and the $k$-Markov-monodromy matrices, which are elements of $SL(2, \mathbb{Z})$ whose $(1,2)$-entries are $k$-generalized Markov numbers. We show that these two families of matrices recover the tree structure of the positive integer solutions to the generalized Markov equation, and we give geometric interpretations and a combinatorial interpretation of $k$-generalized Markov numbers. As an application, we provide a computation algorithm of classical Markov number from a one-dimensional dynamical viewpoint. Moreover, we clarify a relation between $k$-generalized Markov numbers and toric surface singularities via continued fractions.