Permutation representation of k-ary trees

From MaRDI portal





In this paper, we study the permutation representation of k-ary trees. First, we extend the notion of traversals, from binary trees to k-ary trees. A pair of k-ary tree traversals can be used to assign a permutation of the integers 1,2,... to each k-ary tree T. A pair of traversals is a valid k-ary tree Representation Scheme (k-RS) if it does not assign the same permutation to two distinct k-ary trees. We characterize such pairs of traversals. We also characterize those k-RS which assign permutations that have their lexicographic order being consistent with some well-known 'natural' order defined on the trees they represent.











This page was built for publication: Permutation representation of k-ary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1062460)