Generating Binary Trees Lexicographically
Authors:
- F. RuskeyFRF. Ruskey
- T. C. HuTHT. C. Hu
- 1 December 1977
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 6 (4) , 745-758
Abstract
We represent a binary tree by the level numbers of its leaves from left to right. Thus every binary tree of n leaves corresponds to a sequence of n numbers. We first give the necessary and sufficient conditions for a sequence to represent a binary tree; then we give an algorithm for generating all the feasible sequences lexicographically as a list. Also, algorithms are developed to determine the position of a given sequence, or to generate the sequence of a given position. Finally, it is shown that the average time per sequence generated is constant (independent of the length of the sequence).Keywords
This publication has 1 reference indexed in Scilit:
- Optimal Computer Search Trees and Variable-Length Alphabetical CodesSIAM Journal on Applied Mathematics, 1971