【初阶数据结构与算法】第七篇：二叉树和堆的基本概念+以及堆的实现

⭐️本篇博客我要给大家分享一下算法中的二叉树。希望对大家有所帮助。
⭐️ 博主码云gitee链接：码云主页

💙系列文章💙

【初阶数据结构与算法】第一篇：算法中的时间复杂度和空间复杂度

【初阶数据结构与算法】第二篇：顺序表

【初阶数据结构与算法】第三篇：单链表

【初阶数据结构与算法】第四篇：链表面试题详解

【初阶数据结构与算法】第五篇：双链表

【初阶数据结构与算法】第六篇：栈和队列（各个功能实现+练习题包含多种方法）

前言

​

🌏一、树的相关概念和结构

🍯1.树的概念

🍤树（tree）是包含 n(n≥0) [2] 个节点，当 n=0 时，称为空树，非空树中条边的有穷集，在非空树中：
🍤每个元素称为节点（node）。
🍤有一个特定的节点被称为根节点或树根（root）。
🍤除根节点之外的其余数据元素被分为个互不相交的集合，其中每一个集合本身也是一棵树，被称作原树的子树。

🍤树形结构中，子树之间不能有交集，否则就不是树形结构

因此，树是递归定义的

🍯2.数的相关概念

🍤节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为2
🍤叶节点或终端节点：度为0的节点称为叶节点； 如上图：D、F、G、H为叶节点
🍤非终端节点或分支节点：度不为0的节点； 如上图：A、B…等节点为分支节点
🍤双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
🍤孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
🍤兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
🍤树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为2
🍤节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
🍤树的高度或深度：树中节点的最大层次； 如上图：树的高度为4(根节点的高度记为1)
🍤堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
🍤节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
🍤子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
🍤森林：由m（m>0）棵互不相交的树的集合称为森林

🍯3.树的表示

🍤左孩子右兄弟表示法是节点中保存第一个孩子的节点的指针，还有一个指针指向下一个兄弟节点。

typedef int DataType;
struct Node
{
    struct Node* firstChild; // 第一个孩子结点
    struct Node* pNextBrother; // 指向其下一个兄弟结点
    DataType data; // 结点中的数据域
}

🌏二、二叉树的概念及结构

🍯1.概念

🍤二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

1. 二叉树的度不超过2
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

🍯2.特殊二叉树

🍍满二叉树

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

🍍完全二叉树

🍤一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

通俗来讲，就是最后一层从左往右是连续的，倒数第二层是满二叉树

** 🍤只有一个节点也可以完全二叉树或者满二叉树，空树也可以是完全二叉树或者满二叉树**

🍯3.二叉树的性质

🍤若规定根节点的层数为1，则一棵非空二叉树的第n层上最多有2^(n-1)个结点

🍤若规定根节点的层数为1，则深度为n的二叉树的最大结点数是2^n-1

🍤对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有n0 = n2+1。

🍤树中父节点与子节点的关系：

• leftChild = parent*2+1
• rightChild = parent*2+1
• parent = (child-1)/2

🍯4.二叉树的存储结构

🍍顺序结构

🍤顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树

🍍链式结构

🍤 二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

🌏三、二叉树顺序结构及实现

🍯1.二叉树的顺序结构

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

🍯2.堆的概念

🍤 堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

小堆：

    parent小于child

大堆：

    parent大于child

🍯3.堆的实现

🍍堆的时间复杂度和创建

🍤依据堆的性质是数组，所以堆的创建时间复杂度是O(N)

下面是堆的创建和相关函数

