0
0

C语言描述数据结构 —— 二叉树(1)

1.树

在学习二叉树之前，先浅浅的了解一下基本的树的概念以及基本结构。

树是一种非线性的数据结构。它是由n(n>=0)个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树。

那么树有这么几个特征：

  • 有一个特殊的结点，称为根结点，根结点没有前驱结点。

  • 除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……Tm，其中每一个集合又是一颗结构与树类似的子树。每颗子树的根结点有且只有一个前驱，可以0个或多个后继。

  • 树可以递归定义的。

我们需要注意的是，在树形结构当中，子树之间不能存在交集。

接下来就是树的一些重要的名词：

节点的度：一个节点含有的子树的个数称为该节点的度；例如上图A节点的度为6。

叶节点或终端节点：度为0的节点称为叶节点；如上图的B、C、H、P……等。

父节点或双亲节点：若一个节点含有子节点，那么这个节点称为其子节点的父节点；例如A是B、C、D……的父节点。

子节点或孩子节点：一个节点在子树当中的根节点称为该节点的子节点；例如B、C、D是A的子节点。

兄弟节点：具有相同的父节点的节点互相称为兄弟节点；B、C、D、E都可以互相称为兄弟节点。

树的度：某个节点最大的度。

节点的层次：从根开始定义，根为第一层，往下为第二层，以此类推。

树的高度或深度：树中节点的最大层次；上图最大层次为4，所以树的高度为4。

那么树的实际运用最典型的就是树状目录：

2.二叉树

2.1二叉树的概念

我们先观察一下二叉树的结构：

可以发现，二叉树不存在度大于2的节点；二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。对于任意的二叉树都是由以下几种情况复合而成的：

2.2特殊的二叉树

1.满二叉树：一个二叉树， 如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且节点总数是2^k-1，则它就是满二叉树。

2.完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的。用易于理解的话说就是，二叉树的最后一层可以只有一个节点或者多个节点，但节点都必须从左到右按顺序来。

那么二叉树具有什么性质呢？在我们没有真正实现这个数据结构的时候是非常不容易记住的，甚至有些难以理解。那么接下来就是要实现数据结构了，在打代码的过程当中，我们是可以体会到二叉树的一些性质的。

2.3二叉树的存储结构

二叉树可以使用两种存储结构，一种是顺序结构，一种是链式结构。这里我们只介绍顺序存储，因为本篇只会使用顺序结构来实现二叉树。

顺序存储：顺序结构就是使用数组来存储。但在现实中只有堆才会使用数组来存储，堆在下面将会做出解释。二叉树的顺序结构在物理上是一个数组，在逻辑上一颗二叉树。下面这幅图也表示，顺序结构的存储方式只能存储完全二叉树。

2.4堆的概念以及结构

如果有一组数据，把它的所有元素按完全二叉树的顺序结构存储方式存储在一个一维数组中，并满足所有的父节点的值大于或等于(小于或等于)所有子节点的值，那么就称为大堆(小堆)。也就是说，满足这个条件，那么根节点存储的数据一定是这颗二叉树中最大或最小的值。

由此我们可以推出堆的性质：

  • 堆中所有父节点的值总是大于等于(小于等于)其所有子节点的值；
  • 堆总是一颗完全二叉树

3.堆的实现

3.1堆的声明

堆是通过顺序结构存储的，所以我们使用顺序表来完成这个数据结构。

typedef int HeapData;
typedef struct Heap
{
    HeapData* a;
    int size;
    int  capacity;
}Heap;

3.2堆初始化

//初始化
void HeapInit(Heap* ph)
{
    assert(ph);
    ph->a = NULL;
    ph->size = ph->capacity = 0;
}

3.2堆插入

在这个步骤中，就要进行建堆了，我们回想一下顺序表的数据尾插，然后将物理结构转换为逻辑结构。在逻辑结构当中分析建堆的过程是非常简单的，当然这里涉及一个算法，具体如下图。

现在我们用代码描述插入和向上调整：

