非线性链表之树结构和堆的代码实现

目录

一.树的结构

1.1树概念及结构

1.2 树的相关概念

1.3 树的表示 

 二. 二叉树概念及结构

2.1概念

2.2 特殊的二叉树： 

2.3 二叉树的性质

2.4 二叉树的存储结构

2.4.1. 顺序存储

​2.4.2. 链式存储

三. 堆的概念及结构

定义

性质

堆的实现

四.堆的代码实现

有关与堆的接口：Heap.h

堆的构建

堆的插入

删除堆顶

堆的销毁

五.结尾

一.树的结构

1.1树概念及结构

  • 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
  • 有一个特殊的结点，称为根结点，根节点没有前驱结点。
  • 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
  • 因此，树是递归定义的。

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

1.2 树的相关概念

  • 基本术语：
    • 节点：树的基本构成单位，每个节点包含一个数据元素及若干指向其子树的分支。
    • 根节点：树中唯一的没有父节点的节点。
    • 叶子节点或终端节点：度为0的节点，即没有子节点的节点。
    • 非终端节点或分支节点：度不为0的节点。
    • 树的度：树中节点的度的最大值。
    • 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。
    • 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
    • 兄弟节点：具有相同父节点的节点互称为兄弟节点。
    • 树的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
    • 树的高度或深度：树中节点的最大层次。

 

1.3 树的表示 

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间 的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

俗称“左孩子右兄弟”

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

 

 二. 二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合，该集合:

        1. 或者为空

        2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：

        1. 二叉树不存在度大于2的结点

        2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树 注意：对于任意的二叉树

都是由以下几种情况复合而成的：

2.2 特殊的二叉树： 

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也

就是 说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深

度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的

结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

2.3 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^{\left ( i-1 \right )}个结点.

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

3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n1 ,则有 n0＝n1 ＋1

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= \log_2{n+1}

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：

        1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

        2. 若2i+1，左孩子序号：2i+1，2i+1>=n否则无左孩子

        3. 若2i+2，右孩子序号：2i+2，2i+2>=n否则无右孩子    

2.4 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

2.4.1. 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空 间的浪费。而现实中使用中只有堆才会使用数组来存储。

2.4.2. 链式存储

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

三. 堆的概念及结构

定义

堆可以被看作是一个可以被视作一棵完全二叉树的数组对象，即是一种顺序存储结构的完全二叉树。堆的物理结构本质上是顺序存储的，是线性的。

性质

  1. 堆序性：堆中某个结点的值总是不大于或不小于其父结点的值。根据这个性质，堆可以分为两种：
    • 最大堆（大根堆）：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。
    • 最小堆（小根堆）：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。
  2. 完全二叉树：堆总是一棵完全二叉树。除了根结点和最后一个左子结点可以没有兄弟结点，其他结点都必须有兄弟结点。

堆的实现

堆的实现通常依赖于数组，其中父节点和子节点之间存在固定的索引关系。例如，对于数组中任意位置i上的元素，其左子节点的位置是2i+1，右子节点的位置是2i+2，父节点的位置则是(i-1)/2（向下取整）。

堆支持多种操作，包括但不限于：

  1. 插入（Push）：向堆中添加一个新元素，并保持堆的性质。这通常通过首先将新元素添加到数组的末尾，然后通过一系列的向上调整（上浮）操作来完成。

  2. 删除堆顶（Pop）：移除堆顶元素（即根节点），并通过一系列的向下调整（下沉）操作来保持堆的性质。在最小堆中，新的堆顶将是剩余元素中的最小值；在最大堆中，则是最大值。

  3. 获取堆顶（Top）：返回堆顶元素的值，但不移除它。

  4. 调整堆：包括向上调整和向下调整两种操作，用于在插入或删除元素后恢复堆的性质

