A Study On Enumerating Binary Trees

Binary trees are the most fundamental and important data structures used in computer science. As such, the problem of enumerating binary trees is of great interest from both theoretical and practical point of view.Enumerating trees has two meanings. One is counting, that is determining the number of some kind of trees. It is well known that the Catalan Number C_n is the number of binary trees with n nodes.The other is generating, which means listing all the trees having same property one by one.In this paper, we first introduce four categories of coding algorithms for generating binary trees. We will compare some of the algorithms using the number of recursive calls to enumerate C_n sequences as a measure of time complexity.We make a father discussion on P-Sequences which is a coding method following the general scheme. We give a recursive algorithm and compare the executive time, finding that our recursive algorithm is more than 1.5 times efficient of which presented by H.Ahrabian. A non-recursive algorithm is alse presented, which is more efftcient.The binary trees can be constructed in typical local order according to this non-recursive algorithm.Heap is an important binary tree structure often used in applications concerned with priority queues and partial ordering such as Sorting, Shortest Paths, Task Schedule, and Minimum Spanning Tree. So enumerating heaps is of great interest.We first make a survey of different kinds of heap structures. Then we introduce a property of Max-heaps recently discovered and an algorithm generating Max-heaps based on the property.At the end of this paper, we study the problem of counting Max-heaps. After introducing the existed methods of counting heaps firstly, we put forward the counting formula of Max-heaps based on the process of generating Max-heaps, and give a simple and efficient algorithm realizing the counting formula. This new algorithm has following advantages compared with other algorithms:1. Time complexity of other algorithms is not liner function of n. On contrast, the new algorithm can be implemented without recurrence.Its time complexity is O(n).2. The new algorithm only needs an array whose size is n, so the space complexity is O(n).