【数据结构入门】二叉树之堆排序及链式二叉树

目录

前言

一、堆排序

1.概念

2.堆排序思想

3.具体步骤

4.实现

5.复杂度

二、堆的应用——TopK问题

三、链式二叉树

1.二叉树创建

 2.二叉树遍历

1)前序、中序以及后序遍历

2)层序遍历

3.结点个数以及高度

1)结点个数:

 2)结点高度

  3)二叉树第K层结点的个数

 4)查找值为x的结点

4. 判断二叉树是否为完全二叉树

5.二叉树的销毁

总结


前言

堆排序是一种使用堆数据结构的排序算法。堆是一种完全二叉树,且满足堆属性,即每个节点的值都大于(或小于)它的子节点的值。

二叉树的遍历有三种方式:前序遍历、中序遍历、后序遍历。这三种遍历方式都是深度优先遍历。

一、堆排序

1.概念

堆排序是一种基于堆数据结构实现的排序算法。它将待排序的序列构建成一个大顶堆(或小顶堆),然后依次取出堆顶元素,将其与最后一个元素交换位置,并不断调整堆使其重新满足堆的性质,最终得到一个有序的序列。

2.堆排序思想

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

1. 建堆
        升序:建大堆
        降序:建小堆

注意:升序排列时,并不是建小堆,而是建大堆,堆排列都是从后往前排的,如果建小堆还需要多次交换数组。

建堆时可以使用向上调整也可以使用向下调整,但是向上调整的时间复杂度更高为Nlog(N),而向下调整建堆的时间复杂度更低,为N,所以采用向下调整建堆。


2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。

3.具体步骤

  1. 构建初始堆:将待排序序列构建成一个大顶堆。从最后一个非叶子节点开始,依次对每个节点进行调整,使其满足大顶堆的性质(父节点的值大于子节点的值)。
  2. 交换堆顶元素和最后一个元素:将堆顶元素与最后一个元素交换位置,并缩小堆的范围(即去掉最后一个元素)。
  3. 调整堆:对交换后的堆进行调整,使其重新满足大顶堆的性质。
  4. 重复步骤2和3,直到堆的范围缩小至1,即所有元素都已经排序完成。

4.实现

//左右子树都是大堆或者小堆
void ADjustDown(HPDataType* a, int sz, int parent)
{int child = parent * 2 + 1;while (child < sz){//选出左右孩子中大的一个//这里child+1的判断在前,不要先访问再判断//这里a[child + 1] > a[child] 建大堆用>, 建小堆用<if (child + 1 < sz && a[child + 1] < a[child]){//这地方可能会越界++child;}//这里a[child] > a[parent] 建大堆用>, 建小堆用<if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int sz)
{//1.建堆 -- 向上调整建堆   NlogN//左右子树必须是大堆/小堆/*for (int i = 1; i < sz; i++){ADjustUp(a, i);}*///2.向下调整建堆  N//左右子树必须是大堆/小堆for (int i = (sz - 1 -1) / 2; i >= 0; i--){ADjustDown(a, sz, i);}int end = sz - 1;while (end > 0){Swap(&a[end], &a[0]);ADjustDown(a, end, 0);--end;}
}

 测试代码:

int main()
{int a[10] = { 2, 1, 5, 4, 7, 9, 8, 3, 6, 0};//对数组排序int sz = sizeof(a) / sizeof(a[0]);HeapSort(a, sz);for (int i = 0; i < sz; i++){printf("%d ", a[i]);}return 0;
}

 测试结果:

5.复杂度

堆排序的时间复杂度为O(nlogn),其中n为待排序序列的长度。堆排序是一种原地排序算法,不需要额外的存储空间,但由于堆的构建过程需要占用一定的空间,所以它并不是稳定的排序算法

二、堆的应用——TopK问题

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

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

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

  1. 用数据集合中前K个元素来建堆

    • 前k个最大的元素,则建小堆

    • 前k个最小的元素,则建大堆

  2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

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

typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void ADjustDown(HPDataType* a, int sz, int parent)
{int child = parent * 2 + 1;while (child < sz){//选出左右孩子中大的一个//这里child+1的判断在前,不要先访问再判断//这里a[child + 1] > a[child] 建大堆用>, 建小堆用<if (child + 1 < sz && a[child + 1] > a[child]){//这地方可能会越界++child;}//这里a[child] > a[parent] 建大堆用>, 建小堆用<if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void PrintTopk(const char* file, int k)
{//1.建堆 -- 用a中的前k个元素建小堆int* topk = (int*)malloc(sizeof(int) * k);assert(topk);FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}//读出前k个数据建小堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &topk[i]);}for (int i = (k - 1 - 1) / 2; i >= 0; i--){ADjustDown(topk, k, i);}//2.将剩余n-k个元素依次与堆顶元素交换,不满则替换int val = 0;int ret = fscanf(fout, "%d", &val);while (ret != EOF){if (val > topk[0]){topk[0] = val;ADjustDown(topk, k, 0);}ret = fscanf(fout, "%d", &val);}for (int i = 0; i < k; i++){printf("%d ", topk[i]);}printf("\n");free(topk);topk = NULL;
}void CreatNData()
{//造数据int n = 10000;srand((unsigned int)time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 10000;fprintf(fin, "%d\n", x);}fclose(fin);
}int main()
{// 在测试时可以先运行第一个函数,创造好数据,// 然后修改k条数据,再运行第二步,在监视窗口观察CreatNData();PrintTopk("data.txt", 10);return 0;
}

三、链式二叉树

只有完全二叉树的实现使用数组比较方便,因为很少造成空间浪费。其他二叉树使用链式结构更节省空间,但是由于链式二叉树的构造比较麻烦,所以这里只介绍链式二叉树的遍历。

1.二叉树创建

在操作二叉树前,需要创建一颗二叉树,这里为了简单直接手动创建一颗二叉树

typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);//BTNode* node7 = BuyNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;//node2->right = node7;return node1;
}

 2.二叉树遍历

学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的结点进行相应的操作,并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。

1)前序、中序以及后序遍历

按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历

  1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

  2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。

  3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

前序遍历图示:

 前序遍历实现:

void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

 前序遍历递归图示:

 后序遍历实现:

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

 后序遍历:

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

前序遍历结果:1 2 3 4 5 6

中序遍历结果:3 2 1 5 4 6

后序遍历结果:3 2 5 6 4 1

2)层序遍历