//定义一个堆，是顺序表类型的
typedef int HPDataType;
typedef struct Heap
{
    HPDataType* a;
    size_t size;
    size_t capacity;
}HP;
//交换两个数字
void Swap(HPDataType* pa, HPDataType* pb);
//初始化
void HeapInit(HP* php);
//销毁
void HeapDestroy(HP* php);
//打印
void HeapPrint(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//计算长度
size_t HeapSize(HP* php);
//获取顶部数字
HPDataType HeapTop(HP* php);

🍍堆的向下调整

🍤向下调整就是将最上面的root依次向下比较，如果是大堆，则将左孩子和右孩子中较大的值与parent比较，当parent小于child时，交换，如果是小堆，则将左孩子和右孩子中较小的值与parent比较，当parent大于child时，交换。

//向下调整
void AjustDown(HPDataType* a, size_t size, size_t root) {
    size_t parent = root;
    size_t child = parent * 2 + 1;
    while (child < size) {
        //将较大的child与parent交换,交换前判断右孩子是不是存在
        if (a[child + 1] < a[child] && child + 1 < size) {
            child++;
        }
        //如果孩子比父亲大，则将孩子与父亲交换
        if (a[parent] > a[child]) {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}

🍍堆的向上调整

🍤同理向上调整就是将child从最下面向上比较，如果是大堆，那么当child大于parent时，child向上交换，如果是小堆，那么当child小于parent时，child向上交换。

//向上调整
void AjustUp(HPDataType* a, size_t child) {
    size_t parent = (child - 1) / 2;
    while (child > 0) {
        //向上调整（大堆）
        //if (a[parent] < a[child])
        if (a[parent] > a[child]) {
            Swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }else{
            break;
        }
    }
}

🍍堆的插入

🍤插入之前要判断是否满了，如果一开始capacity就没有元素，则给他四个元素，之后如果满了就把原来空间扩大两倍，reallo时注意不要直接在原来指针上开辟，如果开辟失败则原来指针丢失，之后将开辟好的空间指针和空间大小全部都交给capacity和a之后，向上调整，维持原来堆的性质。

//插入,注意扩容
void HeapPush(HP* php, HPDataType x) {
    assert(php);
    //满了扩容
    if (php->size == php->capacity) {
        size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newcapacity);
        if (tmp == NULL) {
            printf("malloc fail: %s", strerror(errno));
            exit(-1);
        }
        php->capacity = newcapacity;
        php->a = tmp;
    }
    php->a[php->size] = x;
    php->size++;
    //向上调整传送过去孩子和a
    AjustUp(php->a, php->size - 1);
}

🍍堆的删除

🍤我们定义堆的删除是删除root，所以首先将堆的第一个元素和最后一个元素交换，之后删除最后一个元素，这样堆的结构就没有完全破坏，因为堆顶的左子树和右子树都是大堆，我们可以进行向下调整就可以恢复堆的形状了，向下调整算法的时间复杂度是堆的高度次，即**O(log(h+1))，及O(logN)**。

//删除，注意是否为空，将头和尾交换数据，此时子树依旧保持不变，只需要向下调整即可
void HeapPop(HP* php) {
    assert(php);
    //数量要大于0
    assert(php->size > 0);
    //将头和尾交换
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    //将堆的地址， 堆的长度，root传过去
    AjustDown(php->a, php->size, 0);
}

🍍堆的初始化

🍤堆的初始化和顺序表和队列差不多，将接收动态开辟的数组地址置NULL，同时size和capicity都置为0

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

🍍堆的销毁

🍤记得将原来数组地址free

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

🍍堆的打印

🍤依次打印即可

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

🍍堆判断是否为空

🍤就是判断size是不是0

//判断是否为空
bool HeapEmpty(HP* php){
    assert(php);
    return php->size == 0;
}

🍍堆的长度

🍤直接返回size

//计算长度
size_t HeapSize(HP* php) {
    assert(php);
    return php->size;
}

🍍堆的获取顶部数字

🍤获取顶部数字要注意，原来空间中是不是还有元素

//获取顶部数字
HPDataType HeapTop(HP* php) {
    assert(php);
    //判断是否存在数字
    assert(php->size > 0);
    return php->a[0];
}

总结

🍤简单介绍了一下堆和二叉树，下面就是介绍堆排序和TOP-K