//交换
static void  Swap(HeapData* p1, HeapData* p2)
{
    assert(p1 && p2);
    HeapData tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
//向上调整
static void AdjustUp(Heap* ph, int child)
{
    assert(ph);
    //找到父节点下标
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        //假设建立小堆
        if (ph->a[child] < ph->a[parent])
        {
            Swap(&ph->a[child], &ph->a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
//插入
void HeapPush(Heap* ph,HeapData x)
{
    assert(ph);
    //是否需要扩容
    if (ph->size == ph->capacity)
    {
        int newcapacity = ph->capacity == 0 ? 4 : ph->capacity * 2;
        HeapData* tmp = (HeapData*)realloc(ph->a, newcapacity * sizeof(HeapData));
        assert(tmp);
        ph->capacity = newcapacity;
        ph->a = tmp;
    }
    ph->a[ph->size] = x;
    ph->size++;
    //向上调整
    AdjustUp(ph,  ph->size - 1);
}

3.3堆打印

//打印
void HeapPrint(Heap* ph)
{
    assert(ph);
    for (int i = 0; i < ph->size; i++)
    {
        printf("%d ", ph->a[i]);
    }
    printf("\n");
}

3.3堆删除

我们不能想当然的认为与顺序表一样删除很简单。我们一定要注意，在添加和删除元素的时候必须要保证我们的结构是个堆，这时候就涉及到专属与堆的删除方法，具体如图。

删除做好了，如何做到保证堆的数据结构合法呢？此时又涉及到一个算法，向下调整算法。

画图只能描述清楚我们的代码思路，那么现在附上实现这个算法的代码，再通过自己画图来深度理解这个算法：

//向下调整
void AdjustDown(Heap* ph, int n, int parent)
{
    assert(ph);
    int minchild = parent * 2 + 1;
    while (minchild < n)
    {
        if (minchild + 1 < n && ph->a[minchild + 1] < ph->a[minchild])
        {
            minchild++;
        }
        if (ph->a[minchild] < ph->a[parent])
        {
            Swap(&ph->a[minchild], &ph->a[parent]);
            parent = minchild;
            minchild = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//删除堆顶
void HeapPop(Heap* ph)
{
    assert(ph);
    Swap(&ph->a[0], &ph->a[ph->size - 1]);
    ph->size--;
    AdjustDown(ph, ph->size, 0);
}

3.4判空

//判空
bool HeapEmpty(Heap* ph)
{
    assert(ph);
    return ph->size == 0;
}

3.5返回堆顶元素

//返回堆顶元素
HeapData HeapTop(Heap* ph)
{
    assert(ph);
    assert(!HeapEmpty(ph));
    return ph->a[0];
}

3.6返回堆元素个数

//返回堆元素个数
int HeapSize(Heap* ph)
{
    assert(ph);
    return ph->size;
}

3.7堆销毁

//堆销毁
void HeapDestroy(Heap* ph)
{
    assert(ph);
    free(ph->a);
    ph->a = NULL;
    ph->size = ph->capacity = 0;
}

3.8完整代码

Heap.h

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
typedef int HeapData;
typedef struct Heap
{
    HeapData* a;
    int size;
    int  capacity;
}Heap;

void HeapInit(Heap* ph);//初始化
void HeapPush(Heap* ph,HeapData x);//插入
void HeapPrint(Heap* ph);//打印
void HeapPop(Heap* ph);//删除
bool HeapEmpty(Heap* ph);//判空
HeapData HeapTop(Heap* ph);//返回堆顶元素
int HeapSize(Heap* ph);//返回堆元素个数
void HeapDestroy(Heap* ph);//堆销毁

Heap.c

//初始化
void HeapInit(Heap* ph)
{
    assert(ph);
    ph->a = NULL;
    ph->size = ph->capacity = 0;
}
//交换
static void  Swap(HeapData* p1, HeapData* p2)
{
    assert(p1 && p2);
    HeapData tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
//向上调整
static void AdjustUp(Heap* ph, int child)
{
    assert(ph);
    //找到父节点下标
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        //假设建立小堆
        if (ph->a[child] < ph->a[parent])
        {
            Swap(&ph->a[child], &ph->a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
//插入
void HeapPush(Heap* ph,HeapData x)
{
    assert(ph);
    //是否需要扩容
    if (ph->size == ph->capacity)
    {
        int newcapacity = ph->capacity == 0 ? 4 : ph->capacity * 2;
        HeapData* tmp = (HeapData*)realloc(ph->a, newcapacity * sizeof(HeapData));
        assert(tmp);
        ph->capacity = newcapacity;
        ph->a = tmp;
    }
    ph->a[ph->size] = x;
    ph->size++;
    //向上调整
    AdjustUp(ph,  ph->size - 1);
}
//打印
void HeapPrint(Heap* ph)
{
    assert(ph);
    for (int i = 0; i < ph->size; i++)
    {
        printf("%d ", ph->a[i]);
    }
    printf("\n");
}
//向下调整
void AdjustDown(Heap* ph, int n, int parent)
{
    assert(ph);
    int minchild = parent * 2 + 1;
    while (minchild < n)
    {
        if (minchild + 1 < n && ph->a[minchild + 1] < ph->a[minchild])
        {
            minchild++;
        }
        if (ph->a[minchild] < ph->a[parent])
        {
            Swap(&ph->a[minchild], &ph->a[parent]);
            parent = minchild;
            minchild = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//删除堆顶
void HeapPop(Heap* ph)
{
    assert(ph);
    Swap(&ph->a[0], &ph->a[ph->size - 1]);
    ph->size--;
    AdjustDown(ph, ph->size, 0);
}
//判空
bool HeapEmpty(Heap* ph)
{
    assert(ph);
    return ph->size == 0;
}
//返回堆顶元素
HeapData HeapTop(Heap* ph)
{
    assert(ph);
    assert(!HeapEmpty(ph));
    return ph->a[0];
}
//返回堆元素个数
int HeapSize(Heap* ph)
{
    assert(ph);
    return ph->size;
}
//堆销毁
void HeapDestroy(Heap* ph)
{
    assert(ph);
    free(ph->a);
    ph->a = NULL;
    ph->size = ph->capacity = 0;
}

test.c

//个人测试，仅测试部分功能
void TestHeap()
{
    int a[] = { 12,45,62,56,2,67,89,1,46,21 };
    Heap p;
    HeapInit(&p);
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        HeapPush(&p, a[i]);
    }
    HeapPush(&p, 10);
    HeapPrint(&p);

    HeapPop(&p);
    HeapPrint(&p);


}
int main()
{
    TestHeap();

    return 0;
}

4.堆的实际运用

我们可以运用堆来完成一个排序算法，那么这个算法优势就在于它的实现复杂度达到了O(logN)。如果我们直接有一个数组，我们如何让它变成堆？

int main()
{
    int a[] = { 21,2,34,12,54,62,76,25,77 };
    return 0;
}

大家或许通过观察实现堆的代码得出这样一个思路：我同样建立一个堆变量，然后把数组的数据插入到堆变量里面，调整完成后再导回到数组里面。这个办法的效率确实是不错的，不过浪费了很多空间。

我们也可以直接通过向上调整算法直接操作数组，就少了一步导入的环节。我们用循环的方法来代替插入(HeapPush接口)。 

void HeapSort(int* a, int n)
{
    assert(a);
    //用循环的方式来模拟HeapPush
    for (int i = 0; i < n; i++)
    {
        AdjustUp(a, i);
    }

}
int main()
{
    int a[] = { 21,2,34,12,54,62,76,25,77 };
    HeapSort(a, sizeof(a) / sizeof(int));
    return 0;
}

第二种便是向下调整法，我们首先要找到最后一个叶节点的父节点，然后依次调整：

void HeapSort(int* a, int n)
{
    assert(a);
    //用循环的方法来模拟HeapPush
    //for (int i = 0; i < n; i++)
    //{
    //    AdjustUp(a, i);
    //}
    
    //向下调整建堆
    //n-2 的目的是万一没有右孩子
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

}
int main()
{
    int a[] = { 21,2,34,12,54,62,76,25,77 };
    HeapSort(a, sizeof(a) / sizeof(int));
    return 0;
}

堆建好了之后，现在就要实现排序了。我们直到，堆顶的元素是最大或最小的，那如果我们要排升序的话是建小堆还是大堆？有人会想的是建小堆，思路是这样的：拿出堆顶的元素，然后删除，然后再拿出堆顶的元素，如此往复就得到了升序的序列。但是这样有一个非常的大的问题，每拿出一个元素，就又得重新建一次堆，这样的话就没有堆排序的实质意义了。所以，我们给的思路是，升序建大堆，降序建小堆。为什么？我们看图：

我们用代码实现我们的思路：

#include <assert.h>
#include <stdio.h>
void Swap(int* p1, int* p2)
{
    assert(p1 && p2);
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void AdjustDown(int* a, int n, int parent)
{
    assert(a);
    int minchild = parent * 2 + 1;
    while (minchild < n)
    {
        if (minchild + 1 < n && a[minchild] > a[minchild + 1])
        {
            minchild++;
        }
        if (a[minchild] < a[parent])
        {
            Swap(&a[minchild], &a[parent]);
            parent = minchild;
            minchild = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int* a, int n)
{
    assert(a);
    
    //向下调整建堆
    //n-2 的目的是万一没有右孩子
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
    //排序
    while (n)
    {
        Swap(&a[0], &a[n - 1]);
        AdjustDown(a, n - 1, 0);
        n--;
    }
}
int main()
{
    int a[] = { 21,2,34,12,54,62,76,25,77 };
    HeapSort(a, sizeof(a) / sizeof(int));
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

可以看到，用到向下调整的算法的地方是非常多的，这也是一个淘汰向上调整的理由，还有一个理由便是向上调整的效率没有向下调整的效率高。在我们设计代码时，尽量使接口能被复用，这样可以降低代码的冗余程度。

标签： 数据结构
本文转载自: https://blog.csdn.net/weixin_59913110/article/details/126444279
版权归原作者 龙兆万 所有， 如有侵权，请联系我们删除。
登录后发布评论

“C语言描述数据结构 &mdash;&mdash; 二叉树(1)”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航