【数据结构】二叉树-堆（下）-链式二叉树

在这里插入图片描述
个人主页~

二叉树-堆（上）
栈和队列

二叉树

  • 四、堆的代码实现
    • Heap.h
    • Heap.c
    • test.c
  • 五、堆的应用
    • 堆排序思想进行排序
  • 六、二叉树链式结构的实现
    • BTree.h
    • BTree.c
    • test.c

四、堆的代码实现

Heap.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
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);
void AdjustUp(HPDataType* a, int child); 
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);

Heap.c

#include "Heap.h"

void Swap(HPDataType* n1, HPDataType* n2)
{
	HPDataType* tmp = *n1;
	*n1 = *n2;
	*n2 = tmp;
}

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if(hp->capacity == hp->size)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);
}

void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 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;
	while (child < n)
	{
		// 选出左右孩子中小/大的那个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

test.c

#include "Heap.h"

int main()
{
	Heap h;
	HeapInit(&h);
	HeapPush(&h, 1);
	HeapPush(&h, 4);
	HeapPush(&h, 7);
	HeapPush(&h, 2);
	HeapPush(&h, 5);
	HeapPush(&h, 9);
	printf("%d\n", HeapTop(&h));

	HeapPop(&h);
	printf("%d", HeapTop(&h));

	HeapDestory(&h);
	return 0;
}

在这里插入图片描述

五、堆的应用

堆排序思想进行排序

我们在上面实现了堆，如果想要升序数组就建大堆，降序数组就建小堆
但建堆并不意味着建完就可以了，想要升序/降序数组的话，建完大堆/小堆后用向下调整算法将堆调整成小堆/大堆，这样调整出来的堆就是一个升序/降序数组

在排序当中，堆排序是一种时间复杂度较低的排序，要远优于冒泡排序，在使用堆排序时，要使用向下调整算法，这样我们就可以最大限度的减少时间的使用

在堆排序中有一个很经典的问题就是TopK问题，即一堆数据，个数为n（n>>k）,求这堆数据中最大/最小的k个数据
如果是求前k个最大的元素，则用前k个元素建小堆
如果是求前k个最小的元素，则用前k个元素建大堆
然后再用剩下的n-k个元素一次与堆顶元素来比较，不满足则替换堆顶元素
也就是说，我们用求前k个最大数据来举例，我们先将整组数据的前k个元素建一个小堆，小堆的根是整个堆里最小的，用它来和剩余的n-k个元素比较，如果剩余的元素中的某一个比小堆根大，那么就替换掉，再用向下调整算法调整，这样一来，最大的数据都沉底了，堆中最小的数据继续与剩余的数据比较，重复上述步骤，当所有剩余元素都比完了之后，剩下的这个小堆就是前k个最大数

六、二叉树链式结构的实现

BTree.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);

BTree.c

#define _CRT_SECURE_NO_WARNINGS

#include "BTree.h"

BTNode* BuyNode(BTDataType x)
{
	BTNode* new = (BTNode*)malloc(sizeof(BTNode));
	if (new == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	new->data = x;
	new->left =  NULL;
	new->right = NULL;

	return new;
}

BTNode* BinaryTreeCreate(BTDataType* a,int n, int* pi) 
{
    if (*pi >= n || a[*pi] == '#')
	{ 
		// 如果到达数组末尾或遇到#，则返回NULL  
        (*pi)++;
        return NULL;
    }

	BTNode* node = BuyNode(a[*pi]);
    (*pi)++; // 移动到下一个节点  

    node->left = BinaryTreeCreate(a, n, pi); // 递归创建左子树  
    node->right = BinaryTreeCreate(a, n, pi); // 递归创建右子树  

    return node;
}

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

int BinaryTreeSize(BTNode* root)
{
	//return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

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

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data = x)
		return root;
	BTNode* ret1 = BinaryTreeFind(root->left, x);

	if (ret1)
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);

	if (ret2)
		return ret2;

	return NULL;
}

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

}

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

}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BinaryTreeInOrder(root->left);
	BinaryTreeInOrder(root->right);
	printf("%c ", root->data);

}

test.c

#define _CRT_SECURE_NO_WARNINGS

#include "BTree.h"


int main()
{
	int i = 0;
	BTDataType val[] = { "ABD##E#H##CF##G##" };

	BTNode* tree = BinaryTreeCreate(val, 17, &i);
	BinaryTreePrevOrder(tree);
	printf("\n");
	BinaryTreeInOrder(tree);
	printf("\n");
	BinaryTreePostOrder(tree);
	printf("\n");
	
	printf("%d\n", BinaryTreeSize(tree));

	printf("%d\n", BinaryTreeLeafSize(tree));

	printf("%d\n", BinaryTreeLevelKSize(tree,3));


	BinaryTreeDestory(tree);
	return 0;
}

在这里插入图片描述

下一篇我们来详细剖析链式二叉树的实现~
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Leetcode：寻找两个正序数组的中位数

