二叉树的顺序结构及实现

3. 二叉树的顺序结构及实现

我们先来学习二叉树的顺序结构及其实现。

3.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。

而完全二叉树更适合使用顺序结构存储。

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

接下来我们将重点学习一下堆。

3.2 堆的概念及结构

那什么是堆呢？

堆其实是一棵二叉树，更准确一点说，它是一棵完全二叉树。

堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。

堆通常是一个可以被看做一棵完全二叉树的数组对象。

那具体的概念是什么呢？

如果有一个关键码的集合K = {k1, k2 ,… , kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足以下条件，则称为堆：

1. 如果该完全二叉树中所有的父亲结点的值均大于等于其孩子结点，则称其为大堆或大根堆。

如果该完全二叉树中所有的父亲结点的值均小于等于其孩子结点，则称其为小堆或小根堆。

注意：

堆只有大堆和小堆。

所以说:

堆是一个一维数组，但是随便给你一个一维数组，它就不一定是堆了，因为必须满足大堆或小堆的特征，才能叫做堆。

堆的性质

1. 堆中某个节点的值总是不大于或不小于其父节点的值；
2. 堆总是一棵完全二叉树。
3. 堆的逻辑结构是一棵完全二叉树，但是其物理结构，即实际的存储结构是一个一维数组。
4. 
5. 其在数组中存储的顺序就是对其做层序遍历的顺序。

🆗，那大家接下来再思考一个问题：

堆是一棵完全二叉树，但是它存储在数组里面，那我们如何找一个结点的孩子或是它的双亲结点呢？

如果是链式存储，我们直接通过它的左右孩子指针就能找到，那顺序存储呢？

其实它们的下标之间是有关系的。

孩子结点和父亲结点的下标关系

双亲结点找孩子：

左孩子：leftchild=parent x 2+1

右孩子：rightchild=parent x 2+2

我们来看一下是不是：

大家可以试一试，是完全正确的。

注意：

如果parent*2 再+1或+2之后超出了下标范围，就证明该结点没有对应的左孩子或右孩子。

那如何通过孩子找双亲结点呢？

不管是左孩子找双亲，还是右孩子找双亲，都满足：

parent=（ child - 1 ）/ 2

我们可以发现，所有结点的左孩子下标都是奇数，右孩子下标都是偶数，但是它们减1除2的结果是一样的（因为C语言中是整除），最终都等于它们双亲结点的下标。

🆗，那接下来我们一起来看一个题：

这个怎么判断呢？

我们说堆虽然物理结构是一个一维数组，但是逻辑上是一个完全二叉树，所以我们只需要将它转化成完全二叉树，然后就可以判断它是不是堆了。

我们判断一下会发现其实A选项就是一个堆。

将A选项的数组转换为完全二叉树：

是不是很容易看出来是一个大堆啊。

所以答案就是A，其它的大家可以自己判断一下。

3.3 堆的实现

接下来我们就一起来用C语言实现一下堆：

常用的接口：

// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

我们这里呢采用顺序结构来实现堆，其实就是用数组来实现，那我们建堆肯定要向数组中插入元素，那我们就可以搞一个动态数组，空间不够可以扩容。

那就需要一个变量来记录数组大小，当然还有容量。

所以，堆的结构我们就可以这样定义：

typedef int HPDataType;
struct heap
{
    HPDataType* arr;
    int size;       //数组大小
    int capacity;  //容量
};

大家看这个结构是不是和我们之前写的顺序表很一样啊。

那我们可以直接把初始化和销毁的函数直接写一下，就和顺序表一样：

//初始化堆
void HeapInit(hp* php)
{
    assert(php);
    php->arr = NULL;
    php->capacity = php->size = 0;
}
//销毁堆
void HeapDestory(hp* php)
{
    assert(php);
    free(php->arr);
    php->arr = NULL;
    php->capacity = php->size = 0;
}

那我们继续。

大家再来思考一下，我们向堆里面插入新数据的时候，可能是任何值，可能大可能小。

但是堆是对数据有要求的，大堆要求所有的父亲结点的值大于它们对应的孩子；小堆要求所有父亲结点小于其孩子。

所以呢，我们向一个堆中插入一些新的数据，插入之后它可能就不是堆了。

那怎么办呢？

那在每次插入新数据之后，我们就要对堆进行检查和调整，确保在加入新的数据之后，它还是一个堆。

那如何调整，这就是我们接下来要学习的：

3.3.1 堆的向上调整算法

1. 铺垫及其前提

那假设现在有这样一个堆：

是一个大堆，那我们现在要插入新数据，并且要保证插入之后的堆还是一个大堆。

首先大家想一下，是不是插入任何一个数据，我们都要对堆进行调整？

🆗，不是的，如果插入之后，它直接就满足当前对应的堆的特征，那就不用调整了。

举个栗子：

就上面那个堆，假设我们现在再插入一个数据12：

大家看需要调整吗？

是不是不用了，原来是个大堆，插入之后还满足是一个大堆。那就不用动了。

那需要调整的情况呢？

现在我们要插入一个100。

🆗，大家看现在这样还是大堆吗？

是不是已经不是大堆了啊。

那要怎么调，大堆需要满足什么条件，任意一个父亲结点都要大于它的孩子，那现在是不是存在不满足条件的树啊。

2. 算法讲解及实现

那我们开始调整：

怎么调？

首先进行向上调整要保证之前的数据必须是一个堆。

然后看插入的数据满足不满足对应的大小关系，不满足就进行交换，直到满足为止。

100这个结点是不是大于它的父亲啊，那大堆中大的才应该做父亲，所以呢，就应该交换100和30这两个结点。

那调整一次就完了吗？

如果调整一次后满足了，那确实就结束了，但是现在是不是还不满足是一个大堆啊，那就要继续调整。

100还是大于它的父亲70：
所以：

这个调整应该是一个循环的过程，那循环什么时候结束呢？

当调整到所有结点都满足大堆或小堆的关系时，或者需要一直调整，当插入的新数据一直交换到成为根结点时就结束了。

当然如果插入的数据直接满足，那一次也不需要调整。

我们把这种从下往上调整的算法叫做向上调整。

大家思考一下，向堆中插入一个元素，时间复杂度是多少？

最坏的情况需要交换多少次，最坏情况就是插入的数据需要一直交换到成为根结点，那就是高度次。

所以应该是log2(N)。

接下来我们就来实现一下向上调整算法：

代码：

//交换
void swap(HPDataType* e1, HPDataType* e2)
{
    HPDataType tmp = *e1;
    *e1 = *e2;
    *e2 = tmp;
}

//向上调整
void AdjustUp(HPDataType* arr, int child)
{
    assert(arr);
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (arr[child] > arr[parent])
        {
            swap(&arr[child], &arr[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

那要是对小堆进行向上调整呢？

很简单，只需要把上面向上调整算法中比较的>换成<就行了。

if (arr[child] < arr[parent])

那我们现在写一下插入数据的函数，插入完直接调用向上调整函数进行调整：

//插入数据，并保证它仍然是一个堆
void HeapPush(HP* php, HPDataType x)
{
    assert(php);
    //判断堆是否满，满的话进行扩容
    if (php->size == php->capacity)
    {
        int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);
        HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        php->arr = tmp;
        php->capacity = newcapacity;
    }
    php->arr[php->size] = x;
    php->size++;
    //向上调整
    AdjustUp(php->arr, php->size - 1);
}

3. 向上调整建堆

那其实我们现在就可以建堆了，怎么建？

直接一个一个进行元素的插入就行了，插入一个调整一次，插入一个调整一次，堆不就建成了。

int main()
{
    int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
    HP hp;
    HeapInit(&hp);
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
    {
        HeapPush(&hp, arr[i]);
    }
    HeapPrint(&hp);
    HeapDestory(&hp);
    return 0;
}

这样一个大堆就建成了。

如果向建成小堆，只需把向上调整算法中的>换成<就行了。

3.3.2 堆的向下调整算法

1. 铺垫及其前提

现在我们已经可以建立一个大堆或小堆了，那大家思考一下，堆这种数据结构有没有什么特别的价值，或者说有什么作用？

可能大家都听说过一种排序叫做堆排序。

🆗，这确实是堆的一个应用。不过除此之外，堆还可以用来解决另外一个问题：

叫做Top-K问题：即在一组数据中找出最大或最小的前K个数据。

那大家思考一下，为什么用堆可以解决TOP-K问题呢？

因为在一个大堆中，堆顶的元素（即根结点）的值一定是最大的，相同道理，小堆的堆顶一定是最小的。

那我们取出堆顶的数据，就取出了这组数据中最大或最小的那个数据了。

但是TOP-K问题不是只取一个最值，我们要取出前K个，也就是说接下来我们要想办法取出次大的数据。

那我们是不是应该把第一次取出来的数据从堆中删除啊。

那现在就有一个新的问题：如果正确的从堆中删除一个数据？

我们现在实现的堆是存放在数组中的，那堆顶的元素是在下标为0的位置的。

我们可不可以用常规的数组头删的方法，直接移动后面的元素覆盖呢？

这样做不太行。

为什么不行？

有两点原因：

1. 首先这样挪动数据效率比较低。
2. 另外，最主要的一点，这样做导致堆原来建立起的关系就乱了。

举个栗子：

这是我们刚才在上面建立好的一个大堆：

大家看，我们这样删除的话，关系 是不是就乱了。

我们之前辛辛苦苦建立起来的关系，建立的“族谱”，就被破坏了。

本来呢，49和34两个人说好了，我们要做一辈子的好兄弟，结果呢，你49却想去当34的爸爸，这样可不行啊。

而且，我们看对于当前这个堆来说，删除堆顶元素之后其实就不再是一个大堆了。

所以这种删除的方法就不是很好，那有没有更好一点的呢？

有大佬呢就想出了这样的方法。

说与其向上面那样把整个“家族”的关系都搞乱了，倒不如先做一个小的变动。

怎么搞呢？

先不直接删除，先拿堆中的最后一个“子孙”和堆顶的元素进行一下交换。

为什么这样做呢？

这样交换以后再删除是不是就比较方便了啊。

因为我们要删除的就是堆顶的元素，把它交换到数组的最后一个位置，数组头删不方便，尾删是不是很easy啊，直接size- -就把最大值删除了。

那删除之后是不是就完事了？

不是滴，虽然现在最大值我们已经可以直接删除了，但是删除完我们就可以直接取次大的了吗？

还不行，因为我们刚才把堆中最后一个元素交换到了堆顶，那大堆的最后一个数据，不敢保证是堆中最小的，但也是比较小的吧。

所以呢意思就是虽然把你推上位了，你成功坐到了堆顶的位置，但是，你撑不住啊！！！

因此，还需要进行一些调整。

虽然还是需要我们进行调整，但是：

我们看他现在的结构有一个特点：

就是它的左右子树并没有得到破坏，仍然保持是一个堆。

这也是向下调整算法的一个前提：

左右子树必须都是堆堆，才能调整。

向上和向下调整我们放在一起回忆一下：

向上调整算法的要求原来的数据必须是一个堆；

向下调整算法要求左右子树必须都是堆。

2. 算法讲解及实现

🆗，铺垫了这麽久，接下来我们就来学习一下如何进行向下调整。

我们接着上面的往下看：

现在这个堆是这样一个状态：

我们把18推上去了，但是它撑不住啊！

它没能力坐稳这个位置啊，所以我们要进行调整，使得他还得是一个大堆，这样我们才能继续取下一个次大的值。

如何调整：

其实思路跟向上调整一样，只不过这次我们是从上往下，不符合关系的进行交换，直至使它成为一个新的大堆。

我们开始调整：

18在这里肯定不合适，它比自己的孩子还要小，所以要交换。

和谁交换？

34可以吗，34换到堆顶，它是不是还撑不住啊。

所以我们要选择它的孩子中大的那一个进行交换。

那在这里就是49。

那现在18坐到原来49的位置，现在这个位置怎么样？

🆗，18是不是还是坐不稳啊。

还得进行交换。

选择18的孩子中大的那一个交换：

现在是不是就可以了啊。

我们交换了两次完成了，所以这还是一个循环的过程。

那这个循环的交换过程应该什么时候停止？

是不是当交换到满足大小关系或者一直交换，直到自己成为叶子结点时结束啊。

那接下来就来实现一下代码：

//向下调整
void AdjustDown(HPDataType* arr, int size, int parent)
{
    assert(arr);
    int child = parent * 2 + 1;
    while (child < size)
    {
        //得出较大的那个孩子
        if (child + 1 < size && arr[child + 1] > arr[child])
        {
            child++;
        }
        //如果孩子大于父亲，就交换
        if (arr[parent] < arr[child])
        {
            swap(arr[child], arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        //如果小于孩子，调整结束
        else
        {
            break;
        }
    }
}
//删除堆顶元素，并确保删除之后还是一个堆
void HeapPop(HP* php)
{
    assert(php);
    assert(php->size > 0);
    swap(&php->arr[0], &php->arr[php->size - 1]);
    php->size--;
    //向下调整
    AdjustDown(php->arr, php->size, 0);
}

算法写好了，我们来验证一下好吧：

我们对上面建好的那个堆先删除一下堆顶元素，在打印出来，看看是不是还保持是一个堆。

🆗，没有问题，跟我们画图得出的结果是一样的。

3.3.3 剩余接口实现

// 取堆顶的数据
HPDataType HeapTop(HP* php)
{
    assert(php);
    assert(php->size > 0);
    return php->arr[0];
}
// 堆的数据个数
int HeapSize(HP* php)
{
    assert(php);
    return php->size;
}
// 堆的判空
bool HeapEmpty(HP* php)
{
    assert(php);
    return php->size == 0;
}

3.3.4 堆的构建

其实在上面我们已经建立过堆了：

但是上面我建立堆是一个数据一个数据去插入，然后经过调整形成一个堆。

1. 向下调整建堆

但是上面那种方式去建堆其实不是特别好（时间复杂度是N*log2N，我们后面会证明） ，有些地方会让我们这样去建立一个堆：

就是给我们一个数组，数组的元素可能是任意值，我们需要将这个数组进行一些处理使它变成一个堆。是直接对数组进行操作，而不是像上面那样，将数组中的元素一个一个的插入去建堆。

下面我就来实现一下这个构建堆的方式：

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。

int arr[] = {27,15,19,18,28,34,65,49,25,37};

那应该怎么做呢？

🆗，我们知道它的逻辑结构是一棵二叉树，那如果它的左右子树已经是一个堆的话，我们就可以很容易将整棵树调整成一个堆。

怎么调整我们上面是不是已经讲过了：

如果它的左右子树已经满足是一个堆，我们可以利用向下调整算法将它变成一个堆。

那我们给的数组可能是随便给的，它的左右子树有可能都不是堆，那我们要如何处理呢？

也就是说现在不具备左右子树都是堆的条件，那怎么办？

既然没有条件，那我们就创造条件嘛！

先想办法把左右子树变成堆就行了。

我们先将给的数组int arr[] = {27,15,19,18,28,34,65,49,25,37};转换为对应完全二叉树：

那要想让它的左右子树都变成堆，我们可以从最后一个结点开始，向前依次调整。

但是，最后的这几个叶子结点，是不是可以直接略过不用管啊，因为这几个没有孩子结点，你可以把它看成一个大堆，也可以看成小堆。

所以，我们只需从倒数第一个非叶子结点开始，依次向前对每一棵子树进行向下调整将其变为堆，这样在调整前面结点的时候，它们对应的左右子树就已经满足是堆了，一直到将根结点调整完，堆就建好了。

那现在又有一个问题：

我们要从倒数第一个非叶子结点开始往前调，那怎么找到倒数第一个非叶子结点呢？

其实观察一下可以发现，倒数第一个非叶子结点就是最后一个结点的父亲结点。

假设最后一个结点的下标是n-1，那倒数第一个非叶子结点的下标就是(n-1-1)/2 。

那我们接下就来实现一下这个构建堆的算法：

// 堆的构建
void HeapCreate(HP* php, HPDataType* arr, int size)
{
    assert(php);
    php->arr = (HPDataType*)malloc(sizeof(HPDataType) * size);
    if (php->arr == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    memcpy(php->arr, arr, sizeof(HPDataType) * size);
    php->capacity = php->size = size;
    for (int i = (size - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(php->arr, size, i);
    }
}

由于我们这里是直接对数组操作，所以我们直接把给的数组使用memcpy拷贝到堆中，然后调整。

那算法写好了，我们来验证一下：

就用上面那个数组，我们现在尝试用该算法将数组直接构建成一个堆。

🆗，一个大堆就构建好了：

2. 向下向上调整建堆的时间复杂度

我们刚才建堆其实是用向下调整的算法建堆的：

给一个数组，把它看成一个完全二叉树，然后从倒数第一个非叶子结点开始往上依次对每个结点进行向下调整，最终构建一个堆。

那接下来，我们来算一下这种建堆方式的时间复杂度：

我们说算一个算法的时间复杂度，我们通常考虑的都是最坏的情况，那向下调整建堆什么样的情况会是最坏的情况呢？

我们调整的对象是什么：

是一个数组，但是我们要把它看作一个完全二叉树去调整，那什么样的完全二叉树需要调整的次数会尽可能多呢？

是不是满的情况啊：

我们知道满二叉树是一种特殊的完全二叉树。

那在是一棵满二叉树的基础上，什么情况下需要调整次数最多？

是不是所有非叶子结点和它的孩子结点的大小关系都不满足，都需要交换且需要交换到最后一层才满足大小关系，这时是最坏的情况。

所以就是这样的：

那总次数怎么算，其实就是前h-1层的结点个数乘以它们要交换的层数。

因此：向下调整建堆的时间复杂度为O(N)。

🆗，那趁热打铁，我们再来算一下向上调整建堆的时间复杂度：

那总次数就是第2到最后一层所有结点需要调整的次数之和。

详细计算过程就不写了，最后 得出的时间复杂度是N*log2N。

所以说，向上调整建堆没有没有向下调整建堆优。

3.为何向下调整建堆更优

那我们来分析一下，为什么向下建堆更优更快呢？

大家看，向下建堆我们是从倒数第一个非叶子结点开始往上调整，最后一层的结点我们是不是不用管啊，那如果在像这种是满二叉树的最坏情况下:

结点总数是2^h-1个

但最后一层就有2^(h-1)个，占了一半都有了。

而且，越靠下层，结点个数越多的，调整的次数越少，因为是向下，上面的调整次数虽然变多了，但是结点个数就很少了。

那向上调整正好反过来了，那效率可不就低了嘛。

所以呢：

今后建堆，我们建议大家选择向下调整算法来建堆。