二元樹和t元樹的列舉問題在許多論文中常被探討，二元樹和t元樹都叫作規則樹，過去的許多研究都使用整數序列來表示規則樹，也產生了各種的演算法，使這些序列在辭彙編纂方式下，能夠有效率地產生。
本篇論文我們主要著眼於多元樹的探討，多元樹就是每個內部節點的子樹個數不相同。我們對n節點多元樹用一簡單的右距離序列表示之。運用多元遞迴樹及伴隨關係表使我們在n節點多元樹作有系統的研究。利用右距離序列表示，我們提出一個演算法可以列舉所有n節點多元樹。此外，在辭彙編纂方式下，決定一n節點多元樹的排列次序及在轉換一整數為其相對應的n節點多元樹，我們也提出一個次序演算法及反次序演算法。

The enumeration of binary trees and t-ary trees has been extensively discussed in recent literature. Binary trees and t-ary trees are called regular trees. A lot of researchers have introduced integer sequences or permutations to characterize regular trees and provided efficient algorithms to generate those sequences in lexicographic order.
In this thesis, we are concerned with the enumeration of uncertain-ary trees in lexicographic order. A tree is said to be uncertain-ary if two nodes in different levels may have a different number of children. Then, we use a concise representation, called right distance sequences (or RD-sequence for short), to describe all uncertain-ary trees with n internal nodes. Using an uncertain-ary recursion tree and its concomitant tables, a systematical way can help us to investigate the structural representations of uncertain-ary trees. In addition, an algorithm is developed to enumerate all uncertain-ary trees with n internal nodes using RD-sequences. We also present two algorithms for determining the rank of a given uncertain-ary tree in lexicographic order (i.e., a ranking algorithm), and for converting a positive integer to its corresponding RD-sequence (i.e., an unranking algorithm).

