所谓分治法，简单概括就是将暂且不能解决的大问题分成很多子问题，如果子问题还是不能解决则继续划分，直到子问题小到可以直接解决的规模，原问题的解即为子问题解的合并。

说明：虽然分治法在考研中不会单独拿出来考查，但是它对考研要求的一些算法的理解有很大帮助，这里通过几个例题，由简到难来体会一下。

【例10-1】 用分治法打印数组a[L，…，R]。

分析：

一个循环就可以，但用分治法来解决该怎么做呢？如果待打印序列长度为1，则可以直接打印；如果待打印序列长度为N，则可以将其划分为两部分：第1个元素是一个划分，后N-1个元素是另一个划分。第一个划分可以直接打印，然后将后N-1个继续划分，直到数组长度为1，可以直接打印，或者长度为0，什么也不做。

由此可以写出以下代码：

♥感觉分治法难以理解？请扫描本书封面二维码，那里有详解视频，可能会对你的理解有帮助。

【例10-2】 假设存在一个函数divid（），可以将一个数组a[L，…，R]分成两部分，元素a[L]为分界线，小于a[L]的元素在左边，大于a[L]的元素在右边。

函数divid（）的声明如下：

int divid（int a[]，int L，int R）；

试用分治法，对数组a[L，…，R]中的元素进行快速排序。

分析：

如果序列长度小于等于1，则默认为是有序的；如果序列长度大于1，则用函数divid（）将其划分成3部分：左边是小于a[L]的部分，中间是a[L]，右边是大于a[L]的部分。a[L]已经有序，则只需对其左右两部分继续进行分治处理即可。

由此可以写出以下代码：

【例10-3】 一棵二叉树存储在二叉链表中，用分治法打印所有结点值，根结点由p所指。

分析：

当树为空时，什么都不用做，问题直接解决。当树中结点数大于等于1时，可用根结点将整棵树划分，分为根、左子树和右子树3部分，根结点直接打印，对左子树继续分治处理，对右子树继续分治处理，最终可以打印整棵树。

由此可以写出以下代码：

(www.daowen.com)

说明：以上就是二叉树先序遍历的分治法解释。

【例10-4】 一个连通图G用邻接表存储，用分治法打印图中的所有顶点值，假设图中结点数大于1。

分析：

如图10-1所示，假如从顶点v开始打印，则可以将整个图分成n部分，由v引出的一条边算一部分，这与例题10-3的情况类似，二叉树用根结点将整棵树划分成根、左子树和右子树，而这里划分为v、第1条边所到达的子图、第2条边所到达的子图……第n条边所到达的子图。v可以直接打印，然后对各个子图继续进行分治处理。因为图中可能有回路，所以需设置访问标记数组visit[]来检测当前的划分是否需要处理。

由此可以写出以下代码：

图10-1 例10-4图

说明：这就是图的深度优先搜索遍历的分治法解释。

【例10-5】 已知二叉树的先序遍历序列和中序遍历序列，分别存储在a[L1，…，R1]与b[L2，…，R2]两个数组中，用分治法由这两个序列建立一棵二叉树，并存储在二叉链表存储结构中。

分析：

如果为空序列，则什么都不做，问题可以直接解决；如果序列长度大于1，则a[L1]为二叉树的根结点，在b[]中找到a[L1]，假设下标为k，则b[L2，…，k-1]是其左子树上的所有结点，b[k+1，…，R2]是其右子树上的所有结点。反映在a[]中，即a[L1+1，…，L1+k-L2]是其左子树上的所有结点，a[L1+k-L2+1，…，R1]是其右子树上的所有结点。这样对a[L1+1，…，L1+k-L2]与b[L2，…，k-1]继续进行分治处理，对a[L1+k-L2+1，…，R1]与b[k+1，…，R2]也继续进行分治处理，最终可以将树建立完毕。

由此可以写出以下代码：

【例10-6】 汉诺塔问题，有3根柱子：x、y、z，第一根柱子上有n个盘子，从上到下依次增大，要求将第一根柱子上的所有盘子移动到第三根柱子上，整个过程都必须满足一根柱子上的盘子从上到下依次增大。

分析：

这个是利用分治法解题的经典题目，过程如下：如果第一根柱子上只有1个盘子，则直接移动即可；如果第一根柱子上的盘子大于1个，则将柱子上的盘子划分成两部分，最下边的盘子为一部分，上面的n-1个盘子为另一部分。对上面的n-1个盘子继续分治处理，将其先移动到第二根柱子上，此时第一根柱子上只有1个盘子，可直接移动到第三根柱子上，然后将第二根柱子上的n-1个盘子继续分治处理，移动到第三根柱子上，此时整个问题解决。

由此可以写出以下代码：