四.堆的代码实现

        关与堆的接口：Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int HPDataPyde;typedef struct Heap
{HPDataPyde* a;int sz;int capacity;
}HP;//堆的构建
void HPInit(HP* pc);//堆的销毁
void HPDestroy(HP* pc);//堆的插入
void HPPush(HP* pc,HPDataPyde x);//堆的删除
void HPPop(HP* pc);//获取堆顶的元素
HPDataType HPTop(Heap* php);

堆的构建

为堆开辟空间

void HPInit(HP* pc)
{assert(pc);pc->a = (HPDataPyde*)malloc(sizeof(HPDataPyde)*4);if (pc->a == NULL){perror("malloc");return;}pc->sz = 0;pc->capacity = 4;
}

堆的插入

void swap(HPDataPyde* a,HPDataPyde* b)
{HPDataPyde tmp = *a;*a = *b;*b = tmp;
}void HPAdjustPush(HP* pc,int child)
{assert(pc);int father = (child - 1) / 2;while (child > 0){if (pc->a[father] > pc->a[child]){swap(&pc->a[father], &pc->a[child]);child = father;father = (child - 1) / 2;}else{return;}}
}void HPPush(HP* pc, HPDataPyde x)
{assert(pc);if (pc->sz == pc->capacity){HPDataPyde* tmp = (HPDataPyde*)realloc(pc->a, sizeof(HPDataPyde) * pc->capacity * 2);if (tmp == NULL){perror("realloc");return;}pc->a = tmp;pc->capacity *= 2;}  pc->a[pc->sz] = x;pc->sz++;HPAdjustPush(pc, pc->sz-1);
}

删除堆顶

void HPAdjustdown(HP* pc, int father)
{assert(pc);HPDataPyde child = father * 2 + 1;while (child < pc->sz){if (child+1 < pc->sz && pc->a[child] < pc->a[child + 1]){child++;}if (pc->a[father] > pc->a[child]){swap(&pc->a[father], &pc->a[child]);father = child;child = father * 2 + 1;}else{return;}}
}void HPPop(HP* pc)
{assert(pc);swap(&pc->a[0],&pc->a[pc->sz-1]);pc->sz--;HPAdjustdown(pc, 0);
}

堆的销毁

void HPDestroy(HP* pc)
{assert(pc);free(pc->a);pc->a = NULL;pc->sz = pc->capacity = 0;
}

五.结尾

如果有什么建议和疑问，或是有什么错误，希望大家可以在评论区提一下。
希望大家以后也能和我一起进步！！
如果这篇文章对你有用的话，希望能给我一个小小的赞！

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

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

相关文章

kafka零拷贝sendfile及mmap简述

kafka零拷贝sendfile及mmap简述

概述 通常在选型比较消息中间件时&#xff0c;都会在备选栏有kafka&#xff1b; kafka突出的特点就是高吞吐&#xff0c;零拷贝&#xff1b; 这里的零拷贝其实就是内核和用户空间之间没有copy&#xff0c;并不是真的0拷贝&#xff1b; 毕竟数据在磁盘&#xff0c;要读到网卡发…
阅读更多...
k8s集群管理 Pod管理命令

k8s集群管理 Pod管理命令

k8s集群管理命令 信息查询命令 子命令说明help用于查看命令及子命令的帮助信息cluster-info显示集群的相关配置信息api-resources查看当前服务器上所有的资源对象api-versions查看当前服务器上所有资源对象的版本config管理当前节点上的认证信息 资源对象概述 Pod概述 Pod 管…
阅读更多...
# 利刃出鞘_Tomcat 核心原理解析（三）

# 利刃出鞘_Tomcat 核心原理解析（三）

利刃出鞘_Tomcat 核心原理解析&#xff08;三&#xff09; 一、 Tomcat专题 - Tomcat架构 - 启动流程 1、Tomcat 启动流程 2、Tomcat 启动 步骤 : 1&#xff09; 启动tomcat &#xff0c; 需要调用 bin/startup.bat (在linux 目录下 , 需要调用 bin/startup.sh) &#xff0c…
阅读更多...
Dubbo框架实现RPC远程调用包括nacos的配置和初始化

Dubbo框架实现RPC远程调用包括nacos的配置和初始化

