1. Toy模板网首页
  2. > Toy博客

【数据结构】二叉树的顺序结构-堆

10月前 作者：ikun66666 分类：Toy博客 阅读(52) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉树的顺序结构-堆。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【数据结构】二叉树的顺序结构-堆

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

【数据结构】二叉树的顺序结构-堆,数据结构,数据结构,算法,c++,c语言

1.堆的概念及结构

小堆：将根结点最小的堆叫做小堆，也叫最小堆或小根堆。

大堆：将根结点最大的堆叫做大堆，也叫最大堆或大根堆。

堆的性质：

  • 堆中某个结点的值总是不大于或不小于其父结点的值。
  • 堆总是一棵完全二叉树。

【数据结构】二叉树的顺序结构-堆,数据结构,数据结构,算法,c++,c语言

2.堆的实现

堆的向下调整算法

现在我们给出一个数组，逻辑上看作一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。

【数据结构】二叉树的顺序结构-堆,数据结构,数据结构,算法,c++,c语言

但是，使用向下调整算法需要满足一个前提：

  • 若想将其调整为小堆，那么根结点的左右子树必须都为小堆。
  • 若想将其调整为大堆，那么根结点的左右子树必须都为大堆。

【数据结构】二叉树的顺序结构-堆,数据结构,数据结构,算法,c++,c语言

向下调整算法的基本思想（以建小堆为例）：

  1. 从根结点处开始，选出左右孩子中值较小的孩子。
  2. 让小的孩子与其父亲进行比较。
    • 若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
    • 若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆了。

代码如下：

//交换函数
void Swap(int* x, int* y){
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//堆的向下调整（小堆）
void AdjustDown(int *a, int n, int parent) {
    //child记录左右孩子中值较小的孩子的下标
    int child = 2 * parent + 1;//先默认其左孩子的值较小
    while (child < n) {
        if (child + 1 < n && a[child + 1] < a[child]){//右孩子存在并且右孩子比左孩子还小
            child++;//较小的孩子改为右孩子
        }
        if (a[child] < a[parent]){//左右孩子中较小孩子的值比父结点还小
            //将父结点与较小的子结点交换
            Swap(&a[child], &a[parent]);
            //继续向下进行调整
            parent = child;
            child = 2 * parent + 1;
        } else{//已成堆
            break;
        }
    }
}

使用堆的向下调整算法，最坏的情况下（即一直需要交换结点），需要循环的次数为：h - 1次（h为树的高度）。而h = log2(N+1)（N为树的总结点数）。所以堆的向下调整算法的时间复杂度为：O(logN) 。

上面说到，使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意树调整为堆？
答案很简单，我们只需要从倒数第一个非叶子结点开始，从后往前，按下标，依次作为根去向下调整即可。

【数据结构】二叉树的顺序结构-堆,数据结构,数据结构,算法,c++,c语言

代码：

for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
    AdjustDown(php->a, n, i);
}

那么建堆的时间复杂度又是多少呢？
当结点数无穷大时，完全二叉树与其层数相同的满二叉树相比较来说，它们相差的结点数可以忽略不计，所以计算时间复杂度的时候我们可以将完全二叉树看作与其层数相同的满二叉树来进行计算。

【数据结构】二叉树的顺序结构-堆,数据结构,数据结构,算法,c++,c语言
总结一下：

  • 堆的向下调整算法的时间复杂度：T(n) = O (log ⁡ N)
  • 建堆的时间复杂度：T(n) = O(N)

堆的向上调整算法

当我们在一个堆的末尾插入一个数据后，需要对堆进行调整，使其仍然是一个堆，这时需要用到堆的向上调整算法。

【数据结构】二叉树的顺序结构-堆,数据结构,数据结构,算法,c++,c语言

向上调整算法的基本思想（以建小堆为例）：

  1. 将目标结点与其父结点比较。
  2. 若目标结点的值比其父结点的值小，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大，则停止向上调整，此时该树已经是小堆了。

【数据结构】二叉树的顺序结构-堆,数据结构,数据结构,算法,c++,c语言

代码如下：

//交换函数
void Swap(HPDataType *x, HPDataType *y) {
    HPDataType tmp = *x;
    *x = *y;
    *y = tmp;
}

