第26章 二叉树 /1

26.1 二叉树的基本概念 /1

26.2 二叉树的性质 /2

26.3 二叉树的存储结构 /3

26.3.1 二叉树顺序存储 /3

26.3.2 二叉树链式存储 /3

26.4 二叉树层次遍历 /5

26.4.1 层次遍历 /6

26.4.2 把二叉树的顺序存储转为

链式存储 /7

26.4.3 垂直输出二叉树 /7

26.5 二叉树前序遍历 /11

26.5.1 前序遍历递归算法 /11

26.5.2 前序遍历非递归算法 /12

26.5.3 快速排序 /12

26.5.4 集合的幂集 /14

26.6 二叉树中序遍历 /16

26.6.1 中序遍历递归算法 /16

26.6.2 中序遍历非递归算法 /17

26.6.3 汉诺塔递归算法 /18

26.7 二叉树后序遍历 /19

26.7.1 后序遍历递归算法 /19

26.7.2 后序遍历非递归算法 /20

26.7.3 求二叉树深度、二叉链表的复制

和删除 /20

26.7.4 把二叉树的顺序存储转为链式

存储的递归算法 /22

  26.7.5 由前序和中序序列建立二叉

链表 /22

习题26 /24第27章 堆 /25

27.1 小根堆Heap类 /25

27.2 堆排序 /29

27.3 哈夫曼树 /32

27.3.1 哈夫曼树的定义 /32

27.3.2 建立哈夫曼树 /32

27.3.3 哈夫曼编码 /35

习题27 /35

第28章 树 /36

28.1 树的基本概念和存储 /36

28.2 Tree类 /39

28.3 树的遍历 /43

28.4 八皇后 /45

习题28 /49

第29章 图 /50

29.1 图的基本概念 /50

29.2 Graph类 /52

29.3 图的遍历 /59

29.3.1 广度优先遍历 /59

29.3.2 深度优先遍历 /61

29.4 最小生成树 /63

29.4.1 普里姆算法 /64

29.4.2 克鲁斯卡尔算法 /70

29.5 最短路径 /73

29.5.1 单源最短路径迪克斯特拉算法 /73

29.5.2 所有顶点对之间的最短带权路径 /79

29.5.3 一顶点对之间的最短带权路径 /84

29.6 拓扑序列 /86

29.7 关键路径 /90

29.8 迷宫求解 /93

习题29 /97

第30章 二叉搜索树 /98

30.1 类型声明与实现 /98

30.2 中序迭代器 /104

30.3 频率统计 /106

30.4 中序线索二叉树 /108

习题30 /109

第31章 平衡二叉搜索树 /110

31.1 动态平衡方法 /110

31.2 二叉平衡搜索树类型 /113

习题31 /116

第32章 B树 /117

32.1 线性索引 /117

32.2 静态m路搜索树 /118

32.3 B-树 /119

32.4 B+树 /122

第33章 散列 /124

33.1 散列表 /124

33.2 散列函数 /125

33.2.1 平方取中法 /125

33.2.2 除留余数法 /125

33.2.3 折叠法 /126

33.2.4 数字分析法 /126

33.3 分离链接法 /126

33.4 开放定址法 /129

33.4.1 线性探查法 /129

33.4.2 平方探查法 /130

33.4.3 双散列函数探查法 /130

习题33 /130第34章 排序 /131

34.1 性能分析 /131

34.1.1 时间复杂性分析 /131

34.1.2 空间复杂性分析 /132

34.2 插入排序 /133

34.2.1 直接插入排序 /133

34.2.2 折半插入排序 /134

34.2.3 希尔排序 /135

34.3 交换排序 /136

34.3.1 起泡排序 /136

34.3.2 快速排序 /137

34.4 选择排序 /138

34.4.1 直接选择排序 /138

34.4.2 堆排序 /139

34.4.3 锦标赛排序 /140

34.5 归并排序 /144

34.5.1 归并 /144

34.5.2 迭代的归并排序 /145

34.6 基数排序 /146

34.7 外排序 /148

34.7.1 外排序基本过程 /148

34.7.2 k路归并 /149

习题34 /151

参考文献 /152