# 臺灣博碩士論文加值系統

(3.235.174.99) 您好！臺灣時間：2021/07/24 19:07

:::

### 詳目顯示

:

• 被引用:0
• 點閱:111
• 評分:
• 下載:5
• 書目收藏:0
 一個 k分支樹是一個有根樹，亦是一個有順序的樹，且每個內部節點恰有 \$k\$個子樹 (k>=2)。Zaks 在 1980年建議採用一種最自然的表示法稱之為「x序列」或是「z序列」來描述一個 k分支樹。在採用 z序列表示法之下，van Baronaigien 和 Xiang 等人在 2000年分別設計了無迴圈演算法以產生 k分支樹之格雷碼。在本篇論文中，我們將介紹一個新的無迴圈演算法，它以 z序列表示法來產生 k分支樹之格雷碼。此一新的演算法所需記憶體空間比目前現有的演算法來的精簡，且執行效能更好。此外，將我們的演算法稍加修改後可以同時產生 k分支樹的 x序列，具同樣的精簡度及效能。
 A k-ary tree is a rooted and ordered tree such that every internal node has exactly k children (k>=2). A natural representation of k-ary trees is the use of x-sequences or z-sequences introduced by Zaks in 1980. Under such representations, a loopless algorithm that generates z-sequences of k-ary trees in Gray-code order was developed by van Baronaigien and Xiang et al. in 2000, respectively. In this paper, we present a new loopless algorithm to generate z-sequences of k-ary trees in Gray-code order. The development of our algorithm is in need of less memory space and is more efficient than the existing algorithms. Moreover, with a slight modification, our algorithm can generate x-sequences of k-ary trees such that only one pair of positions have different binary codes for two successive sequences.
 中文摘要..........................i英文摘要..........................ii誌謝................................iii目錄................................v表目錄.............................vii圖目錄.............................viii一、緒論..........................11.1 研究背景....................11.2 研究動機與目的...........41.3 論文架構....................5二、文獻探討....................7三、主要結果....................193.1 k分支樹的結構性質......193.2 翻轉樹........................213.3 無迴圈演算法..............23四、結論與未來研究方向....314.1 結論...........................314.2 未來研究方向..............32參考文獻..........................33
 [1] H. Ahrabian, A. Nowzari-Dalini, and E. Salehi. Gray code algorithm for listing k-ary trees. Studies in Information and Control, 13:243–251, 2004.[2] G. Ehrlich. Loopless algorithms for generating permutations, combinations, and other combinatorial configurations . Journal of the ACM, 20:500–513, 1973.[3] M.C. Er. A note on generating well-formed parenthesis strings lexicographically. Computer Journal, 26:205–207, 1983.[4] M.C. Er. Lexicographic listing and ranking t-ary trees. Computer Journal, 30:569–572, 1987.[5] Frank GRAY. Pulse code communication, March 17 1953. US Patent 2,632,058.[6] J.F. Korsh. Loopless generation of k-ary tree sequences. Information ProcessingLetters, 52:243–247, 1994.[7] J.F. Korsh and P. LaFollette. Loopless generation of Gray codes for k-ary trees.Information Processing Letters, 70:7–11, 1999.[8] J.F. Korsh and P. LaFollette. A loopless Gray code for rooted trees. ACMTransactions on Algorithms, 2:135–152, 2006.[9] J.F. Korsh and S. Lipschutz. Shift and loopless generation of k-ary trees. Information Processing Letters, 65:235–240, 1998.[10] Joan M Lucas. The rotation graph of binary trees is hamiltonian. Journal of Algorithms, 8:503–535, 1987.[11] J. Pallo. Enumerating, ranking and unranking binary trees. Computer Journal, 29:171–175, 1986.[12] A. Proskurowski. On the generation of binary trees. Journal of the ACM (JACM), 27:1–2, 1980.[13] A. Proskurowski and F. Ruskey. Binary tree Gray codes. Journal of Algorithms, 6:225–238, 1985.[14] F. Ruskey. Generating t-ary trees lexicographically. SIAM Journal on Computing, 7:424–439, 1978.[15] F. Ruskey and T.C Hu. Generating binary trees lexicographically. SIAM Journal on Computing, 6:745–758, 1977.[16] C.D. Savage. A survey of combinatorial Gray codes. SIAM Review, 39:605–629, 1997.[17] Trojanowski and Anthony E. Ranking and listing algorithms for k-ary trees. SIAM Journal on Computing, 7:492–509, 1978.[18] V. Vajnovszk. Constant time algorithm for generating binary tree Gray codes. Studies in Information and Control, 5:15–21, 1996.[19] V. Vajnovszk. On the loopless generation of binary tree sequences. Information Processing Letters, 68:113–117, 1998.[20] V. Vajnovszk. Generating a Gray code for P-sequences. Journal of Mathemat- ical Modelling and Algorithms, 1:31–41, 2002.[21] D.R. van Baronaigien. A loopless algorithm for generating binary tree sequences. Information Processing Letters, 39:189–194, 1991.[22] D.R. van Baronaigien. A loopless Gray-code algorithm for listing k-ary trees. Journal of Algorithms, 35:100–107, 2000.[23] D.R. van Baronaigien and F. Ruskey. Generating t-ary trees in a-order. Information Processing Letters, 27:205–213, 1988.[24] S.G. Williamson. Combinatorics for Computer Science. Computer Science Press, Rockville, MD, 1985.[25] R.-Y. Wu, J.-M. Chang, and Y.-L. Wang. Loopless Generation of non-regular trees with a prescribed branching sequence. Computer Journal, 53:661–666, 2010.[26] L. Xiang, C. Tang, and K. Ushijima. Grammar-oriented enumeration of binary trees. The Computer Journal, 40:278–291, 1997.[27] L. Xiang and K. Ushijima. Grammar-oriented enumeration of arbitrary trees and arbitrary k-ary trees. IEICE TRANSACTIONS on Information and Systems, 82:1245–1253, 1999.[28] L. Xiang, K. Ushijima, and C. Tang. Efficient loopless generation of Gray codes for k-ary trees. Information Processing Letters, 76:169–174, 2000.[29] L. Xiang, K. Ushijima, and C. Tang. On generating k-ary trees in computer representation. Information processing letters, 77:231–238, 2001.[30] S. Zaks. Lexicographic generation of ordered trees. Theoretical Computer Science, 10:63–82, 1980.[31] D. Zerling. Generating binary trees using rotations. Journal of the ACM (JACM), 32:694–701, 1985.
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 k分支樹序列在格雷碼順下之定序演算法

 無相關期刊

 1 不同媒體豐富性學習方式對心流體驗與認知負荷之影響：遊戲式學習對非遊戲式學習 2 局部扭轉超立方體中嵌入兩個互斥多維度網格 3 非凌越排序基因演算法之調校與財務投資組合最佳化 4 多維環狀體在陣列光纖網路上之波長分配研究 5 自動化證件照拍攝演算法設計 6 以社交網路為基礎之知識社群系統建置研究 - 以知識銀行系統為例 7 在梯形圖上探討中繼數 8 模組化資源整合流程之研究-以台北國際花卉博覽會未來館為例 9 探討核酸內切酶FEN1在B型肝炎病毒中環狀共價鍵結去氧核醣酸形成過程所扮演的角色 10 成人付費及持續使用數位學習意願之影響因素探討─以中小企業網路大學校為例 11 企業員工數位化生涯歷程檔案之構面與組成要項 12 網路化學習歷程檔案對學生知識管理之影響 13 在EPUB檔中隱藏資料的研究 14 跨部門情境下Wiki對協同合作成效影響之研究 15 生物技術產業創投媒合網站系統之研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室