二叉树枚举算法的研究

《二叉树枚举算法的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、华东师范大学硕士学位论文二叉树枚举算法的研究姓名：董兆安中请学位级别：硕士专业：计算机软件与理论指导教师：孙强20041201摘要二叉树是计算机科学中最星本的也雄最版耍的树型数据结构.因此.-XW枚举算法的研究无论在算法理论上还是在实际应用中都具有重要的意义.树的枚举有两种含义⑴，一冲是计数.即计算具有茱种特性的槿的总数目，Catalan数C.堆该领域著名的成果Z-,它表示n个节点组成的二叉柯的数目；另一种悬生成，即一个一个地产生具有某种特性的所有树.本文首先介绍了现有的四种基于嬪码的二文榆枚举生成算法.然后・以各个算法生成0个編码所需要的平均递归调用次数作为时间复杂度对比的尺度囚

2、・对儿个主要的编码生成算法进行丁对比分析.P序列编码生成算法是一种广义根式下的-码生成算法.本文对P序列編码的生成算法进行了研究.首先提山了一个枚举生成P序列編码的递归算法，实脸数据麦明：新算法通过贼少递归调用的次数，使算法的效率比H.Ahrabian的算法⑴提高了50%以上・基于上述对比结杲，本文乂提出了一个tiiHW法.进一步极髙了算法的效牟.而且根抿该1T递归算法设计的二义树枚举生成算法可以按照爛免的局部顺序生成对应的二叉诃•堆址一种曲耍的二义树.它破丿泛应用于数据推洋、最短路径、任务调厦、最小生成树等与优先级队列相关的领域•所以，堆的枚举算法的研究对相关应用族域会育很大的帮助

3、・本文甘先介绍了齐种类型的堆结构及其发展，然后介绍了新近发現的最人值堆的一种性质⑴，以及基于这一性质提出的一种晨大值堆的生成算法⑴・最斥・对蹑人值堆的枚举计数进行了深入的研究.首先，讨论了已有的两种堆的枚举计数算法〔°叫悠后根据最大值堆的生成过程推导出了堆的枚举计数新公式，并且基丁这一公式提出了一种新的最大值堆的枚举计数外法，该算法与同类算法相比貝有以下优点：1.其他的计数算法，“算法的时间复朵度不是”的多项式”何：而新算法不需要递归就可以实现，算法的时何复杂度为0(”)・2.新算法仅需耍一个大小为”的一维数组，空间复杂度为5”)・【关键词】一义树，堆，枚举.生成，计数ABSTRAC

4、TBinarytreesarethemostfundamentalandimportantdatestructuresusedincomputerscience・Assuch,theproblemofenumeratingbinarytreesisofgreatinterestfromboththeoreticalandpracticalpointofview.Enumeratingtreeshastwomeanings.Oneiscounting,thatisdeterminingthenumberofsomekindoftrees.ItiswellknownthattheCata

5、lanNumberC.isthenumberofbinarytreeswithnnodes.Thcotherisgenerating,whichmeanslistingallthetreeshavingsamepropertyonebyone.Inthispaper,wefirstintroducefourcategoriesofcodingalgorithmsforgeneratingbinarytrees.WewillcomparesomeofthealgorithmsusingthenumberofrecursivecallstoenumerateCBsequencesasam

6、easureoftimecomplexity・WemakeafutherdiscussiononP-Sequenceswhichisacodingmethodfollowingthegeneralscheme.Wegivearecursivealgorithmandcomparetheexecutivetime,findingthatourrecursivealgorithmismorethan1.5timesefficientofwhichpresentedbyH.Ahrabian・Anon-recursivealgorithmisalsopresented,whichismore

7、efficient.Thebinarytreescanbeconstnictedintypicallocalorderaccordingtothisnon-recursivealgorithm.HeapisanimportantbinarytreestructureoftenusedinapplicationsconcernedwithpriorityqueuesandpartialorderingsuchasSorting,ShortestPaths,T