（计算机软件与理论专业论文）二叉树枚举算法的研究.pdf

二又树枚举算法的研究摘要 摘要 二叉树是计算机科学中最基本的也是最重要的树型数据结构。冈此，二叉树枚举算法的 研究无论在算法理论上还是在实际应用中都具有重要的意义。 树的枚举有两种含义，一种是计数即计算具有某种特性的树的总数目，c a t a l a n 数g 是 该领域著名的成果之一，它表示h 个节点组成的二叉树的数目；另一种是生成，即一个一个 地产生具有某种特性的所有树。 本文首先介绍了现有的四种基于编码的二义树枚举生成算法。然后，以各个算法生成g 个编码所需要的平均递归调用次数作为时间复杂度对比的尺度口l ，对几个主要的编码生成算法 进行了对比分析。 p 序列编码生成算法是一种广义模式下的二义树编码生成算法。本文对p 序列编码的生 成算法进行了研究。首先提出了一个枚举生成p 序列编码的递归算法，实验数据表明：新算 法通过减少递归调用的次数，使算法的效率比h a h r a b i a n 的算法”埂高了5 0 以上。基于上 述对比结果，本文又提出了一个非递归算法，进一步提高了算法的效率，而且根据该非递归 算法设计的二叉树枚举生成算法可以按照规范的局部顺序生成对应的二叉树。 堆是一种重耍的二叉树，它被j “泛应用于数据排序、最短路径、任务调度、最小生成树 等与优先级队列相关的领域。所以，堆的枚举算法的研究对相关应用领域会有很大的帮助。 本文首先介绍了各种类型的堆结构及其发展，然后介绍了新近发现的最人值堆的一种性 质【4 1 以及基于这一性质提出的一种最大值堆的生成算法”。最后对最人值堆的枚举计数 进行了深入的研究。 首先，讨论了已有的两种堆的枚举计数算法 6 3 1 ，然后根据最大值堆的生成过程推导出了 堆的枚举计数新公式，并且基丁这一公式提出了一种新的最大值堆的枚举计数算法，该算法 与同类算法相比具有以下优点： 1 其他的计数算法，“算法的时间复杂度不是 的多项式”【6 】；而新算法不需要递归就 可以实现，算法的时间复杂度为0 ( n ) 。 2 新算法仅需要一个大小为”的一维数组，空间复杂度为d ( n ) 。 【关键词】_ 二义树，堆，枚举，生成，计数 第1 页 墅堕堂竺坠! 竺! 竺! 堕旦坐型! 竺! 垒生坚! a b s t r a c t b i n a r yt r e e sa r et h em o s tf u n d a m e n t a la n di m p o r t a n td a t as t r u c t u r e su s e di nc o m p u t e rs c i e n c e a ss u c h ，t h ep r o b l e mo fe n u m e r a t i n gb i n a r yt r e e si so fg r e a ti n t e r e s tf r o mb o t ht h e o r e t i c a la n d p r a c t i c a lp o i n to f v i e w e n u m e r a t i n gt r e e sh a st w om e a n i n g s o n ei sc o u n t i n g , t h a ti sd e t e r m i n i n gt h en u m b e r o f s o m e k i n do ft r e e s i ti sw e l lk n o w nt h a tt h ec a t a l a nn u m b e rgi st h en u m b e ro fb i n a r yt r e e sw i t h n o d e s t h eo t h e ri sg e n e r a t i n g ，w h i c hm e a n sl i s t i n ga l lt h et r e e sh a v i n gs a m ep r o p e r t yo n e b yo n e i nt h i sp a p e r , w ef i r s ti n t r o d u c ef o u rc a t e g o r i e so f c o d i n ga l g o r i t h m sf o rg e n e r a t i n gb i n a r yt r e e s w ew i l lc o m p a r es o m eo ft h ea l g o r i t h m su s i n gt h en u m b e ro fr e c u r s i v ec a l l st oe n u m e r a t ec n s e q u e n c e sa sam e a s u r eo f t i m ec o m p l e x i t y w em a k eal u t h e rd i s c u s s i o no np - s e q u e n c e sw h i c hi sac o d i n gm e t h o df o l l o w i n gt h eg e n e r a l s c h e m e w eg i v ear e c u r s i v ea l g o r i t h ma n dc o m p a r et h ee x e c u t i v et i m e ，f i n d i n gt h a to u rr e c u r s i v e a l g o r i t h mi sm o r et h a n1 5t i m e se f f i c i e n to fw h i c hp r e s e n t e db yh a h r a b i a n an o n - r e , c u r s i v e a l g o r i t h mi sa l s ep r e s e n t e d ，w h i c hi sm o r ee f f i c i e n t t h eb i n a r yt r e e sc a nb ec o n s t r u c t e di nt y p i c a l l o c a lo r d e ra c c o r d i n gt ot h i sn o n - r e c u r s i v ea l g o r i t h m h e a pi sa ni m p o r t a n tb i n a r yt r e es t r u c t u r eo f t e nu s e di na p p l i c a t i o n sc o n c e r n e dw i t hp r i o r i t y q u e u e sa n dp a r t i a lo r d e r i n gs u c ha ss o r t i n g ，s h o r t e s tp a t h s ，t a s ks c h e d u l e ，a n dm i n i m u ms p a n n i n g t r e e s oe n u m e r a t i n gh e a p si so fg r e a ti n t e r e s t w ef i r s tm a k ea s u r v e yo fd i f f e r e n tk i n d so fh e a p s t r u c t u r e s t h e nw ei n t r o d u c eap r o p e r t yo fm a x - h e a p sr e c e n t l yd i s c o v e r e da n da na l g o r i t h m g e n e r a t i n gm a x - h e a p sb a s e d0 nt h ep r o p e r t y a tt h ee n do ft h i sp a p e r , w es t u d yt h ep r o b l e mo fc o u n t i n gm a x - h e a p s a f t e ri n t r o d u c i n gt h e e x i s t e dm e t h o d so f c o u n t i n gh e a p sf i r s t l y , w ep u tf o r w a r dt h ec o u n t i n gf o r m u l ao f m a x - h e a p sb a s e d o nt h ep r o c e s so fg e n e r a t i n gm a x - h e a p s ，a n dg i v ea s i m p l ea n de f f i c i e n ta l g o r i t h mr e a l i z i n gt h e c o u n t i n gf o r m u l a t h i sn e wa l g o r i t h mh a sf o l l o w i n ga d v a n t a g e sc o m p a r e dw i t ho t h e ra l g o r i t h m s ： 1 t i m ec o m p l e x i t yo fo t h e ra l g o r i t h m si sn o tl i n e rf u n c t i o no fn o nc o n t r a s t , t h ei l e w a l g o r i t h mc a nb ei m p l e m e n t e dw i t h o u tr e c u r r e n c e r st i m ec o m p l e x i t yi so 2 t h en e wa l g o r i t h mo n l yn e e d sa na r r a yw h o s es i z ei sn ，s ot h es p a c ec o m p l e x i t yi so m k e yw o r d s b i n a r yt r e e h e a p ，e n u m e r a t i n g ，g e n e r a t i n g ，c o u n t i n g 第1 1 页 二叉树枚举算法的研究声明 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成 果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表 或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作 了明确说明并表示谢意。 作者签名：董2 i 篷望作者签名：室= 丑垒鲨 日期：丝丝! 兰! i 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学 位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出 版。保密的学位论文在解密后适用本规定。 址、1 学位论文作者签名：勤簧导师签名：扪、；勺 日期：! 叟! 兰少 叉树枚举算法的研究第1 章绪论 1 1 前言 第1 章绪论 树，作为一个数学上的概念，最早出现在g 克希霍夫的著作中。后来，树的定义以及 有关丁讨论树型枚举的结果出现在a 凯利的一系列论文中吲。现在，树不仅是数学领域的 一类抽象的数学对象，而且是计算机数据结构与算法分析中最重要的非线性数据结构，被广 泛应用于优先级队列、分支决策、分类学、计算机语言、组合优化、形式文法、图像处理、 c a d 、g i s 等众多领域。 从数学上讲。树的枚举理论具有其独立的数学结果的意义。枚举有计数( c o u n t i n g ) 和 生成( g e n e r a t i n g ) 两种含义f ”。树的计数，即计算某种特性的树的数目；树的生成，即一个 一个的产生具有某种特性的所有树。比如，我们刚刚完成个用来处理- 二义树的程序，为了 测试或者分析这个程序，有必要产生节点数目相同而形状不同的二叉树以作为测试数据。 计算机的出现和计算机算法的研究极人的推动了树的枚举理论的发展。树的枚举理论也 推动了n 元排列( p e r m u t a t i o n s ) 、良构串( w e l l - f o r m e ds t r i n g s ) 等组合对象的枚举算法的研 究1 4 “。 1 2 本文的主要工作 树的枚举计数理论在数学领域中已不是一个新题目，c a t a l a n 数、波利砸( p o l y a ) 计数 定理、生成函数、排列组合理论等都与计数理论密切相关 k s 】。关于树的枚举计数理论国内的 王振宁老师在文献 1 中已经进行了详细的研究，文献【8 ，9 】中也有较为详细的介绍，本文将简 单介绍一下二叉树的计数与c a t a l a n 数。 树的枚举生成方面，也已经积累了大量的研究成果。本文将介绍”个节点的二叉树的枚 举生成算法。这些算法都是先建立_ 二叉树与二叉树编码之间的一一对应关系，然后将二叉树 的枚举生成问题转化为编码的枚举生成问题i ”j 。目前主要有四种编码模式f 的- 二义树生成算 法，即基于树排列的编码生成算法、基于旋转的编码生成算法、广义模式卜的编码生成算法、 基于文法的编码生成算法。 k n o t t 早在1 9 7 7 年就已提山了树排列( t r e ep e m l u t a t i o n ) 的概念，建立了二义树与树排 列编码之间的一一对应的关系；他还定义了二叉树的自然顺序( n a t u r a lo r d e r ) ，使得节点个 数相同而形状不同的二义树之间可以比较优先次序。随后，r o t t e m 和v a r o l 在树排列的基础 第1 页 二叉树枚举算法的研究第1 章绪论 上提出了选举序一y l j ( b a l l o t s e q u e n c e ) i ”】并给出了生成所有选举序列的算法。根据 该算法设计的二叉树枚举生成算法中，二义树的生成顺序称作选举顺序( b a l l o t o r d e r ) 。 1 9 8 5 年，z e r l i n g 提出了二叉树的旋转编码方法( c o d i n gb a s e do nr o t a t i o n s ) 【1 9 。旋转 是将一棵二叉树变形为另外一棵基准二叉树的特定操作。该编码方法存在明显的不足：必须 先知道二叉树的形状，然后进行旋转才可以得到对应的编码。1 9 8 7 年e m a k i n e n 提出了l d ( l e t ld i s t a n c e ) 编码 2 4 1 改进了旋转编码的不足。本文对该算法进行了分析，得出该算法生 成g ( c a t a l a n 数) 个编码的平均递归调用次数是0 3 3 。近两年来，j p a l l o 和l u e a s 等又对 二叉树的旋转编码进行更深入的研究1 3 4 , 4 2 , 4 3 。 扩展二叉树与二叉树的一一对应关系，启发人们提出了一些基于扩展二叉树的编码方法， 我们称为广义模式下的编码。最甲是r u s k e y 和h u 提出的叶子层号序列编码( l e a fl e v e l s s e x u e n c e s ) ；1 9 8 2 年，s z a k s 提出的编码算法中沿用p r o s k u r o w s k i 的方法，用1 表示 内节点，用0 表示外节点，从而得到一个由0 、l 组成的序列 l g l ，称作z 序列( zs e q u e n c e s ) ； 1 9 8 5 年，m c e r 提出的比特串( b i tp a t t e n ) 编码 2 t i 采用了同样的编码方法，他给出了枚 举所有比特串编码的算法，算法的平均递归调片j 次数趋向于5 3 3 ，p 序列编码方法最早是由 p a l l o 和r a c c a 在1 9 8 5 年提出的1 2 0 。2 0 0 3 年，h a h r a b i a n 又提出了一个新的p 序列的枚举 生成算法 3 1 ，该算法生成g 个p 序列编码的平均递归调用次数是1 。本文将进一步研究改进 p 序列的枚举生成算法。此外，w 序列2 2 1 也是广义模式f 的编码方法。 1 9 9 7 年l x i a n g 等人提出了基于上下文无关文法( c o n t e x t f r e eg r a m m a r ) 的编码方法。 二叉树的文法编码被看作是定义在给定字母表上的一个上下文无关文法推导出的单词 ( w o r d ) 。l x i a n g 等人结合二叉树的结构特点研究了这类文法的一些特性。他制还以算法生 成g 个编码所需要的平均递归调用次数作为算法时间复杂度对比的尺度对已有的几种算法 进行了对比分析，并给出了基于文法的二叉树枚举生成算法。l x i a n g 提出的算法生成g 个 p 序列编码的平均递归调用次数小下1 3 3 ，但是大于1 。e m a k i n e n 也对- 二叉树文法编码进 行了研究，并提山了有关这类文法性质的更简单的证明方法l | “。 值得注意的是，有时我们像上面叙述的那样只需要考虑树与树之间形状上的差异而不考 虑节点内的数值的大小这一类的树的枚举问题称为无值枚举：另外一些情况下，我们可能 仅仅关心树的节点内的数据信息之间的比较，相关的枚举问题称为有值枚举【6 l 。 堆( h e a p ) 是一种很重要的树型数据结构，它被，“泛应用于数据排序、最短路径、最小 生成树、任务调度、离散事件模拟以及其他一些网络问题优化处理等问题的研究中1 1 。 堆的定义与节点内的数值信息密切相关，所以堆的枚举问题属丁有值枚举【6 l 。堆的常用 表示方法是它的隐式结构，即用一个数组来表示对麻的完全二叉树内的数值。除隐式堆结构 以外，人们还提出了一些堆的变种数据结构，这些堆型数据结构在算法分析等许多领域扮演 重要的角色。随着堆排序等相关算法及应用的不断改进与发展，堆结构的一些组合属性也 第2 页 二叉树枚举算法的研究 第1 章绪论 被深入的研究，堆的枚举生成与计数算法就属于这一范畴。 2 0 0 1 年，文献 4 】发现并证明了最大值堆的一种层次性质。简单地说，就是最大值堆的某 一层上的所有节点的值( 不包括叶子节点的值) 与堆中此层以f 的所有节点的值满足一个不 等式组。根据堆的这一性质，文献 5 】提山了一个枚举生成所有最大值堆的实用算法该算法 使用了“层次判断法”，人大提高了堆的生成效率。 2 0 0 2 年文献 6 】又进一步讨论了最大值堆的枚举计数问题，并设计了一个递归算法来计算 任意最大值堆的枚举总数目。遗憾的是“该算法的时间复杂度不是h 的多项式”1 6 1 。k u r z 也 在2 0 0 2 年给出了一个递归公式米实现堆的枚举计数【”。 本文的研究t 作土要有以下两点： 1 首先介绍四种现有的基于编码的二叉树枚举生成算法。然后按照文献 2 使用的方 法以算法生成g 个编码所需要的递归调用次数作为时间复杂度对比分析的尺度对其中几个 主要的生成算法进行对比分析。 p 序列编码生成算法是一种广义模式下的编码生成算法。h a h r a b i a n 的算法 3 1 g e n p 生成 。个p 序列编码需要递归调用g 次，而本文提出的一个递归算法g e n p 2 通过减少递归调用 的次数，使算法的效率比原算法提高了5 0 以上。基丁上述对比结果，本文又进一步提出了 一个非递归算法g e n p 3 。算法g e n p 3 的运行效率明显高于算法g e n p 2 。 2 在堆的枚举算法的研究中，本文首先同顾了各种类型的堆结构及其发展。然后介绍 了新近发现的最大值堆的一种性质，以及基于这一性质提出的一种堆的生成算法。最后，本 文对堆的枚举计数进行了深入研究。首先，讨论了已有的堆的枚举计数方法，然后根据最大 值堆的生成过程推导出了堆的枚举计数公式并且提出了一种高效的最大值堆的枚举计数新 算法。该算法不需要递归就可以实现算法的时间复杂度为d p 。空间复杂度也为。倒。 1 3 本文内容安排 本文其余章节内容安排如下： 第2 章给出二叉树的相关概念和一些符号约定。另外还介绍了树的排序、二叉树的计数、 排名等预备知识。 第3 章介绍了四种编码模式下的二叉树生成算法，并比较分析了儿种主要的算法。最后 研究了厂义模式下的p 序列编码枚举生成算法。 第4 章重点研究了堆的枚举生成与计数算法的设计与实现。 第5 章对本文的研究进行了总结和展望。 第3 页 二叉树枚举算法的研究第2 章二叉树 第2 章二叉树 本章首先介绍了二叉树的概念以及一些符号约定，然后介绍了二叉树集合上的自然顺序 ( n a t u r a lo r d e r ) 和局部顺序( l o c a lo r d e r ) 的定义。c a t a l a n 数不仅是二叉树的枚举计数结果，而 且还经常出现在其他一些组合计数问题中，本文作了简单的介绍。最后讨论了二叉树的排名 ( r a n k i n g ) 与解析排名( u n r a n k i n g ) 的概念。 2 1 概念与符号约定 定义2 1 1 8 】二叉树( b i n a r yt r e e ) 是一个有限的节点的集合t ，它或者为一空集，或者： 1 ) 有一个特定的节点，称为根节点( r o o t ) ； 2 ) 两个不相交的有限子集死，其中死，珞都是二义树，称作根节点r 的左、 右子树。 严格地说，二叉树不是二次有序树，p 叉树也不是| 次有序树，它们完全是另外一种树 型结构的概念。在树型结构的应用中，二叉树特别重要。许多算法因为使用了二义树作为存 储结构而变得非常简单；另外，我们可以通过“克努特变换”很容易地实现二叉树与任意次 数的树之间的转换h j 。 这里我们给出一些符号约定，以各后文使用。假设，是一棵_ 二义树，它的左子树表示为 上驴( r ) ，右子树为r i g h t ( t ) ：如果“是二叉树t 的个节点那么l e f t ( 甜) 表示节点“的 左子树，r i g h t ( u ) 表示“的右子树；二叉树r 的节点数目，也称为二叉树，的大小，表示为 s i z e ( t ) 。从根节点到最左边的孩子节点的路径叫做t 的左臂( l e ra r m ) 1 1 9 1 如果所有的 节点都在左臂上，那么这样的一二义树叫做左倾线性树( l e r l i n e r t r e e ) 或左倾列表( l e r l i s t ) 2 a l ；类似地，也可以定义r 的右臂( r i g h t a r m ) 。如图2 - 1 所示： 图2 1 左倾线性树和右倾线性树 f i g 2 - ll e r l i s ta n dr i g h tl i s t 定义2 2 扩展二叉树( e x t e n d e db i n a r yt r e e ) 是个有限节点的集合l 它或者为一叶 子节点( e x t e r n a ln o d e ) ，或者： 第4 页 州 2 、 。、 2 ， n 二叉树枚举算法的研究第2 章二叉树 1 ) 有一个特定的内节点( i n t e m a ln o d e ) ，称为根节点； 2 ) 两个不相交的有限子集巩，靠，其中n ，玮都是扩展二叉树，称作根节点r 的左、右子树。 硷 ( a ) 二叉树( b ) 扩展二叉树 图2 2 二叉树及扩展二又树 f i g 2 - 2b i n a r yt r e ea n de x t e n d e db i n a r yt r e e 定理2 1 由2 n + 1 个节点组成的扩展二义树，必然有 个内1 7 点和肿1 个外节点。 图2 2 给出一棵二叉树和对应的扩展二叉树。可以看出，二叉树和扩展二叉树没有本质 上的不同，区别只是在于对“空集”的表示方式不同。这样就在n 个节点的二叉树与2 n + 1 个节点的扩展二叉树之间建立的一一对应的关系。 完全二叉树( c o m p l e t eb i n a r yt r e e ) 是一种特殊的二义树，如图2 - 3 所示。 一般情况下，在使用完全二叉树时，对各节点从上往下，从左往右依次编号为w ，然 后存储在线性数组中。可以得出如下结论：节点k 的父亲肖点是节点陋2 j ，节点k 的孩子 节点如果都存在的话编号分别是2 和2 k + l 。 图2 - 3 完全二又树 f i g 2 3c o m p l e t eb i n a r yt r e e 对于二叉树的一些概念。可以推广到三叉树【8 1 ，甚至k 叉树。比如，对于完全k 义树上 的一个节点p ，其父亲节点编号为l ( p + 一2 ) k j ：而这个节点的孩子节点如果存在的话， 依次为：k ( p 一1 ) + 2 ，k ( p 一1 ) + 3 ，印+ 1 。 第5 页 二叉树枚举算法的研究第2 章二叉树 2 2 二叉树的线性排序 d e k n u t h 定义了二叉树集合上的一个偏序关系嘲，这里用符号“”表示，记号“x y ”可以读作“x 先于或者等于y ”。在此我们沿用k n o t t 的定义，即如果x y 且x y ( x 不等价于y ) ，写作“x y ”且读作“x 先于y ”。 对于二叉树集合上的偏序关系“ ”，定义如下。 定义2 3 已知二叉树乃、乃，定义乃 乃，当且仅当： ns i z e ( t 1 ) s i z e ( t 2 ) ；或者 2 ) s i z e ( t t ) = s i z e ( t 2 ) ，且三印r w 工驴r 黝；或者 3 ) s i z e ( t o = s i z e r z ，l e f t ( t 1 ) = 上驴r z 0 ，而且r i g h t ( t d r i g h t ( t o 。 上述定义被称作自然顺序( n a t u r a l o r d e r ) 。m c e r 将自然顺序的定义扩展到了t 叉( 有 序) 树，并提出了局部顺序( l o c a lo r d e r ) 的概念怛。 假设m 叫表示含有i 7 个节点的k 叉树的集合。如果树t e t o c , n ) ，则用正表示k 叉树r 的第i 棵子树。图2 4 给出的是树的集合z 馏，卅上所有树的一个自然顺序关系( 即含有4 个 内节点的二叉树集合) 。 定义2 4 ( n a t u r a l o r d e r ) 己知集合z 伉州内的两棵k 叉树t 、s ，定义偏序关系t s 为： 1 ) s i z e s i z e 御：或者 2 ) s i z e = s i z e 何，且存在一个i ，1 f t 有 a )乃= 西，其中l ， f ；且 b ) 正 x ：夕气令op ；又 12345678 9 1 0 1 2 1 31 4 图2 - 4z 仁卅上的自然顺序 f i g 2 - 4n a t u r a lo r d e ro f r ( e ，卅 定义2 5 ( l o c a l o r d e r ) 己知集合7 传圳内的两棵k 义树n 量定义r s 为 1 ) t 为空树，而s 非空：或者 2 1ns 都不为空，且存在一个i ，1 f t 有 a ) 巧= s ，其中1 0 f ：且 第6 页 二叉树枚举算法的研究第2 章二叉树 b )正 父乏夕人令o 多p 又 123456780 o11 21 31 4 固2 - 5t f 2 4 ) 上的局部顺枣 f i g 2 - 5l o c a lo r d e ro f t 2 。4 ) 自然顺序的特点是将二叉树的节点个数考虑在内，对参与排序的树结构有一个全局的了 解，使用自然顺序设计的生成树算法总是将节点个数小的二义树排在前面。与自然顺序不同 的是，局部顺序只注重各个树之间的局部筹异，差异越小的二叉树排名越邻近，可见，生成 的树不一定是按照节点个数排序的。 假设两棵树r 、s 属于同一树族集台，且按照自然顺序比较的结果是：t s ，但按照局 部顺序却可能是：s 1 个节点的二叉树可以看成是由一个根节点、一棵具有i 个节点的左子树和一 棵具有n f - 1 个节点的右于树所组成。从生成函数的角度来看，序列 g ) 的生成函数为： 第7 页 二叉树枚举算法的研究第2 章二叉树 c 。= 妻n = 0 一警 二 它满足递归方程：c ( x ) = 1 + 工c ( x ) 2 ，该递归方程很自然的对应于二叉树的定义。 求解上述关系可以得到： e = 磊1 。、( 2 。n 上述结果即所谓的c a t a l a n 数。图2 - 4 和图2 - 5 给出的就是当二叉树节点个数为n = 4 时 c d = 1 4 棵形状不同的二叉树在自然顺序和局部顺序下的排序。 c a t a l a n 数的提出已经有1 0 0 多年的历史了，目前它已经被麻用于许多组合对象的枚举计 数算法的研究中。举例如下 9 1 ： 1 首先，扩展二义树与二叉树的对应关系，可以知道含有 个内节点和耐- 1 个叶子节 点的不同形状的扩展二叉树的数目为c h 。 2 堆栈的存取操作。片js 和x 分别表示进栈( p u s h ) 和出栈( p o p ) 操作；对于一个 空栈，首先需要进栈一次，然后才可能出栈。在任何时刻，由s 和x 组成的堆栈操 作序列中，x 的个数一直不能超过s 的个数。由s 和x 组成的此类序列的总数为e 。 3 凸多边形的三角形拆分问题。一个凸n + 2 边形，通过不相交丁该多边形的对角线， 把它边形拆分成若干三角形，不同拆分的数目就可以用第n 个c a t a l a n 数e 表示。 4 方格遍历问题。在一个_ 二维方格平面中，从点( o ，o ) 到点( 聆，甩) 的路径中不超过直 线y = x 的路径条数。这里采用的单步前进方向是( o ，1 ) 和( 1 ，0 ) 。 5 d y c k 路径。d y c k 路径是在平面坐标系中从( o ，o ) 到( 2 n + 2 ，0 ) 的方格遍历路径 中，不低于x 轴的路径数目。这里的单步前进方向是( 1 ，1 ) 和( 1 ，- 1 ) 。 可见，c a t a l a n 数不仅仅具有独立的数学意义，还作为组合对象的枚举计数结果被应用于 组合数学领域的研究。当然，c a t a l a n 数的应用还不止以上所述。后文讨论到的二叉树编码的 枚举计数结果都可以通过c a t a l a n 数来计算，这也正体现了二义树的编码与对应的二叉树之 间的一一对应关系。 第8 贞 二叉树枚举算法的研究第2 章二叉树 2 4 二叉树的排名与解析排名 通过计数，我们可以得到节点个数为”的二叉树集合曰( h ) 的人小g ，结合前文定义的 树的线性排序关系，确定集合b ( n ) 和区间【l ，g 上的一一对应的芙系。 定义2 6 设n 个节点的_ 二叉树的集合为_ 8 ( 胛) ，b ( 行) 降c 。t 如果8 ( n ) 上的偏序关系 “ ”，使得正 瓦 0 l j c ( ，( r ) ) 其中：函数c ( t ) 表示s i z e ( t ) ；r r 了) 、，分别表示二叉树t 的左右子树；g 表示c a t a l a n 数； g 。= c j g r l 表示左子树含有j 个节i 点总节点数目为n 的- 二叉树的数目，即 c 。= g ( 这里如果产d ，那么q 。= ：否则q 。；d ) 。 j = o 定理2 2 已知n 个节点的二义树正、正满足定义2 3 定义的自然顺序互 正，当且仅 当r a n k ( t 1 ) r a n k ( t 2 ) 。 r a n k ( t ) 函数的计算需要常数时间获得各子树的大小( 预先存储到各节点) t 然后对每 个节点递归调用r a n k ( t ) ，所以时间复杂度为。俐。 下面分析逆函数r a n k _ 1 ( f ，n ) ，即要根据排名i 构造对应的二义树z 。 已知g ”= c j 。巴一，一1 表示左子树含有个节点，总竹点数目为”的二叉树的数目。 首先，假设z 的左子树节点数目为k ，则 七= 扯，黔柚沁f ) 其中，s j 。是可以预计算的信息；可以通过二分查找树查找到所需要的值，时间复杂度 为o ( 1 0 9 k ) o ( 1 0 9 n ) 。 第9 贞 二叉树枚举算法的研究 第2 章一叉树 其次，递归调用r a n k ( l f c ，) 和r a n k ( i m o d c ，) 分别构造二叉树正的左、右 子树，其中r = 胛一k 一1 表示右子树的人小。 r a n k l ( f ，n ) 函数如果不包含递归操作，时间复杂度为o ( n ) ：因为每次递归操作就会生 成一个节点，所以兄口腑。( f ，n ) 构造一棵二叉树的时间复杂度为0 ( n l o g n ) 。 现在，我们可以定义一个函数n e x t ( t ) 来生成二叉树r 在自然顺序上的后继二叉树。这 样就可以用图2 1 中的右倾二叉树作为初始树，重复调用n e x t ( t ) 直到二义树没有后继树， 此时大小为n 的二叉树就生成完毕。n e x t ( t 1 的执行过程如下： 首先，尝试调用n e x t ( r i g h t ( t ) ) ，将r i g h t ( n 转化为对应的后继树；如果r i g h t ( t ) 没 有后继树，则将r i g h t ( t 1 转化为相同节点数目的右倾二叉树； 然后，尝试调用n e x t ( l 驴( r ) ) ，将上妒( 丁) 转化为对应的后继树；如果三妒( 丁) 也没有 后继树t 则首先将r i g h t ( t ) 的一个竹点传递给驴( 丁) t 然后将r i g h t ( t ) 和l e f t ( r ) 转化 为对应的初始树。 递归调用上述过程，就可以生成二义树，的f | 亓继树。上述过程中，初始化 个节点的二 叉树的时间复杂度为0 俐：二叉树上n 个节点为根的子树都可能调用一次n e x t ( t ) ，所以 n e x t 叮) 的时间复杂度为0 俐。 本章首先介绍了二叉树的一些概念与定义，然后介绍了_ 二义树的自然顺序和局部顺序两 种偏序关系的定义。二叉树的生成算法可以按照这两种规范的顺序生成节点数目相同而形状 不同的二叉树。此外我们还介绍了二叉树的计数与c a t a l a n 数。在一定的生成顺序下，我们 可以定义二叉树的排名操作，这样就可以建立二叉树集合与非负整数集合上的一一对应的关 系。本章最后介绍了二叉树在自然顺序上的排名和解析排名的操作。摊名和解析排名的操作 同样适用于后文将要介绍的二叉树编码生成算法中，这样就建立了二义树、二叉树的编码以 及二义树排名三者之间的一一对应的关系。在第3 章我们将详细讨论。 第1 0 页 二叉树枚举算法的研究第3 章- 二叉树的枚举生成算法 第3 章二叉树的枚举生成算法 树在计算机内的表示主要是借助于指针实现的，所以最直接的办法就是在树的指针结构 下设计枚举生成算法。但是，事实证明：使用树的指针结构设计生成算法不是一个很好的选 择。本文将要介绍的基于编码的二叉树枚举生成算法避免了对指针的操作，降低了时间和空 间开销。 目前主要有四种编码模式下的二义树生成算法 2 , 2 8 】，即基丁树排列( t r e e p e r m u t a t i o n s ) 的编码生成算法、基于旋转( r o t a t i o n s ) 的编码生成算法、广义模式( g e n e r a ls c h e m e ) 下的 编码生成算法、基于文法( c o n t e x t - f r e eg r a m m a r ) 的编码生成算法。这些算法都是先建立二 叉树集合与编码集合之间的一一对应的关系，然后将二叉树的枚举生成问题转化为编码的枚 举生成问题i ”1 。 3 1 二叉树的编码过程 图3 1 给出了一种编码过程的示意图。对于图中编码过程得到的n 元组和整数排名我们 都可以称作“编码”，这丝毫没有引起概念上的混淆。 ，x 2 ，x ”) 二叉树编码 1 ，翻 二叉树“怕n k _ n g 排名整数 图3 1 二又树编码过程示意图 f i g 3 1c o d i n ga n dd e c o d i n g 借助于一定的编码方法，我们就可以得到一棵二义树对应的编码，这样的编码称作“有 效的( f e a s i b l e ) ”编码。显然，有效的编码至少要满足两个条件。第一编码