设二叉树的根结点所在层数为1,层序遍历就是从所在二叉树的根结点出发,首先访问第一层的树根结点,然后从左到右访问第2层上的结点,接着是第三层的结点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

 层序遍历的实现可以借助队列,利用队列先进先出的特点,如果根不为空,就入队;如果左子树或右子树不为空就入队,直到队列为空。

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}printf("\n");QueueDestory(&q);
}

3.结点个数以及高度

1)结点个数:

注意:节点个数的返回,如果是要返回变量一定要注意,函数栈帧的会存储各自的变量,因此最好传入变量地址。

下面介绍不传变量的写法:

//分治思想
int TreeSize(BTNode* root)
{return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}

 2)结点高度

要进行结点的递归比较时,存储变量值可以极大的提高效率

int TreeHeight(BTNode* root)
{if (root == NULL){return 0;}//记录数据,可以减少很多复杂度,提高效率int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

  3)二叉树第K层结点的个数

根结点为第一层

 当前树的第k层个数=左子树的第k-1层个数 +左子树的第k-1层个数

int TreeLevelK(BTNode* root, int k)
{assert(k > 0);if (root == NULL){return 0;}if (k == 1){return 1;}return TreeLevelK(root->left, k - 1)+TreeLevelK(root->right, k - 1);}

 4)查找值为x的结点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* lret = BinaryTreeFind(root->left, x);if (lret){return lret;}BTNode* rret = BinaryTreeFind(root->right, x);if (rret){return rret;}//左右树都没有,返回空return NULL;
}

4. 判断二叉树是否为完全二叉树

完全二叉树按层序走,非空节点一定是连续的。

bool TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);//为空则不入if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}//判断是不是完全二叉树while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//后面有非空,说明非空结点不是完全连续if (front){QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}

5.二叉树的销毁

采用后序遍历,不用存储根结点的位置。

void TreeDestory(BTNode* root)
{if (root == NULL){return;}TreeDestory(root->left);TreeDestory(root->right);free(root);
}

总结

  • 堆排序的基本思想是先将待排序的序列构建成一个最大堆(或最小堆),然后将根节点与最后一个节点交换,再将剩下的 n-1 个节点重新构建成一个最大堆(或最小堆),如此循环,直到所有节点都被交换到适当的位置,从而得到一个有序序列。
  • 前序遍历先访问根节点,然后递归地前序遍历左子树,再递归地前序遍历右子树。
  • 中序遍历先递归地中序遍历左子树,然后访问根节点,再递归地中序遍历右子树。
  • 后序遍历先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。
  • 二叉树的遍历时间复杂度均为 O(n),其中 n 是二叉树的节点数量。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/413938.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