[1] H. Ahrabian and A. Nowzari-Dalini, On the generation of binary trees in A-order, International Journal of Computer Mathematics 71 (1999) 351–357.
[2] H. Ahrabian and A. Nowzari-Dalini, Generation of t-ary trees with Ballot-sequences, International Journal of Computer Mathematics 80 (2003) 1243–1249.
[3] H. Ahrabian, A. Nowzari-Dalini, and E. Salehi, Gray code algorithm for listing k-ary trees, Studies in Informatics and Control 13 (2004) 243–251.
[4] H. Ahrabian and A. Nowzari-Dalini, Adaptive generation of t-ary trees in parallel, The Electronic International Journal Advanced Modeling and Optimization 8 (2006) 19–28.
[5] S. G. Akl and I. Stojmenovi´c, Generating t-ary trees in parallel, Nordic Journal of Computing 3 (1996) 63–71.
[6] V. Bapiraju and V.V.B. Rao, Enumeration of binary trees, Information Processing Letters 51 (1994) 125-127.
[7] B. Effantin, Generation of valid labelled binary trees, Proceedings of the 2003 International Conference on Computational Science and Its Applications (ICCSA’2003), LNCS, vol. 2667 (2003) 245–253.
[8] G. Ehrlich, Loopless algorithms for generating permutations, combination, and other combinatorial configurations, Journal of the ACM 20 (1973) 500–513.
[9] M. C. Er, Efficient generation of k-ary trees in natural order, The Computer Journal 35 (1992) 306–308.
[10] M. C. ER, A Simple Algorithm for Generating Non-regular Trees in Lexicographic Order, The Computer Journal 14 (1988) 61–64.
[11] D. A. Klarner, Correspondences between plane trees and binary sequences, Journal of Combinatorial Theory 9 (1970) pp. 401–411.
[12] G. D. Knott, A numbering system for binary trees, Communications of ACM 20 (2), (1977), 113-115.
[13] D. E. Knuth, The Art of Computer Programming. Vol. 1: Fundamental Algorithms, Addison-Wesley, Reading, MA, 1968.
[14] Z. Kokosi´nski, On parallel generation of t-ary trees in an associative model, in: Proc. of 4th International Conference on Parallel Processing and Applied Mathematics (PPAM 2001), LNCS 2328, Springer, (2002) pp. 228–235.
[15] Z. Kokosi´nski, A parallel dynamic programming algorithm for unranking t-ary trees, in: Proc. of 5th International Conference on Parallel Processing and Applied Mathematics (PPAM 2003), LNCS 3019, Springer, (2004) pp. 255–260.
[16] J. F. Korsh, Loopless generation of k-ary tree sequences, Information Processing Letters 52 (1994) 243–247.
[17] J. F. Korsh and S. Lipschutz, Shifts and loopless generation of k-ary trees, Information Processing Letters 65 (1998) 235–240.
[18] J. F. Korsh and P. LaFollette, Loopless generation of Gray code for k-ary trees, Information Processing Letters 70 (1999) 7–11.
[19] J. F. Korsh, Generating t-ary trees in linked representation, The Computer Journal 48 (2005) 488–497.
[20] J. M. Lucas, D. Roelants van Baronaigien, and F. Ruskey, On rotations and the generation of binary trees, Journal of Algorithms 15 (1993) 343–366.
[21] E. M¨akinen, Left distance binary tree representations, BIT 27 (1987) 163–169.
[22] E. M¨akinen, Generating random binary trees – A survey, Information Sciences 115 (1999) 123-136.
[23] H. W. Martin and B. J. Orr, A random binary tree generator, in: Proc. of the 17th conference on ACM Annual Computer Science Conference, Louisville, Kentucky, February 21-23, 1989, pp. 33-38.
[24] J. Pallo and R. Racca, A note on generating binary trees in A-order and B-order, Intern. J. Computer Math. 18 (1985) 27–39.
[25] J. Pallo, Enumerating, ranking and unranking binary trees, The Computer Journal 29 (1986) 171–175.
[26] A. Proskurowski, On the generating of binary trees, Journal of the ACM 27 (1980) 1–2.
[27] D. Roelants van Baronaigien and F. Ruskey, Generating t-ary trees in A-order, Information Processing Letters 27 (1988) 205–213.
[28] D. Roelants van Baronaigien, A loopless algorithm for generating binary tree sequences, Inform. Process. Lett. 39 (1991) 189194.
[29] D. Roelants van Baronaigien, A loopless Gray-code algorithm for listing k-ary trees, Journal of Algorithms 35 (2000) 100–107.
[30] F. Ruskey and T. C. Hu, Generating binary trees lexicographically, SIAM Journal on Computing 6 (1977) 745–758.
[31] F. Ruskey, Generating t-ary trees lexicographically, SIAM Journal on Computing 7 (1978) 424–439.
[32] F. Ruskey and A. Proskurowski, Generating binary trees by transpositions, Journal of Algorithms 11 (1990) 68–84.
[33] M. Solomon and R.A. Finkel, A note on enumerating binary trees, J. ACM 27 (1980) 3-5.
[34] T. Takaoka, O(1) time algorithms for combinatorial generation by tree traversal, The Computer Journal 42 (1999) 400–408.
[35] A. E. Trojanowaki, Ranking and listing algorithms for k-ary trees, SIAM Journal on Computing 7 (1978) 492–509.
[36] V. Vajnovszki, C. Phillips, Optimal parallel algorithm for generating k-ary trees, in: Proc. of the 12th International Conference on Computers and Their Applications, Tempe, Arizona, (ed. M. C. Woodfill), March 13-15, 1997, pp. 201–204
[37] V. Vajnovszki, On the loopless generation of binary tree sequences, Information Processing Letters 68 (1998) 113–117.
[38] V. Vajnovszki and C. Phillips, Systolic generation of k-ary trees, Parallel Processing Letters 9 (1999), 93–101.
[39] V. Vajnovszki, Generating a Gray code for P-sequences, Journal of Mathematical Modelling and Algorithms 1 (2002) 31–41.
[40] L. Xiang, K. Ushijima, and S. G. Akl, Generating regular k-ary trees efficiently, The Computer Journal 43 (2000) 290–300.
[41] L. Xiang, K. Ushijima, and C. Tang, Efficient loopless generation of Gray codes for k-ary trees, Information Processing Letters 76 (2000) 169–174.
[42] L. Xiang, K. Ushijima, and C. Tang, On generating k-ary trees in computer representation, Information Processing Letters 77 (2001) 231–238.
[43] L. Xiang, K. Ushijima, and Y. Asahiro, Coding k-ary trees for efficient loopless generation in lexicographic order, in: Proc. of International conference on Information Technology: Coding and Computing (ITCC’02), IEEE Computer Society Press, Las Vegas, April 8-10, 2002, pp. 396–401.
[44] S. Zaks, Lexicographic generation of ordered trees, Theoretical Computer Science 10 (1980) 63–82.
[45] S. Zaks, Generation and ranking of k-ary trees, Information Processing Letters 14 (1982) 44–48.
[46] D. Zerling, Generating binary trees using rotations, Journal of Association for Computing Machinery 32 (1985) 694–701.