核心算法

上次讲到用链表或者数组去写完全二叉搜索树的利弊，接下来就要考虑核心算法了。

首先我们来解决一下样例输入对应的问题，然后再从解决样例问题的过程中去找规律，来得到我们真正的核心算法，那么这个题一开始要怎么想呢？首先要看一下二叉搜索树的概念，在一棵二叉搜索树里面，根结点左边所有的元素都比它小，右边的都比它大，那换言之，如果我知道它的左子树一共包含了多少个结点，那我就知道根结点上要放的数字一定是从小到大排第几位的那个数字，那我怎么能够确定的知道左子树有多少个结点呢？这就用到了完全二叉树的概念，因为给定了一个固定的n以后，这个完全二叉树的结构是固定的，所以我可以非常准确的算出来它的左边一共有多少个结点，那在这种情况下呢，首先我把我的输入的序列从小到大排一个序，然后根据这棵完全二叉树一共有多少个结点，这个总结点的个数，我是可以导出一个公式，来精确的计算它的左子树，一共有多少个结点，那比如说在这个问题里面，n是等于10的，我一共有10个结点，那么我可以很准确的算出来，它的左子树必定含有6个结点，也就是说根结点一定是从小到大排第7位的那个数字，那在这里头我先数过6个数，第7个数就一定是它的根结点，同时也就决定了后面的3个数一定是属于它的右子树的，于是在这个位置上呢(指根结点)我实际上应该填的就是6

在填完这个6以后呢，你应该已经看出来了，我们就可以很容易的，递归的去分别解决左边和右边的问题，因为什么呢？因为如果这棵树是一棵完全二叉树的话，它的左子树和右子树，一定也是完全二叉树，于是我们就完全变成了左边和右边完全小一号的问题，比如说左边就含有6个结点，6个结点的完全二叉树，它根结点的左子树一定包含3个结点，于是呢，我从这数前面3个数，我就知道3一定要被填到根结点这个位置的

同时它的右子树一定包含4和5，然后就可以把3填在根结点处，然后递归去解决它的左子树的问题，这个左子树包含3个结点，作为一棵完全二叉树来说它的结构是非常简单的，

它的根节点应该是中间的1，左边是0，右边是2，然后递归的去考虑它的右子树，具有两个结点的完全二叉树一定是长成(4,9)这个样子的，就是一个根结点加一个左子树，所以根结点一定是5，左子树一定是4。右子树就更简单，3个结点，然后它是完全对称的，所以它的根结点是中间的8，左边是7，右边是9。

这样就完成了我们的填写，从刚才我们填写的过程中，这实际上是对这棵树的一种先序遍历，每到一个根结点的时候，我就要先从这个序列里面找到谁应该是根结点，先把它填上，然后再递归的解决左边，递归的去解决右边，这就是一个非常典型的先序遍历的应用，那么代码要怎么写呢？