项目背景介绍 这个技术我是直接在项目中运用并且学习的&#xff0c;所以我写笔记最优先的角度就是从项目背景出发 继上一次API网关完成了这个实现用户调用一次接口之后让接口次数增多的操作之后&#xff0c;又迎来了新的问题。 就是我们在调用接口的时候需要对用户进行校验&…
阅读更多...
【Linux】详解IPC：共享内存

【Linux】详解IPC：共享内存

目录 IPC 共享内存 1.理解 2.运用 1. 创建 ipc - shmget 2. 创建 key - ftok ⭕shmid vs key 3. 连接 - shmat 4. 脱离 - shmdt 5. 控制/删除 - shmctl 总结 代码示例 3.实验 comm.hpp processa.cc processb.cc log.hpp makefile 测试 4.思考 IPC 进程间通…
阅读更多...
vue3引入模块报错：无法找到模块“xxx”的声明文件

vue3引入模块报错：无法找到模块“xxx”的声明文件

使用vue3ts导入vue文件的时候&#xff0c;报错&#xff1a;找不到模块“./XXX.vue”或其相应的类型声明 这是由于&#xff1a;Vue 文件并不是标准的 JavaScript 模块&#xff0c;因此 TypeScript 需要通过这种声明方式来理解和处理这些文件 我是使用vite创建的项目&#xff0…
阅读更多...
【生信入门linux篇】如何安装一个linux虚拟机用于学习

【生信入门linux篇】如何安装一个linux虚拟机用于学习

一.虚拟机 虚拟机&#xff08;Virtual Machine&#xff0c;简称VM&#xff09;是一种软件实现的计算机系统&#xff0c;它能够在物理计算机上模拟出多个独立的计算机环境。每个虚拟机都可以运行自己的操作系统和应用程序&#xff0c;就像在独立的物理计算机上一样。虚拟机技术…
阅读更多...
小试牛刀-区块链Solana多签账户

小试牛刀-区块链Solana多签账户

目录 1.什么是多签账户 2.多签账户的特点 2.1 多个签名者 2.2 最小签名要求 2.3 常见应用场景 3.多签账户实现 3.1 账户的创建 3.1.1 创建新账户 3.1.2 获取创建和初始账户事务 3.1.3 账户的签名 3.2 代币转移操作 Welcome to Code Blocks blog 本篇文章主要介绍了 …
阅读更多...
LeetCode_sql_day16（601.体育馆的人流量）

LeetCode_sql_day16（601.体育馆的人流量）

描述&#xff1a;601. 体育馆的人流量 - 力扣&#xff08;LeetCode&#xff09; 编写解决方案找出每行的人数大于或等于 100 且 id 连续的三行或更多行记录。 返回按 visit_date 升序排列 的结果表。 输入Stadium表: ----------------------------- | id | visit_date | peop…
阅读更多...
电子电气架构 --- 车辆模式管理

电子电气架构 --- 车辆模式管理

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。 老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师： 屏蔽力是信息过载时代一个人的特殊竞争力，任何消耗你的人和事，多看一眼都是你的不对。非必要不费力证明自己，无利益不试图说服别人，是精神上的节…
阅读更多...
CUDA-MODE 第一课: 如何在 PyTorch 中 profile CUDA kernels

CUDA-MODE 第一课: 如何在 PyTorch 中 profile CUDA kernels

我的课程笔记&#xff0c;欢迎关注&#xff1a;https://github.com/BBuf/how-to-optim-algorithm-in-cuda/tree/master/cuda-mode 第一课: 如何在 PyTorch 中 profile CUDA kernels 这里是课程规划&#xff0c;有三位讲师 Andreas, Thomas, Mark&#xff0c;然后大概2周出一个 …
阅读更多...
Elasticsearch：用例、架构和 6 个最佳实践

Elasticsearch：用例、架构和 6 个最佳实践

