Generating binary trees of bounded height

DOI10.1007/BF00288468MaRDI QIDQ1064071zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1986

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00288468

zbMATH Keywords

algorithmencoding scheme for binary treesinternal nodes

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Review text

We present a new encoding scheme for binary trees with n internal nodes whose heights are bounded by a given value h, \(h\geq \lceil \log_ 2(n+1)\rceil\). The scheme encodes the internal nodes of the tree level by level and enables us to develop an algorithm for generating all binary trees within this class in a certain predetermined order. Specifically, the trees are generated in decreasing height and for trees of the same height they are generated in lexicographically increasing order. The algorithm can be easily generalized to encompass t-ary trees with bounded height. It is then shown that the average generation time per tree is constant (independent of n and h).

Recommendations

• Generating t-ary trees in A-order
• Generation of binary trees from (0-1) codes
• Generating binary trees using rotations
• A linear-time algorithm for the generation of trees
• Generating ordered trees

Cites work

• A numbering system for binary trees
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• Centers of 2–Trees
• Constant Time Generation of Rooted Trees
• Generating t-Ary Trees Lexicographically
• Generating Binary Trees Lexicographically
• Generating Trees and Other Combinatorial Objects Lexicographically
• Generation of Binary Trees from Ballot Sequences
• Lexicographic generation of ordered trees
• Limit distributions for coefficients of iterates of polynomials with applications to combinatorial enumerations
• Ranking and Listing Algorithms for k-Ary Trees
• Ranking and Unranking of 2-3 Trees
• Ranking and unranking of B-trees

Cited in

(11)

• Generating binary trees by Glivenko classes on Tamari lattices
• A loopless algorithm for generating binary tree sequences
• On generating B-trees with constant average delay and in lexicographic order
• Uniform generation of forests of restricted height
• scientific article; zbMATH DE number 1823192 (Why is no real title available?)
• Ranking and Unranking of Non-regular Trees
• Generating trees withnnodes andmleaves
• On the generation of binary trees from (0–1) codes
• scientific article; zbMATH DE number 1751212 (Why is no real title available?)
• Tables
• Algorithms for media

This page was built for publication: Generating binary trees of bounded height

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