A Note on Enumerating Binary Trees.

Abstract

Algorithms have been presented for computing a bijection between the set of binary trees on n nodes and an initial segment of the positive integers. A more complicated algorithm was also presented that computes a different bijection, claiming that their algorithm is more efficient and has advantages if a sequence of several consecutive trees is required. A modification of the first algorithm is presented that is simpler than the first and as efficient as the second. Also given is a new linear-time algorithm for transforming a tree into its successor in the natural ordering of binary trees.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1979
Accession Number
ADA068900

Entities

People

  • Marvin Solomon
  • Raphael A. Finkel

Organizations

  • University of Wisconsin–Madison

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computer Programming
  • Computing-Related Activities
  • Continents
  • Databases
  • Generators
  • Mathematics
  • Military Research
  • North Carolina
  • Permutations
  • Probability
  • Sequences
  • Statistics
  • Trees (Data Structures)
  • United States
  • Universities

Fields of Study

  • Mathematics

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.