1. 什么是 Elasticsearch&#xff1f; Elasticsearch 是一个开源分布式搜索和分析引擎&#xff0c;专为处理大量数据而设计。它建立在 Apache Lucene 之上&#xff0c;并由Elastic 支持。Elasticsearch 用于近乎实时地存储、搜索和分析结构化和非结构化数据。 Elasticsearch 的…
阅读更多...
4.3.2 C++ 平面拟合的实现

4.3.2 C++ 平面拟合的实现

4.3.2 C 平面拟合的实现 参考教程&#xff1a; gaoxiang12/slam_in_autonomous_driving: 《自动驾驶中的SLAM技术》对应开源代码 (github.com) Eigen打印输出_打印eigen矩阵-CSDN博客 1. 编写 Plane fitting 1.1 创建文件夹 通过终端创建一个名为Plane_fitting的文件夹以保…
阅读更多...
文件操作与IO（下）

文件操作与IO（下）

✨个人主页&#xff1a; 不漫游-CSDN博客 目录 前言 流对象 InputStream OutputStream 运用 在控制台进行输入并写入文件 进行普通文件的复制 前言 之前的文章文件操作与IO&#xff08;上&#xff09;已经介绍了文件系统的相关操作&#xff0c;这次的主角是文件内容的相关…
阅读更多...
SpringBoot 框架学习笔记（七）：Thymeleaf、拦截器 和 文件上传实现（解决了文件重名 和 按日期分目录存放问题）

SpringBoot 框架学习笔记（七）：Thymeleaf、拦截器 和 文件上传实现（解决了文件重名 和 按日期分目录存放问题）

1 Thymeleaf 1.1 基本介绍 &#xff08;1&#xff09;官方文档&#xff1a;Tutorial: Using Thymeleaf &#xff08;2&#xff09;Thymeleaf 是什么 Thymeleaf 是一个跟 Velocity、FreeMarker 类似的模板引擎&#xff0c;可完全替代 JSPThymeleaf 是一个 java 类库&#xf…
阅读更多...
.net core webapi 自定义异常过滤器

.net core webapi 自定义异常过滤器

1.定义统一返回格式 namespace webapi;/// <summary> /// 统一数据响应格式 /// </summary> public class Results<T> {/// <summary>/// 自定义的响应码&#xff0c;可以和http响应码一致&#xff0c;也可以不一致/// </summary>public int Co…
阅读更多...
vue 打包时候的分包

vue 打包时候的分包

export default defineConfig({plugins: [vue()],resolve: {alias: {: fileURLToPath(new URL(./src/, import.meta.url))}},// 分包&#xff0c;node_modules中的单独打包成名字为vendor的js文件build: {rollupOptions: {manualChunks(id) {if (id.includes(node_modules)) {r…
阅读更多...
EF8 学习过程中的问题和解决方案

EF8 学习过程中的问题和解决方案

一、varchar类型字段如果为null 无法使用contains来判断是否包含字符串 1. 有问题的代码&#xff1a; contractList _dbcontext.contractHeads.Where(u > u.code.Contains(queryStr) || u.name.Contains(queryStr) || u.companyName.Contains(queryStr) || u.customerNa…
阅读更多...
uniapp开启数据压缩的坑-SpringBoot-gzip

uniapp开启数据压缩的坑-SpringBoot-gzip

1、服务器配置 服务端开启的数据压缩配置 server:port: ${port:8881}servlet:# 应用上下文路径context-path: /orderserverundertow:threads:io: 4worker: 500buffer-size: 2048# 开启Gzip压缩&#xff0c;compression:# 开启压缩enabled: true# 对json格式内容进行压缩mime-…
阅读更多...
KCTF 闯关游戏：1 ~ 7 关

KCTF 闯关游戏：1 ~ 7 关

前言 看雪CTF平台是一个专注于网络安全技术竞赛的在线平台&#xff0c;它提供了一个供网络安全爱好者和技术专家进行技术交流、学习和竞技的环境。CTF&#xff08;Capture The Flag&#xff0c;夺旗赛&#xff09;是网络安全领域内的一种流行竞赛形式&#xff0c;起源于1996年…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023