当前位置: 首页 > news >正文

数据结构(树)

1.树的概念和结构

树,顾名思义,它看起来像一棵树,是由n个结点组成的非线性的数据结构。

下面就是一颗树:

树的一些基本概念:

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

2.树的表示

树的表示比线性表复杂,它不仅要存储数据,还要存储和其他结点的关系。

树有很多的表示方法,下面是最为常见的一种:孩子兄弟表示法

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

如图:每一个结点都有自己孩子结点和兄弟结点,如果没有就存NULL,这样就可以表示每一个结点了。

3.二叉树的概念和结构

先看下面图:

每一个树干都有两个树枝,这就是我们生活中的二叉树,而数据结构中的二叉树有两种常见又特殊的:

完全二叉树:

满二叉树:

4.二叉树的存储

二叉树的存储有顺序存储和链式存储:

顺序存储:

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

链式存储:

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

二叉链:

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}

三叉链:

// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* parent; // 指向当前结点的双亲
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
};

普通二叉树一般不用顺序结构存储,因为会有空间的浪费,只要完全二叉树才适合顺序存储,也就是堆:

5.堆的概念和结构

堆是一种完全二叉树,堆又分为大堆和小堆。

大堆:每一个父结点都比它的子结点大

小堆:每一个父结点都比子结点小

相关文章:

数据结构(树)

1.树的概念和结构 树,顾名思义,它看起来像一棵树,是由n个结点组成的非线性的数据结构。 下面就是一颗树: 树的一些基本概念: 结点的度:一个结点含有的子树的个数称为该结点的度; 如上图&#…...

HTML静态网页成品作业(HTML+CSS)——川西旅游介绍网页(2个页面)

🎉不定期分享源码,关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 🏷️本套采用HTMLCSS,未使用Javacsript代码,共有2个页面。 二、作品演示 三、代…...

MySQL数据库单表查询中查询条件的写法

1.使用比较运算符作为查询条件 ; !; >; >; <; <; 如上图所示&#xff0c;可以使用命令select 字段&#xff0c;字段 from 表名 where Gender “M”; 即挑选出Gender “M” 的教师&#xff0c; 如上图所示&#xff0c;可以使用命令select 字段&#xff0c;…...

SQL靶场搭建

概述 简单介绍一下SQL靶场的搭建&#xff0c;以及在搭建过程中遇到的一些问题。使用该软件搭建靶场相对简单&#xff0c;适合新手小白。当然&#xff0c;也可以在自己的虚拟机下进行搭建&#xff0c;相对来说就较为复杂。本章主要讲解使用Phpstudy进行SQL靶场搭建。 这里我推…...

Cocos Creator 帧动画播放组件制作详解

前言 Cocos Creator 是一个强大的游戏开发工具&#xff0c;提供了丰富的功能和组件&#xff0c;其中帧动画播放组件是游戏开发中常用的组件之一&#xff0c;通过帧动画播放组件可以实现角色动画、特效动画等效果。本文将详细介绍如何使用 Cocos Creator 制作帧动画播放组件&am…...

基于STM32控制的双轮自平衡小车的设计

基于STM32控制的双轮自平衡小车的设计是一项涉及电子、控制理论、机械设计和编程的综合工程。以下是关于该设计的一个概述&#xff0c;包括关键组件、控制策略和示例代码。 设计概述 1. 项目背景 自平衡小车作为一种智能控制系统&#xff0c;其设计和实现涉及到多个学科领域…...

Dijkstra算法在《庆余年》中的应用:范闲的皇宫之旅

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容&#xff0c;和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣&#xff01; 推荐&#xff1a;数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航&#xff1a; LeetCode解锁100…...