//堆的向上调整（小堆）
void AdjustUp(HPDataType *a, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {            //调整到根结点的位置截止
        if (a[child] < a[parent]) {//孩子结点的值小于父结点的值
            //将父结点与孩子结点交换
            Swap(&a[child], &a[parent]);
            //继续向上进行调整
            child = parent;
            parent = (child - 1) / 2;
        } else {//已成堆
            break;
        }
    }
}

初始化堆

首先，必须创建一个堆类型，该类型中需包含堆的基本信息：存储数据的数组、堆中元素的个数以及当前堆的最大容量。

typedef int HPDataType;
// 堆的结构 - 顺序表
typedef struct Heap {
    HPDataType *a;
    int size;
    int capacity;
} Heap;

建堆

然后我们需要一个建堆函数，对刚创建的堆进行初始化，注意在初始化期间要将传入数据建堆。

// 堆的创建 - 建堆算法
void HeapCreate(Heap *php, HPDataType *a, int n) {
    assert(php);
    php->a = (HPDataType *) realloc(php->a, sizeof(HPDataType) * n);
    if (php->a == NULL) {
        perror("realloc fail");
        exit(-1);
    }
    // 内存复制  数组复制到php->a中
    memcpy(php->a, a, sizeof(HPDataType) * n);
    php->size = php->capacity = n;
    // 建堆算法 - 从最后一个叶子节点的父亲节点开始向下调整，然后从父亲节点的前所有节点都向下调整一次
    // 最后节点的父亲的坐标是(n-1-1)/2  n-1因为n是节点个数，坐标从0开始
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(php->a, n, i);
    }
}

销毁堆

为了避免内存泄漏，使用完动态开辟的内存空间后都要及时释放该空间，所以，一个用于释放内存空间的函数是必不可少的。

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

打印堆

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

堆的插入

数据插入时是插入到数组的末尾，即树形结构的最后一层的最后一个结点，所以插入数据后我们需要运用堆的向上调整算法对堆进行调整，使其在插入数据后仍然保持堆的结构。