传进去的参数主要有这么3个，我们来分别的看一下，假设在调用这个solve之前，我已经把输入序列存在一个数组A里面，然后把这个数组A做了一个从小到大的排序，就是排序以后的输入序列是放在A里面的，当我在递归调用去解决这个问题的时候呢，我对应的是A这个序列里面的某一小段，这个ALeft存的就是当前这一段最左边元素的下标，ARight就是存的是最右边元素的下标，TRoot是什么东西呢？我们把最后结果生成的那棵树也存在另外一个数组叫做T里面，TRoot对应的是当前我们要考虑的这棵子树，它的根结点所在的位置，这个元素的下标存在TRoot里面，在main函数里面最开始调用solve这个函数的时候，在A的起始点，就是A的第0个元素，A的终止点就是A的最后一个元素，就是N-1是它的下标，对应这棵结果树它是一个完全二叉树，它的根结点一定存在T0这个位置，所以TRoot最开始传进去的是0，整个函数要完成的任务，就是从A传进去的这一段里面选出一个正确的数字填到结果树TRoot的位置上，好了，做好了一切准备工作，就开始干活了。要干的第一件事，要想到solve是一个递归的函数，递归函数必须要有一个停止的条件，什么时候停止呢？先计算一下n当前传进来这一段数组元素一共有多少个，那么就是最右边的下标减去最左边的下标加上1，就得到了这一段里面元素的总个数(n=ARight - ALeft + 1),如果n等于0，那就没有任何元素可以处理了，这是它的最小情况，直接return什么事情都不做，如果n不等于0的话，那我们要选一个正确的数字，填在根结点的位置上，这个正确的数字要怎么选呢？首先要算出来它的左子树到底包含多少个结点，然后那个左子树右端点的下一个元素就应该放在根结点的位置上，要怎么样知道左子树的规模呢？这还不是一个很简单的事情，在这呢，我就先把它记成一个函数(L = GetLeftLength(n)),传进去的这个n呢，是当前这棵完全二叉树总结点的个数，返回的就应该是有n个结点的树，就不是一棵普通的树，就是一棵完全二叉树，它左子树一共有多少个结点，现在先不管它是怎么做的，总之它把这个树给返回来了，也就是左边一共有L个元素(L = GetLeftLength(n)),那么根结点的元素就应该填什么呢？A[ALeft + L]这个位置上这个源应该被填到T的根结点位置上去(T[TRoot] = A[ALeft + L]),到此为止，我们就应该把这个函数应该干的活干完了，接下来就是要递归的解决左边递归的解决右边，于是我们得把左边给定义好，右边也要定义好，左边的A的元素值是很明显的，就是从ALeft一直指到哪里呢？指到这个元素的前一个，把这一段作为A的左段，传到下一个solve里面去，但是左边要传进去的TRoot应该传什么呢？当前的根结点的下标是TRoot，这个结点在完全二叉树里面左孩子的下标应该是多少呢？那么在之前讲堆的时候，应该讲过，如果根结点是TRoot的话，那么它的左孩子的下标应该是TRoot乘以2，但是你要小心，那是在堆里面，堆的特点是它的第0个元素，是不存真实值的，它只存一个哨兵，但是在我们这个结果树里面，我的根结点是直接放在0里面的，是从0开始算下标的，而在这个微小的差别之下，它的左孩子就不是TRoot乘以2，而是TRoot乘以2再加1，在头脑里想一下，我从0开始，第0个元素它的左孩子下标应该是1，也就是2乘以0再加上1，它的右孩子的TRoot的下标就很简单，就是左孩子加1，就是它的右孩子，如果你不放心，在往下推一下看看，1它的左孩子下标应该是什么，应该是3对不对，就是1乘以2再加1得到3，右孩子下标就是4，以此类推，这样我们就得到了在T这棵树里面，当前这个根结点左孩子的下标和右孩子的下标，现在我们就可以递归的去解决左边，递归的去解决右边，解决左边的时候呢，它的左端点还是ALeft不变，右端点是你刚才取掉了根结点那个元素的前一个值，所以是ALeft+L-1,然后这边传的是TRoot左孩子的下标(solve(ALeft, ALeft+L-1, LeftTRoot)),LeftTRoot是下一个要填的根结点，右边呢，对应的应该是刚才那个根结点加1，是右边的左端点，然后右边的右端点是不变的，传进去根结点的下标就是TRoot它的右孩子，

那么到此为止，我们这个核心算法就描述完了，

但是真的要去实现这个程序的时候，还有两个很关键的步骤，第一件事先得会排序，排序算法会在很后面的时候才给大家专门的介绍，那在这里头要用到排序呢，先给大家介绍一个比较简单的现成的库函数，可以先凑合着用着。

这里要跟大家介绍的是C语言里很好用的库函数叫做qsort，你要用qsort的话，你先要#include <stdlib.h>,把这个头文件包进去，然后就可以在main函数里面去对这个数组做预处理，调用qsort，要传进去的参数是有这么4个关键的参数，qsort的第一个参数要传进去的是待排序序列的首元素的位置，也就是说如果我们把读进来的原始的输入存在一个叫A的数组里面，那我只要把这个数组的名字放在这就可以了，后面这个N呢，是你待排序列的总长度，也就是一共要排n个元素，第三个参数传的是你要排的那个元素的大小，那在这道题里面，我们只是要对整数做一个排序，所以传进去的就是sizeof(int),如果在后面我们调用qsort做更复杂的排序的时候，有的时候我们需要传入一个结构体，那么这个就应该是sizeof那个结构体的大小，有趣的是最后一个参数，这个最后一个参数不是一个变量，它是一个函数的名字，这个函数我在这给它取一个名字叫做compare,你可以给它取叫别的名字，这个compare要做的事情是什么呢，就是要比较两个元素的大小，因为qsort是通过比较一对元素的大小来决定哪个元素在前面，哪个元素应该在后面，就我们这道题里面，compare应该怎么写呢？

这是compare的标准接口，不管前面给它取什么名字，它应该返回一个整数，让它传进去的是两个待比较元素的指针，它应该返回的整数，是返回3种整数之一，可以返回一个负数，可以返回一个0，也可以返回一个正数，然后qsort就根据这个compare返回来的是负数，是0，还是正数，来决定这两个元素谁应该在前面，谁应该在后面，还是彻底的不做交换，那么在我们这个问题里面，我可以非常简单的把这个return值就写成a减去b的值，将来你要用qsort对更复杂的数据结构做排序的时候，这个compare可以写的非常复杂，总之这个compare函数是要你自己根据实际情况来实现的。