HTML静态网页成品作业(HTML+CSS)——利物浦足球俱乐部介绍网页设计制作(5个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;共有5个页面。 二、作品演示 三、代码目录 四、网站代码 HTML部分代…...

mac 查看占用80端口的命令

在 Mac 上&#xff0c;如果你想查看哪个进程正在使用 80 端口&#xff0c;你可以使用 lsof 命令。这个命令非常强大&#xff0c;用于列出被进程打开或使用的文件信息。 打开你的终端&#xff0c;并输入以下命令&#xff1a; sudo lsof -i :80这里&#xff0c;-i :80 选项告诉…...

【Qt常用控件】—— 布局管理器

目录 前言 &#xff08;一&#xff09;垂直布局 &#xff08;二&#xff09;水平布局 &#xff08;三&#xff09;网格布局 &#xff08;四&#xff09;表单布局 &#xff08;五&#xff09;分组布局 &#xff08;六&#xff09;Spacer 总结 前言 之前使⽤Qt在界⾯上…...

模板中的右值引用(万能引用)、引用折叠与完美转发

模板中的右值引用&#xff08;万能引用&#xff09;、引用折叠与完美转发 文章目录 模板中的右值引用&#xff08;万能引用&#xff09;、引用折叠与完美转发一、万能引用与引用折叠1. 模板中的右值引用2. 自动类型推导(auto)与万能引用3. 引用折叠与万能引用4. lambda表达式捕…...

Nacos启动报错:[db-load-error]load jdbc.properties error

在学习Nacos中间件时&#xff0c;出现了一个错误&#xff0c;竟然启动报错&#xff01;&#xff01;&#xff01;! 这个错误第一次遇见&#xff0c;当时我感觉大体就是--数据库连接方面的错误。 可是&#xff0c;对于初学者的我来说一脸懵啊&#xff1f;&#xff1f;&#xff…...

5.23相关性分析

相关性分析是一件很自然而然的事情&#xff0c;在生活中和科学研究中&#xff0c;我们都可能会不由自主地关注两件或者多件事情之间的联系。比如性别和方向感有没有关系&#xff0c;有多大关系&#xff0c;辨别不同事物时如何说明特征的科学性&#xff08;也就是该特征和事物的…...

使用 Sonatype Nexus Repository Manager 如何安装npm.md

1. 安装与启动 Nexus2. 登录 Nexus Web UI3. 创建 npm 仓库4. &#xff08;可选&#xff09;配置 npm 代理仓库5. 创建 npm 仓库组6. 配置 npm 客户端7. 测试和使用 Sonatype Nexus Repository Manager (通常简称 Nexus) 是一个强大的二进制管理系统&#xff0c;用于存储和管理…...

console如何连接远程机器上的java程序

启动参数 -Djava.rmi.server.hostname192.168.1.10 -Dcom.sun.management.jmxremote -Dcom.sun.management.jmxremote.port12345 -Dcom.sun.management.jmxremote.sslfalse -Dcom.sun.management.jmxremote.authenticatefalse2.jdk安装目录/bin下执行 go jconsole![在这里插入…...

高稳定数显芯片防干扰抗噪数码屏驱动高亮LED驱动IC-VK16K33A/AA 最大13×3的按键扫描

产品型号&#xff1a;VK16K33A/AA 产品品牌&#xff1a;永嘉微电/VINKA 封装形式&#xff1a;SOP28/SSOP28 原厂&#xff0c;工程服务&#xff0c;技术支持&#xff01; 概述 VK16K33A/AA是一种带按键扫描接口的数码管或点阵LED驱动控制专用芯片&#xff0c;内部集成有数据…...

Redis离线安装(单机)

目录 1-环境准备1-1下载redis-4.0.11.tar.gz1-2gcc环境 2-上传解压3-编译安装(需要gcc环境)4-配置redis5-启动Redis6-开启防火墙(root)7-添加开机启动脚本8-设置权限9-设置开机启动10-测试redis服务11-检查是否安装成功12-创建redis命令软连接13-测试redis14-必要时设置防火墙 …...

[Algorithm][动态规划][路径问题][不同路径][不同路径Ⅱ][珠宝的最高价值]详细讲解

目录 1.不同路径1.题目链接2.算法原理详解3.代码实现 2.不同路径 II1.题目链接2.算法原理详解3.代码实现 3.珠宝的最高价值1.题目链接2.算法原理详解3.代码实现 1.不同路径 1.题目链接 不同路径 2.算法原理详解 思路&#xff1a; 确定状态表示 -> dp[i][j]的含义 走到dp[…...

ChatGPT移动应用收入在GPT-4o发布后迎来最大涨幅

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

汉语拼音 如何 转化成粤语拼音 的

将汉语拼音&#xff08;普通话拼音&#xff09;转化为粤语拼音涉及到对声母、韵母以及声调的对照和调整。以下是详细的转换步骤和注意事项&#xff1a; 一、转换步骤 识别普通话拼音的声母和韵母查找对应的粤语拼音声母和韵母应用粤语声调 二、声母对照表 普通话拼音粤语拼…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...

Qwen系列之Qwen3解读:最强开源模型的细节拆解

文章目录 1.1分钟快览2.模型架构2.1.Dense模型2.2.MoE模型 3.预训练阶段3.1.数据3.2.训练3.3.评估 4.后训练阶段S1: 长链思维冷启动S2: 推理强化学习S3: 思考模式融合S4: 通用强化学习 5.全家桶中的小模型训练评估评估数据集评估细节评估效果弱智评估和民间Arena 分析展望 如果…...

表单设计器拖拽对象时添加属性

背景&#xff1a;因为项目需要。自写设计器。遇到的坑在此记录 使用的拖拽组件时vuedraggable。下面放上局部示例截图。 坑1。draggable标签在拖拽时可以获取到被拖拽的对象属性定义 要使用 :clone, 而不是clone。我想应该是因为draggable标签比较特。另外在使用**:clone时要将…...

以太网PHY布局布线指南

1. 简介 对于以太网布局布线遵循以下准则很重要&#xff0c;因为这将有助于减少信号发射&#xff0c;最大程度地减少噪声&#xff0c;确保器件作用&#xff0c;最大程度地减少泄漏并提高信号质量。 2. PHY设计准则 2.1 DRC错误检查 首先检查DRC规则是否设置正确&#xff0c;然…...

大模型智能体核心技术:CoT与ReAct深度解析

**导读&#xff1a;**在当今AI技术快速发展的背景下&#xff0c;大模型的推理能力和可解释性成为业界关注的焦点。本文深入解析了两项核心技术&#xff1a;CoT&#xff08;思维链&#xff09;和ReAct&#xff08;推理与行动&#xff09;&#xff0c;这两种方法正在重新定义大模…...

World-writable config file /etc/mysql/mysql.conf.d/my.cnf is ignored

https://stackoverflow.com/questions/53741107/mysql-in-docker-on-ubuntu-warning-world-writable-config-file-is-ignored 修改权限 -> 重启mysql # 检查字符集配置 SHOW VARIABLES WHERE Variable_name IN (character_set_server, character_set_database ); --------…...

LeetCode第244题_最短单词距离II

LeetCode第244题&#xff1a;最短单词距离II 问题描述 设计一个类&#xff0c;接收一个单词数组 wordsDict&#xff0c;并实现一个方法&#xff0c;该方法能够计算两个不同单词在该数组中出现位置的最短距离。 你需要实现一个 WordDistance 类: WordDistance(String[] word…...