Numbering binary trees with labeled terminal vertices

Abstract

For each rooted binary tree with t labeled terminal vertices (leaves) a natural number can be assigned uniquely. Unrooted trees with t labeled terminal vertices and t-2 unlabeled internal vertices of degree 3 can also be numbered uniquely using the same convention. Rooted trees in which the hights of the internal vertices are rank ordered are also considered. Applications to problems in taxonomy are discussed. © 1983 Society for Mathematical Biology.