Leetcode：寻找两个正序数组的中位数

题目链接&#xff1a;4. 寻找两个正序数组的中位数 - 力扣&#xff08;LeetCode&#xff09; 题目分析 1、当只有一个有序数组时&#xff0c;该数组的中位数会将该数组分为两份&#xff1a;左子数组 和 右子数组 2、当有两个有序数组时&#xff0c; 我们仍然可以通过一条分隔…
阅读更多...
计算机网络之快重传和快恢复以及TCP连接与释放的握手

计算机网络之快重传和快恢复以及TCP连接与释放的握手

快重传和快恢复 快重传可以让发送方尽早得知丢失消息&#xff0c; 当发送消息M1,M2&#xff0c;M3,M4,M5后,假如消息M2丢失&#xff0c;那么按照算法会发送对M2报文前一个报文M1的重复确认&#xff08;M1正常接受到&#xff0c;已经发送了确认),然后之后收到M4,M5,也会发送两…
阅读更多...
内网安全之注册和查看证书

内网安全之注册和查看证书

注册证书 如图所示&#xff0c;是 Will Schroeder 和 Lee Christensen 发布的 Certified_Pre-Owned 白皮书里面画的证书注册流程: 从图中我们可以看到&#xff0c;证书注册流程如下&#xff1a; 客户端生成一对公、私钥。客户端生成证书签名请求(CSR&#xff0c;Certificate…
阅读更多...
linux系统——性能检测工具glances

linux系统——性能检测工具glances

在linux系统中&#xff0c;由python开发的glances工具是一个功能强大的性能检测工具 可以通过yum进行安装 安装glances后&#xff0c;进入命令界面 glance支持网站模式&#xff0c;将监控到的数据以网站形式显示出来 这里需要用python包管理命令 使用glances -w开放…
阅读更多...
Java集合-List(Collection子接口)及其子类(ArrayList、Vector、LinkedList)

Java集合-List(Collection子接口)及其子类(ArrayList、Vector、LinkedList)

List接口是 Collection接口的子接口。 1、List集合类中数据有序&#xff0c; 即添加顺序和取出顺序有序&#xff0c;而且可以重复。 2、List集合类中每个元素都有其对应的顺序索引&#xff0c;即支持索引。例&#xff0c;list.get(2)&#xff1b;取第三个元素。 3、实现类有很多…
阅读更多...
百度地图1

百度地图1

地图的基本操作 百度地图3.0文档 百度地图3.0实例中心 设置地图 centerAndZoom(center: Point, zoom: Number)设初始化地图,center类型为Point时&#xff0c;zoom必须赋值&#xff0c;范围3-19级&#xff0c; // 百度地图API功能var map new BMap.Map("map"); //…
阅读更多...
CentOS8搭载正反向解析dns服务器

CentOS8搭载正反向解析dns服务器

1.介绍&#xff08;是什么&#xff09; DNS&#xff08;Domain Name System&#xff09;&#xff0c;即域名系统&#xff0c;是一个将域名和 IP 地址相互映射的分布式数据库&#xff0c;它可以将用户输入的域名转换成对应的 IP 地址。DNS 由多个服务器组成&#xff0c;分为多个…
阅读更多...
企业想要搭建一个虚拟展厅需要多少钱？

企业想要搭建一个虚拟展厅需要多少钱？

企业搭建虚拟展厅的费用会根据多种因素有所不同&#xff0c;主要包括展厅的类型、规模、功能需求、技术复杂度以及服务商的定价策略等。以下是关于虚拟展厅搭建费用的分点说明和归纳&#xff1a; 一、展厅类型&#xff1a; 1、全景实拍展厅&#xff1a; 利用VR全景拍摄技术还…
阅读更多...
结构体中内存的对齐

结构体中内存的对齐

前言 学C的同学应该知道~ 想精通C语言就不得不面对—指针与内存 续上次指针进阶&#xff0c;这一章我来聊一聊C语言内存对齐的问题 学习结构体的你有没有注意过结构体向系统申请的内存为多少呢的&#x1f601; 思考 #include<stdio.h> typedef struct s1 {char a;char …
阅读更多...
【Python】 如何获取 Python 函数的名称作为字符串？

【Python】 如何获取 Python 函数的名称作为字符串？

基本原理 在 Python 中&#xff0c;获取函数名称是一个简单但非常有用的技巧&#xff0c;尤其是当你需要动态地引用函数或者在日志、调试中需要函数名称时。Python 提供了几种方法来获取函数的名称。 方法一&#xff1a;使用 __name__ 属性 每个函数对象都有一个 __name__ 属…
阅读更多...
【Unity】使用Jenkins实现远程Unity打包

【Unity】使用Jenkins实现远程Unity打包

