On Generating All Binary Trees

Issue title: New Frontiers in Scientific Discovery – Commemorating the Life and Work of Zdzislaw Pawlak

Article type: Research Article

Authors: Skarbek, Władysław

Affiliations: Faculty of Electronics and Information Technology, Warsaw University of Technology, Nowowiejska 16/19, 02-665 Warszawa, Poland. E-mail: [email protected]

Abstract: In context of Pawlak's machine a general iterative meta scheme for generating of combinatorial objects is introduced and applied to proof the correctness of ASR (Arm Switching and Rotation) algorithm generating all binary trees on k nodes. The average time complexity of the ASR algorithm and B* are analyzed and compared to the B algorithm discussed by Knuth. The analyzed algorithms are all obtained by various natural correspondences from author's DCP (Degrade and Compress Path) algorithm for generating all ordered trees on k+1 nodes.

Keywords: Pawlak' machine, binary tree, ordered tree, generating trees

Journal: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 505-536, 2007