Methods from nonparametric Bayesian statistics are often used to address model selection problems such as determining the number of components in a mixture model. At the heart of these methods is the Chinese restaurant process (CRP), which defines a distribution on assignments of observations to components in a way that does not limit the number of components. In this work, we expand the class of statistical models to which nonparametric Bayesian methods can be applied by defining distributions with similar properties on two kinds of structured representations: trees and binary matrices. These distributions can be used as priors in models used in a variety of applications -- anywhere data is to be explained in terms of a latent hierarchy, set of features, or bipartite graph, but the dimensionality of this latent structure is unknown. I will describe some applications to modeling text, images, and psychological data. This is joint work with David Blei, Zoubin Ghahramani, and Michael Jordan.