第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