Loopless Generation of Non-regular Trees with a Prescribed Branching Sequence1

被引：14

作者：

Wu, Ro-Yu ^{[3
]}

Chang, Jou-Ming ^{[2
]}

Wang, Yue-Li ^{[1
]}

机构：

[1] Natl Taiwan Univ Sci & Technol, Dept Informat Management, Taipei, Taiwan

[2] Natl Taipei Coll Business, Dept Informat Management, Taipei, Taiwan

[3] Lunghwa Univ Sci & Technol, Dept Ind Management, Tao Yuan, Taiwan

来源：

COMPUTER JOURNAL | 2010年 / 53卷 / 06期

关键词：

non-regular trees; coding trees; gray-code generation; loopless algorithms; K-ARY TREES; BINARY-TREES; GRAY CODES; ALGORITHM; ROTATIONS; ORDER;

D O I：

10.1093/comjnl/bxp015

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

An ordered tree is called a non-regular tree with a prescribed branching sequence (or non-regular tree for short) if its internal nodes have a prespecified degree sequence in preorder list. We define a concise representation, called right distance sequences to describe such trees. A coding tree helps us to systematically investigate the structural representation of non-regular trees. Consequently, we present a loopless algorithm to generate Gray-codes of non-regular trees using right distance sequences.

引用

页码：661 / 666

页数：6

共 25 条

[1] LOOPLESS ALGORITHMS FOR GENERATING PERMUTATIONS, COMBINATIONS, AND OTHER COMBINATORIAL CONFIGURATIONS [J].

EHRLICH, G .

JOURNAL OF THE ACM, 1973, 20 (03) :500-513

[2] A SIMPLE ALGORITHM FOR GENERATING NON-REGULAR TREES IN LEXICOGRAPHIC ORDER [J].

ER, MC .

COMPUTER JOURNAL, 1988, 31 (01) :61-64

[3] NUMBERING SYSTEM FOR BINARY TREES [J].

KNOTT, GD .

COMMUNICATIONS OF THE ACM, 1977, 20 (02) :113-115

[4]

Knuth D. E., 2006, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All TreesHistory of Combinatorial Generation, V4

[5] Loopless generation of Gray codes for k-ary trees [J].

Korsh, JE ;

LaFollette, P .

INFORMATION PROCESSING LETTERS, 1999, 70 (01) :7-11

[6] Shifts and loopless generation of k-ary trees [J].

Korsh, JF ;

Lipschutz, S .

INFORMATION PROCESSING LETTERS, 1998, 65 (05) :235-240

[7] LOOPLESS GENERATION OF K-ARY TREE SEQUENCES [J].

KORSH, JF .

INFORMATION PROCESSING LETTERS, 1994, 52 (05) :243-247

[8] ON ROTATIONS AND THE GENERATION OF BINARY-TREES [J].

LUCAS, JM ;

VANBARONAIGIEN, DR ;

RUSKEY, F .

JOURNAL OF ALGORITHMS, 1993, 15 (03) :343-366

[9] A NOTE ON GENERATING BINARY-TREES IN A-ORDER AND B-ORDER [J].

PALLO, J ;

RACCA, R .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1985, 18 (01) :27-39

[10] ENUMERATING, RANKING AND UNRANKING BINARY-TREES [J].

PALLO, JM .

COMPUTER JOURNAL, 1986, 29 (02) :171-175

← 1 2 3 →