极狐GitLab 如何管理 Kubernetes 集群?

极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门面向中国程序员和企业提供企业级一体化 DevOps 平台&#xff0c;用来帮助用户实现需求管理、源代码托管、CI/CD、安全合规&#xff0c;而且所有的操作都是在一个平台上进行&#xff0c;省事省心省钱。可以一键安装极狐GitL…

Springboot中使用Elasticsearch(部署+使用+讲解 最完整)

目录 引言 一、docker中安装Elasticsearch 1、创建es专有的网络 2、开放端口 3、在es-net网络上安装es和kibana 4、可能出现的问题 5、测试 6、安装IK分词器 7、测试IK分词器 二、结合业务实战 1、准备依赖 2、配置yml 3、读取yml配置 4、准备es配置类 5、编写测…

【AI学习笔记】AIGC,AI绘画 ComfyUI+ComfyUI Manager安装

【AI学习笔记】ComfyUIComfyUI Manager安装 最近在面向BOSS直聘学习ComfyUI的使用&#xff0c;但是不出意外&#xff0c;因为学习者们迥异的电脑配置以及杂乱的AI软件工具包互相纠缠&#xff0c;跟人工智能相关的环境安装多少都会遇到点教程预料不到的BUG。 推荐入门教程&…

盛京银行营收、利润双降下的负重难行,症结在哪儿?

撰稿|芋圆 来源|贝多财经 盛京银行自2020开年始&#xff0c;经营业绩除了在2022年稍有回暖外&#xff0c;均处于营收、利润双降的局面。 2024年半年报显示&#xff0c;盛京银行的资产总额为10683亿元&#xff0c;规模较2023年末收缩1.1%&#xff1b;营业收入46亿元&#xff0…

如何在windows中使用hfd.sh aria2c下载huggingface文件

这里写目录标题 简介hfd.sh使用方法windows系统安装aria2c aria2c官方文档&#xff1a; https://aria2.github.io/manual/en/html/aria2c.html 简介 我们在下载huggingface上模型权重的时候&#xff0c;要么在浏览器上直接下&#xff0c;要么使用官方下载程序。浏览器上还得一…

easy_spring_boot Java 后端开发框架

Easy SpringBoot 基于 Java 17、SpringBoot 3.3.2 开发的后端框架&#xff0c;集成 MyBits-Plus、SpringDoc、SpringSecurity 等插件&#xff0c;旨在提供一个高效、易用的后端开发环境。该框架通过清晰的目录结构和模块化设计&#xff0c;帮助开发者快速构建和部署后端服务。…

应急响应-应急响应流程(各个阶段与实战)

目录 前言准备阶段检测阶段研判分析定损止损&#xff08;对应遏制、根除阶段&#xff09;定损止损 攻击还原清理恢复总结复盘实战讲解进程ssh暴力破解命令混淆派生恶意命令命令注入 网络文件webshellC2脚本木马 参考 前言 做入侵检测时会有一些攻击告警&#xff0c;需要做应急…

《神话:悟空》的破晓之路:文化深度与技术巅峰的交响乐章

在八月的炽热中&#xff0c;《黑神话&#xff1a;悟空》如同一道璀璨的光芒&#xff0c;划破了国产游戏的寂静夜空&#xff0c;不仅以其惊人的销量速度震撼了业界&#xff0c;更以其深厚的文化底蕴与顶尖的游戏设计&#xff0c;在全球玩家心中留下了不可磨灭的印记。这款游戏的…

鸿蒙XComponent组件的认识

概述&#xff1a; XComponent组件作为一种渲染组件&#xff0c;通常用于满足开发者较为复杂的自定义渲染需求&#xff0c;例如相机预览流的显示、游戏画面的渲染、自定义视频播放器等等。其中Native API是其核心内容&#xff01; 其可通过指定其type字段来实现不同的功能&…

入行「游戏策划」,该从何处下手?

想知道策划岗位该怎么入行可点击蓝链 相比较起以技术为最重要评判标准的开发岗&#xff0c; 「游戏策划」这一岗位在非业界人士的眼中 一直都是一个风评方差很大的岗位。 有人说策划岗又轻松又威风&#xff0c; 只需要输出想法&#xff0c;落地都交给开发&#xff0c; 干…

