EFFICIENT GENERATION OF K-ARY TREES IN NATURAL ORDER

被引：21
作者：
ER, MC
机构：
[1] Department of Mathematics and Computing Sciences, St. Francis Xavier University, Antigonish
来源：
COMPUTER JOURNAL | 1992年 / 35卷 / 03期
关键词：
D O I：
10.1093/comjnl/35.3.306
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
A k-ary tree with n nodes can be encoded as a k-inorder-preorder sequence of length (k - 1) n by labelling the tree from 1 to (k - 1) n in generalised inorder and then reading off the labelled integers in generalised preorder. The natural ordering of a set of k-ary trees with n nodes is shown to be preserved in the lexicographic ordering of a set of k-inorder-preorder sequences of length (k - 1) n. An efficient algorithm for generating a set of k-inorder-preorder sequences in lexicographic order is presented. This set of k-inorder-preorder sequences can subsequently be converted to the corresponding set of k-ary trees in natural order.
引用
收藏
页码：306 / 308
页数：3
相关论文
共 50 条
[41]   Non-blocking k-ary search trees [J].
Theory Group, Dept. of Computer Science, University of Toronto, Canada ;
不详 .
Lect. Notes Comput. Sci., (207-221)
[42]   Non-blocking k-ary Search Trees [J].
Brown, Trevor ;
Helga, Joanna .
PRINCIPLES OF DISTRIBUTED SYSTEMS, 2011, 7109 :207-+
[43]   Generation of assembly sequences with k-ary operations [J].
Wang, Haixia ;
Ceglarek, Dariusz J. .
2007 IEEE INTERNATIONAL SYMPOSIUM ON ASSEMBLY AND MANUFACTURING, 2007, :50-+
[44]   Counting Vertices with Given Outdegree in Plane Trees and k-ary Trees [J].
Rosena R. X. Du ;
Jia He ;
Xueli Yun .
Graphs and Combinatorics, 2019, 35 :221-229
[45]   Counting Vertices with Given Outdegree in Plane Trees and k-ary Trees [J].
Du, Rosena R. X. ;
He, Jia ;
Yun, Xueli .
GRAPHS AND COMBINATORICS, 2019, 35 (01) :221-229
[46]   LOOPLESS GENERATION OF K-ARY TREE SEQUENCES [J].
KORSH, JF .
INFORMATION PROCESSING LETTERS, 1994, 52 (05) :243-247
[47]   Efficient Removal of Divisors in the k-ary Algorithm [J].
Enikeev, R. R. .
UCHENYE ZAPISKI KAZANSKOGO UNIVERSITETA-SERIYA FIZIKO-MATEMATICHESKIE NAUKI, 2019, 161 (03) :393-404
[48]   Embedding of k-ary complete trees into hypercubes with uniform load [J].
Trdlicka, J ;
Tvrdik, P .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1998, 52 (02) :120-131
[49]   SELF-ADJUSTING K-ARY SEARCH-TREES [J].
SHERK, M .
LECTURE NOTES IN COMPUTER SCIENCE, 1989, 382 :381-392
[50]   A Subfamily of Skew Dyck Paths Related to k-ary Trees [J].
Zhang, Yuxuan ;
Zhuang, Yan .
JOURNAL OF INTEGER SEQUENCES, 2024, 27 (02)
12345