《树的枚举与算法复杂性分析》求取 ⇩

第一章绪论1

1.1 数学中的树和计算机科学中的树1

1.2 树结构上的算法和复杂性分析8

1.3 树的枚举9

1.4 本书的研究对象及其同若干学科的关系10

1.5 定义和术语11

1.6 算法描述语言SL14

第二章预备知识18

2.1 生成函数18

2.2 反演公式22

2.3 差分方程与递推关系23

2.4 置换群与波利亚（Pólya）定理26

2.5 渐近分析31

2.6 树图32

第三章各种树枚举问题37

3.1 按节点个数的树枚举38

3.2 按节点和叶子个数的树枚举41

3.3 更一般的树枚举56

第四章树上的各种枚举问题66

4.1 叶子枚举66

4.2 通路长度的枚举78

4.3 带次数通路长度的枚举88

5.1 树上可加枚举问题的概念94

第五章树上的可加枚举问题94

5.2 若干具体树族上的可加枚举问题96

5.3 简单生成树族上的可加枚举问题107

5.4 甚简单生成树族上的可加枚举问题110

5.5 有序树族上的几个等分问题118

5.6 有向树上的可加枚举问题129

5.7 第二类可加枚举问题137

5.8 更一般的可加枚举问题147

5.9 其他类型的可加枚举问题152

5.10 可加枚举问题的实用求解156

6.1 分治原理165

第六章树结构上的可加复杂性算法165

6.2 递归过程和递归下降法168

6.3 树结构上可加复杂性算法的概念171

6.4 递归可加复杂性算法的时间特性分析174

6.5 树的枚举与树结构上算法复杂性分析之间的关系189

第七章几个具体算法的复杂性分析192

7.1 树的遍历算法192

7.2 多路搜索树算法的复杂性分析219

7.3 检索树（trie）算法分析232

7.4 穿线树上的算法分析239

附录248

参考文献260