前言 很多时候&#xff0c;我们需要自动打包&#xff0c;比如下班了&#xff0c;我要出一个包明天早上用。比如每天夜里12点&#xff0c;我需要定时出一个稳定包。 这个时候就需要Jenkins了。 1.安装环境 安装 jenkins 之前&#xff0c;需要安装Java 。Java下载网站 ①下载…
阅读更多...
校园交友|基于SprinBoot+vue的校园交友网站(源码+数据库+文档)

校园交友|基于SprinBoot+vue的校园交友网站(源码+数据库+文档)

校园交友网站 目录 基于SprinBootvue的校园交友网站 一、前言 二、系统设计 三、系统功能设计 1系统功能模块 2后台功能模块 5.2.1管理员功能模块 5.2.2用户功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#x…
阅读更多...
音视频开发9 FFmpeg 解复用相关整体说明，重要API说明

音视频开发9 FFmpeg 解复用相关整体说明，重要API说明

一&#xff0c;播放器框架 二 常用音视频术语 容器&#xff0f;文件&#xff08;Conainer/File&#xff09;&#xff1a; 即特定格式的多媒体文件&#xff0c; 比如mp4、flv、mkv等。 媒体流&#xff08;Stream&#xff09;&#xff1a; 表示时间轴上的一段连续数据&#xff0…
阅读更多...
【技术实操】银河高级服务器操作系统实例分享，数据库日志文件属主不对问题分析

【技术实操】银河高级服务器操作系统实例分享，数据库日志文件属主不对问题分析

1. 问题现象描述 2023 年 06 月 30 日在迁移数据库过程中&#xff0c;遇到数据库 crash 的缺陷&#xff0c;原因如下&#xff1a;在数据库启动时候生成的一组临时文件中&#xff0c;有 owner 为 root 的文件&#xff0c; 文件权限默认为 640&#xff0c; 当数据库需要使用的时…
阅读更多...
C++系列——————类和对象（上）

C++系列——————类和对象（上）

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、面向对象的三大特征二、类的引入2.1类的定义 三.类的访问限定符3.1访问限定符的介绍3.2.访问限定符的使用 四、类的作用域五、类的实例化六、类对象模型6.1…
阅读更多...
惠海 H6251L 降压恒压芯片IC 48V 60V 100V 150V 200V 降3.3V 5V 12V 5A大电流 低功耗，动态响应优异

惠海 H6251L 降压恒压芯片IC 48V 60V 100V 150V 200V 降3.3V 5V 12V 5A大电流 低功耗，动态响应优异

H6251L是一款多样化的高压降压开关控制器&#xff0c;它具备许多引人注目的特性和优势&#xff0c;使其在多个领域都有许多的应用。以下是对H6251L的详细分析&#xff1a; 首先&#xff0c;H6251L具有宽压8V-200V的输入范围&#xff0c;这意味着它可以在电压环境下稳定工作&am…
阅读更多...
【康耐视国产案例】智能AI相机联合OSARO为Zenni眼镜实现订单履约自动化

【康耐视国产案例】智能AI相机联合OSARO为Zenni眼镜实现订单履约自动化

在电商潮流下&#xff0c;Zenni眼镜作为全球领先的在线眼镜零售商&#xff0c;每年销售超过600万副眼镜&#xff0c;却面临着一个独特而复杂的问题——需要通过扫描眼镜盒内的条形码来处理订单。传统手动处理已经到达流程瓶颈&#xff0c;急需一种更加自动化、可扩展的方法。为…
阅读更多...
STM32 HAL库USART的接收数据方法实现（STM32Cube_FW_F1_V1.8.5）

STM32 HAL库USART的接收数据方法实现（STM32Cube_FW_F1_V1.8.5）

目录 概述 1 使用STM32Cube生成项目 1.1 软件版本信息 1.2 配置串口相关参数 1.3 生成工程 2 问题描述 3 解决问题 3.1 修改代码 3.2 编写新的回调函数 4 测试 概述 本文主要介绍STM32 HAL库USART的接收数据方法实现&#xff0c;笔者使用的HAL库为STM32Cube_FW_F1_V1.…
阅读更多...
Leetcode刷题笔记6

Leetcode刷题笔记6

34. 在排序数组中查找元素的第一个和最后一个位置 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣&#xff08;LeetCode&#xff09; 解法一&#xff1a;暴力查找 [1, 2, 3, 3, 3, 4, 5] t 3 从前往后扫描暴力查找&#xff0c;最坏情况下O(N) 优化 利用数组有序的…
阅读更多...
【动态规划 组合数学 放球问题】2338. 统计理想数组的数目

【动态规划 组合数学 放球问题】2338. 统计理想数组的数目

本文涉及知识点 动态规划汇总 组合数学汇总 【组合数学 隔板法 容斥原理】放球问题 本题同解 【动态规划】【前缀和】【分组】2338. 统计理想数组的数目 LeetCode2338. 统计理想数组的数目 给你两个整数 n 和 maxValue &#xff0c;用于描述一个 理想数组 。 对于下标从 0…
阅读更多...
最新文章

Copyright @ 2022~2023