GENERATING BINARY-TREES BY TRANSPOSITIONS

被引：35

作者：

RUSKEY, F

PROSKUROWSKI, A

机构：

[1] UNIV VICTORIA,DEPT COMP SCI,VICTORIA V8W 2Y2,BC,CANADA

[2] UNIV OREGON,DEPT COMP & INFORMAT SCI,EUGENE,OR 97403

来源：

JOURNAL OF ALGORITHMS | 1990年 / 11卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1016/0196-6774(90)90030-I

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let T(n) denote the set of all bitstrings with n 1's and n 0's that satisfy the property that in every prefix the number of 0's does not exceed the number of 1's. This is a well known representation of binary trees. We consider algorithms for generating the elements of T(n) that satisfy one of the following constraints: (a) successive bitstrings differ by the transposition of two bits or (b) successive bitstrings differ by the transposition of two adjacent bits. In case (a) a constant average time generation algorithm is presented. In case (b) we show that such generation is possible if and only if n is even or n < 5. A constant average time algorithm is presented in this case as well. © 1990.

引用

页码：68 / 84

页数：17

共 21 条

[1] EFFICIENT GENERATION OF BINARY REFLECTED GRAY CODE AND ITS APPLICATIONS [J].