二叉树枚举算法的研究.docx

二叉树枚举算法的研究.docx华东师范大学硕士学位论文二叉树枚举算法的研究姓名:董兆安中请学位级别:硕士专业:计算机软件与理论指导教师:.-⑴,,-,它表示n个节点组成的二叉柯的数目;另一种悬生成,・以各个算法生成0\个編码所需要的平均递归调用次数作为时间复杂度对比的尺度囚・-,实脸数据麦明:新算法通过贼少递归调用的次数,⑴提高了50%以上・基于上述对比结杲,•、最短路径、任务调厦、最小生成树等与优先级队列相关的领域•所以,堆的枚举算法的研究对相关应用族域会育很大的帮助・本文甘先介绍了齐种类型的堆结构及其发展,然后介绍了新近发現的最人值堆的一种性质⑴,以及基于这一性质提出的一种晨大值堆的生成算法⑴・最斥・,讨论了已有的两种堆的枚举计数算法〔°叫悠后根据最大值堆的生成过程推导出了堆的枚举计数新公式,并且基丁这一公式提出了一种新的最大值堆的枚举计数外法,该算法与同类算法相比貝有以下优点:其他的计数算法,“算法的时间复朵度不是”的多项式”何:而新算法不需要递归就可以实现,算法的时何复杂度为0(”)・新算法仅需耍一个大小为”的一维数组,空间复杂度为5”)・【关键词】一义树,堆,,puterscience・Assuch,,,,・WemakeafutherdiscussiononP-,・Anon-recursivealgorithmisalsopresented,-,ShortestPaths,TaskSchedule,・ThenweintroduceapropertyofMax-heapsrecentlydiscoveredandanalgorithmgeneratingMax-,westudytheproblemofcountingMax-heaps・Afterintroducingtheexistedmethodsof