// 堆的插入
void HeapPush(Heap *php, HPDataType x) {
    assert(php);
    // 内存满了，扩容
    if (php->size == php->capacity) {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType *tmp = (HPDataType *) realloc(php->a, sizeof(HPDataType) * newcapacity);
        if (tmp == NULL) {
            perror("realloc fail");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newcapacity;
    }
    // 插入
    php->a[php->size] = x;
    php->size++;
    // 插入完，开始向上调整建堆
    // 将数组和child的位置传过去
    AdjustUp(php->a, php->size - 1);
}

堆的删除

堆的删除，删除的是堆顶的元素，但是这个删除过程可并不是直接删除堆顶的数据，而是先将堆顶的数据与最后一个结点的位置交换，然后再删除最后一个结点，再对堆进行一次向下调整。

原因：我们若是直接删除堆顶的数据，那么原堆后面数据的父子关系就全部打乱了，需要全体重新建堆，时间复杂度为O(N) 。若是用上述方法，那么只需要对堆进行一次向下调整即可，因为此时根结点的左右子树都是小堆，我们只需要在根结点处进行一次向下调整即可，时间复杂度为O(log ⁡N)

// 堆的删除
void HeapPop(Heap *php) {
    assert(php);
    assert(php->size > 0);

    // 堆的删除，因为不能破坏堆的结构，所以将堆顶，和堆底最后一个数据交换，然后删除堆底，堆顶再向下调整，保持堆的结构
    // 1.交换堆顶和堆底
    Swap(&php->a[0], &php->a[php->size - 1]);
    // 2.删除堆底
    php->size--;
    // 3.向下调整
    AdjustDown(php->a, php->size, 0);
}

获取堆顶的数据

获取堆顶的数据，即返回数组下标为0的数据。

// 取堆顶
HPDataType HeapTop(Heap *php) {
    assert(php);
    assert(php->size > 0);

    return php->a[0];
}

获取堆的长度

获取堆的长度，即返回堆结构体中的size变量。

// 求堆的长度
size_t HeapSize(Heap *php) {
    assert(php);

    return php->size;
}

堆的判空

堆的判空，即判断堆结构体中的size变量是否为0。

// 堆的判空
bool HeapEmpty(Heap *php) {
    assert(php);

    return php->size == 0;
}

完整代码

#pragma once
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int HPDataType;
// 堆的结构 - 顺序表
typedef struct Heap {
    HPDataType *a;
    int size;
    int capacity;
} Heap;


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

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

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

// 向上调整 - 大堆
void AdjustUp(HPDataType *a, int child) {
    // 1.找父亲
    int parent = (child - 1) / 2;
    // 2.跟父亲比大小，如果是大堆，知道父亲大于孩子循环结束，如果一直小于孩子，一直交换，然后循环结束条件是child==0
    while (child > 0) {
        // 孩子大于父亲则交换
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

// 向下调整 - 大堆
void AdjustDown(HPDataType *a, int n, int parent) {
    // 如果是大堆，先找父亲的孩子中的大的，然后跟他交换
    // 先假设左孩子是大的，如果不是，重新设置为右孩子是大的
    int child = parent * 2 + 1;
    // child的值不会越界，所以循环条件是child < n
    while (child < n) {
        // 重新设置最大的孩子，如果右孩子大，就++child。特殊情况：最后的节点，只有左孩子，没有右孩子，所以还要加条判断，左孩子+1<n说明还有一个右孩子
        if (child + 1 < n && a[child] < a[child + 1]) {
            child++;
        }
        // 1.父亲小于孩子，交换，继续向下调整
        // 2.父亲大于孩子，跳出
        if (a[parent] < a[child]) {
            Swap(&a[parent], &a[child]);
            // 交换后，重新设置parent，找下一个位置开始向下调整
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

// 堆的插入
void HeapPush(Heap *php, HPDataType x) {
    assert(php);
    // 内存满了，扩容
    if (php->size == php->capacity) {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType *tmp = (HPDataType *) realloc(php->a, sizeof(HPDataType) * newcapacity);
        if (tmp == NULL) {
            perror("realloc fail");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newcapacity;
    }
    // 插入
    php->a[php->size] = x;
    php->size++;
    // 插入完，开始向上调整建堆
    // 将数组和child的位置传过去
    AdjustUp(php->a, php->size - 1);
}

// 堆的删除
void HeapPop(Heap *php) {
    assert(php);
    assert(php->size > 0);

    // 堆的删除，因为不能破坏堆的结构，所以将堆顶，和堆底最后一个数据交换，然后删除堆底，堆顶再向下调整，保持堆的结构
    // 1.交换堆顶和堆底
    Swap(&php->a[0], &php->a[php->size - 1]);
    // 2.删除堆底
    php->size--;
    // 3.向下调整
    AdjustDown(php->a, php->size, 0);
}

// 取堆顶
HPDataType HeapTop(Heap *php) {
    assert(php);
    assert(php->size > 0);

    return php->a[0];
}

// 求堆的长度
size_t HeapSize(Heap *php) {
    assert(php);

    return php->size;
}

// 堆的判空
bool HeapEmpty(Heap *php) {
    assert(php);

    return php->size == 0;
}

// 交换
void Swap(HPDataType *p1, HPDataType *p2) {
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// 堆的创建 - 建堆算法
void HeapCreate(Heap *php, HPDataType *a, int n) {
    assert(php);
    php->a = (HPDataType *) realloc(php->a, sizeof(HPDataType) * n);
    if (php->a == NULL) {
        perror("realloc fail");
        exit(-1);
    }
    // 内存复制  数组复制到php->a中
    memcpy(php->a, a, sizeof(HPDataType) * n);
    php->size = php->capacity = n;
    // 建堆算法 - 从最后一个叶子节点的父亲节点开始向下调整，然后从父亲节点的前所有节点都向下调整一次
    // 最后节点的父亲的坐标是(n-1-1)/2  n-1因为n是节点个数，坐标从0开始
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(php->a, n, i);
    }
}

3.堆的应用

堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

  1. 建堆
    • 升序：建大堆
    • 降序：建小堆
  2. 利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

【数据结构】二叉树的顺序结构-堆,数据结构,数据结构,算法,c++,c语言

代码如下：

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

// 向下调整 - 大堆
void AdjustDown(int *a, int n, int parent) {
    // 如果是大堆，先找父亲的孩子中的大的，然后跟他交换
    // 先假设左孩子是大的，如果不是，重新设置为右孩子是大的
    int child = parent * 2 + 1;
    // child的值不会越界，所以循环条件是child < n
    while (child < n) {
        // 重新设置最大的孩子，如果右孩子大，就++child。特殊情况：最后的节点，只有左孩子，没有右孩子，所以还要加条判断，左孩子+1<n说明还有一个右孩子
        if (child + 1 < n && a[child] < a[child + 1]) {
            child++;
        }
        // 1.父亲小于孩子，交换，继续向下调整
        // 2.父亲大于孩子，跳出
        if (a[parent] < a[child]) {
            Swap(&a[parent], &a[child]);
            // 交换后，重新设置parent，找下一个位置开始向下调整
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

// 对数组进行堆排序
void HeapSort(int *a, int n) {
    // 向上调整建堆 -- N*logN
    /*for (int i = 1; i < n; ++i)
    {
    AdjustUp(a, i);
    }*/

    // 向下调整建堆 - 大堆 O(N)    _
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }

    int end = n - 1;
    while (end > 0) {
        // 第一个和最后一个交换，除了最后一个，剩下的进行建堆调整，把最大的调整到堆顶
        Swap(&a[0], &a[end]);
        // end为坐标，坐标比个数多一个，所以下面的end是剩余的个数
        AdjustDown(a, end, 0);
        end--;
    }
}

int main() {
    int arr[10] = {32, 43, 56, 76, 84, 12, 45, 67, 43, 37};
    HeapSort(arr, sizeof(arr) / sizeof(int));
    for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
        printf("%d ", arr[i]);
    }
}

TOPK问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

  1. 用数据集合中前K个元素来建堆
    • 前k个最大的元素，则建小堆
    • 前k个最小的元素，则建大堆
  2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

//交换函数
void Swap(int *x, int *y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
//堆的向下调整（小堆）
void AdjustDown(int *a, int n, int parent) {
    //child记录左右孩子中值较小的孩子的下标
    int child = 2 * parent + 1;//先默认其左孩子的值较小
    while (child < n) {
        if (child + 1 < n && a[child + 1] < a[child]) {//右孩子存在并且右孩子比左孩子还小
            child++;                                   //较小的孩子改为右孩子
        }
        if (a[child] < a[parent]) {//左右孩子中较小孩子的值比父结点还小
            //将父结点与较小的子结点交换
            Swap(&a[child], &a[parent]);
            //继续向下进行调整
            parent = child;
            child = 2 * parent + 1;
        } else {//已成堆
            break;
        }
    }
}

int *getLeastNumbers(int *arr, int arrSize, int k, int *returnSize) {
    *returnSize = k;
    if (k == 0)
        return NULL;
    //用数组的前K个数建小堆
    int i = 0;
    int *retArr = (int *) malloc(sizeof(int) * k);
    for (i = 0; i < k; i++) {
        retArr[i] = arr[i];
    }
    for (i = (k - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(retArr, k, i);
    }
    //剩下的N-k个数依次与堆顶数据比较
    for (i = k; i < arrSize; i++) {
        if (arr[i] > retArr[0]) {
            retArr[0] = arr[i];//堆顶数据替换
        }
        AdjustDown(retArr, k, 0);//进行一次向下调整
    }
    return retArr;//返回最大的k个数
}

时间复杂度：O(k + N * log k)空间复杂度：O(k)文章来源地址https://www.toymoban.com/news/detail-701439.html

到了这里，关于【数据结构】二叉树的顺序结构-堆的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构初阶--二叉树的顺序结构之堆

    数据结构初阶--二叉树的顺序结构之堆

    目录 一.堆的概念及结构 1.1.堆的概念 1.2.堆的存储结构 二.堆的功能实现 2.1.堆的定义 2.2.堆的初始化 2.3.堆的销毁 2.4.堆的打印 2.5.堆的插入 向上调整算法 堆的插入 2.6.堆的删除 向下调整算法 堆的删除 2.7.堆的取堆顶元素 2.8.堆的判空 2.9.堆的求堆的大小 三.堆的创建 3.1.向上调

    2024年02月14日
    浏览(45)
  • 初阶数据结构之---二叉树的顺序结构-堆

    初阶数据结构之---二叉树的顺序结构-堆

    今天要讲的堆，不是操作系统虚拟进程地址空间中（malloc，realloc等开空间的位置）的那个堆，而是数据结构中的堆，它们虽然名字相同，却是截然不同的两个概念。堆的底层其实是 完全二叉树 ，如果你问我，完全二叉树是什么。好吧，那我先从树开始讲起，开始我们今天的

    2024年03月14日
    浏览(58)
  • 二叉树的顺序结构以及堆的实现——【数据结构】

    二叉树的顺序结构以及堆的实现——【数据结构】

    W...Y的主页 😊 代码仓库分享  💕 上篇文章，我们认识了什么是树以及二叉树的基本内容、表示方法……接下来我们继续来深入二叉树，感受其中的魅力。 目录  二叉树的顺序结构 堆的概念及结构 堆的实现   堆的创建  堆的初始化与释放空间  堆的插入 堆的删除  堆实

    2024年02月07日
    浏览(47)
  • 数据结构——二叉树的基本概念及顺序存储（堆）

    数据结构——二叉树的基本概念及顺序存储（堆）

    目录 一.前言 二.树概念及结构 2.1 树的概念 2.2 树的相关概念 2.3 树的表现 2.4 树在实际中的应用（表示文件系统的目录树结构） 三.二叉树的概念及结构 3.1 概念 3.2 特殊的二叉树 3.3 二叉树的性质 3.4 二叉树的存储结构 3.4.1 顺序存储 3.4.2 链式存储 四.二叉树顺序结构及实现

    2024年02月08日
    浏览(45)
  • 【数据结构】二叉树的顺序结构实现及时间复杂度计算（二）

    【数据结构】二叉树的顺序结构实现及时间复杂度计算（二）

    目录 一，二叉树的顺序结构实现         1，二叉树的顺序结构         2，堆的概念及结构         3，堆的接口实现 1，堆的创建 2，接口函数 3，初始化 4，销毁 5，是否增容 6，交换数据 7，堆向上调整算法 8，插入数据 9，删除数据 10，堆向下调整算法 11，打印数

    2024年02月09日
    浏览(37)
  • 【数据结构—二叉树的基础知识介绍和堆的实现（顺序表）】

    【数据结构—二叉树的基础知识介绍和堆的实现（顺序表）】

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 文章目录 前言 1.树概念及结构 1.1树的概念 1.2 树的相关概念  1.3 树的表示 1.4 树在实际中的运用（表示文件系统的目录树结构） 2.二叉树概念及结构 2.1概念 2.2 特殊的二叉树： 2.3 二叉树的存储结构

    2024年02月03日
    浏览(43)
  • 数据结构入门（C语言版）二叉树的顺序结构及堆的概念及结构实现应用

    数据结构入门（C语言版）二叉树的顺序结构及堆的概念及结构实现应用

    普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用 顺序结构的数组来存储 ，需要注意的是 这里的堆和操作系统虚拟进程地址空间中的堆是两回事 ，一个是 数据结构 ，一

    2023年04月19日
    浏览(53)
  • 数据结构（C语言实现）——二叉树的概念及二叉树顺序结构和链式结构的实现（堆排序+TOP-K问题+链式二叉树相关操作）

    数据结构（C语言实现）——二叉树的概念及二叉树顺序结构和链式结构的实现（堆排序+TOP-K问题+链式二叉树相关操作）

    前面学习了数据结构中线性结构的几种结构，顺序表，链表，栈和队列等，今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点，所以本文着重介绍二叉树的相关概念和性质，以及二叉树的应用。 树是一种非线性的数据结构，它是由n（

    2023年04月21日
    浏览(45)
  • 数据结构与算法-二叉树的遍历

    数据结构与算法-二叉树的遍历

    🌞 “少年没有乌托邦，心向远方自明朗！” 二叉树的遍历是按照一定次序访问二叉树中的所有结点，且每个结点仅被访问一次的过程。遍历线性结构是容易解决的，而二叉树的结构是非线性结构，需要寻找规律，使二叉树的结点排列在一个线性队列上，便于遍历。 由二叉树

    2024年02月08日
    浏览(46)
  • 【数据结构】二叉树的遍历递归算法详解

    【数据结构】二叉树的遍历递归算法详解

    我们来写一个函数 BuyNode(x)函数 用于创建二叉树结点。 用动态开辟函数 malloc 函数进行动态开辟，并强制转换为 BTNode 型，用变量 node 来去管理开辟的空间。 我们初始化结点，其 val 即为传入的参数x，左右指针 left 和 right 都设为NULL。 我们在主函数中创建上面这样一颗二叉树

    2024年01月20日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包