u盘pe怎么安装系统_u盘pe安装系统详细步骤

u盘pe怎么安装系统&#xff1f;u盘pe安装系统需要准备一个u盘&#xff0c;然后将u盘制作成pe&#xff0c;进入pe后再安装系统&#xff0c;下面小编就教大家u盘pe安装系统详细步骤教程。 u盘pe启动盘是什么&#xff1f; u盘pe启动盘是一种可引导的USB存储设备&#xff0c;其中包…

【js逆向专题】4.python调用JS和扣代码

小节目标: 掌握 python调用js代码方式熟悉 js开放接口进行调用了解 补环境的基本概念掌握 js调试技巧 一. pyexecjs的使用 1. 简介 PyExecJS 是一个 Python 库&#xff0c;用于在 Python 环境中执行 JavaScript 代码。它实际上是对 ExecJS 库的 Python 封装&#xff0c;Exec…

Makefile入门

Makefile入门 文章目录 Makefile入门一、Makefile入门1.1 编译工具及构建工具介绍&#xff1a;1.2 编译的四个阶段&#xff1a;1.3 Makefile的认知&#xff1a;1.3.1 什么是Makefile&#xff1a;1.3.2 Makefile的规则与示例&#xff1a; 二、Makefile的基本语法&#xff1a;2.1…

Java注解和JDK新特性

1. 注解 1.1. 认识注解 Annotation&#xff1a;JDK1.5新提供的技术 编译检查&#xff1a;比如SuppressWarnings, Deprecated和Override都具有编译检查的作用替代配置文件&#xff1a;使用反射来读取注解的信息 注解就是代码里的特殊标记&#xff0c;用于替代配置文件&#…

内存管理篇-17解开页表的神秘面纱-下

1.页表初探遗留问题-页表的创建过程 使用MMU之前&#xff0c;页表要准备好&#xff0c;怎么准备的&#xff1f;如何把物理内存通过section映射构建页表页表的创建过程分析&#xff1a;__create_page_tables--创建临时页表&#xff0c;然后在开启MMU 页表的大小和用途页表在内存…

zdppy_cache缓存框架升级,支持用户级别的缓存隔离,支持超级管理员管理普通用户的缓存

启动服务 import zdppy_api as api import zdppy_cachekey1 "admin" key2 "admin"app api.Api(routes[*zdppy_cache.zdppy_api.cache(key1, key2, api) ])if __name__ __main__:import zdppy_uvicornzdppy_uvicorn.run(app, host"0.0.0.0",…

Mac 安装Hadoop教程

1. 引言 本教程旨在介绍在Mac 电脑上安装Hadoop&#xff0c;便于编程开发人员对大数据技术的熟悉和掌握。 2.前提条件 2.1 安装JDK 想要在你的Mac电脑上安装Hadoop&#xff0c;你必须首先安装JDK。具体安装步骤这里就不详细描述了。你可参考Mac 安装JDK8。 2.2 配置ssh环境…

代码随想录 -- 字符串 -- 重复的子字符串

459. 重复的子字符串 - 力扣&#xff08;LeetCode&#xff09; 暴力解法&#xff1a; 思路&#xff1a; 假设子串 s 长度 n 为 i&#xff0c;从1到n/2遍历&#xff1a; 1. 如果 s 能够由他的子串重复构成&#xff0c;那么 s 的长度 n 一定整除其子串 s 的长度 n&#xff0c; …

结合Wireshark抓包实战,图文详解TCP三次握手及四次挥手原理(附下载)

网络安全的基础是网络&#xff0c;若连最基础的网络协议都搞不明白&#xff0c;何谈网络安全。针对核心的TCP协议&#xff0c;本文通过Wireshark工具抓取并分析TCP三次握手和四次挥手的详细过程&#xff0c;包括数据包捕获步骤&#xff0c;每个握手阶段和挥手阶段的数据包内容解…

数据分析处理库(pandas)

目录 数据预处理 数据读取 DataFrame结构 数据索引 创建DataFrame Series操作 数据分析 统计分析 pivot数据透视表 groupby操作 常用函数操作 Merge操作 排序操作 缺失值处理 apply自定义函数 时间操作 绘图操作 大数据处理技巧 数值类型转换 属性类型转换…