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

【数据结构】树和二叉树的概念及结构(一)

目录

一,树的概念及结构

        1,树的定义

        2,树结点的分类及关系

        3,树的表示

二,二叉树的概念及结构

        1,二叉树的定义

        2,特殊的二叉树

        3,二叉树的性质

        4,二叉树的存储结构

1,顺序存储

2,链式储存


一,树的概念及结构

        1,树的定义

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

树(Tree)是n(n>=0)个结点的有限集;

n=0时称为空树;

在任意一颗非空树中:

1,有且仅有一个特定的称为根(Root)的结点;

2,当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,......,Tm,其中每一个集合本身又是一棵树,并且称为跟的子树(SubTree);

如下图所示:

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

        2,树结点的分类及关系

结点的度:一个结点含有的子树的个数称为该结点的度; 如上图:A的为4

叶结点或终端结点:度为0的结点称为叶结点; 如上图:K,G,L,M,N...等结点为叶结点

非终端结点或分支结点:度不为0的结点; 如上图:B,C,E...等结点为分支结点

双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:A是B的父节点

孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结点

兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点

树的度:一棵树中,最大的结点的度称为树的度; 如上图:树的度为4

结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推

树的高度或深度:树中结点的最大层次; 如上图:树的高度为4

堂兄弟结点:双亲在同一层的结点互为堂兄弟;如上图:H、I互为堂兄弟结点

结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先,C是G,H的祖先

子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙,G,H是C的子孙

森林:由m(m>0)棵互不相交的树的集合称为森林

        3,树的表示

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

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

图解:

二,二叉树的概念及结构

        1,二叉树的定义

二叉树(Binary Tree)是n(n>=0) 个结点的有限集合;

该集合或者为空集(称为空二叉树);

或者由一个根结点和两颗互不相交的,分别为根结点的左子树和右子树的二叉树组成;

 图示:

由上图可以看出:

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

2,二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

二叉树具有以下五种基本形态:

        2,特殊的二叉树

1,斜树

所有的结点都只有左子树的二叉树叫左斜树;

所有的结点都只有右子树的二叉树叫右斜树;

斜树图示:

2,满二叉树

一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是 说,如果一个二叉树的层数为K,且结点总数是2^k-1 ,则它就是满二叉树

3,完全二叉树

完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

        3,二叉树的性质

1,若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1)个结点

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

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

4,若规定根结点的层数为1,具有n个结点的满二叉树的深度,h=log2(n+1) 

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

1,若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点

2,若2i+1<n,左孩子序号:2i+1

3,若2i+1>n,右孩子序号:2i+2

        

        4,二叉树的存储结构

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

1,顺序存储

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

二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

2,链式储存

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系;

通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址;

链式结构又分为二叉链和三叉链

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向当前节点的双亲struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
};

第一阶段就到这里了,带大家先了解一下树和二叉树的原理;

后面博主会陆续更新;

如有不足之处欢迎来补充交流!

完结。。。


相关文章:

【数据结构】树和二叉树的概念及结构(一)

目录 一&#xff0c;树的概念及结构 1&#xff0c;树的定义 2&#xff0c;树结点的分类及关系 3&#xff0c;树的表示 二&#xff0c;二叉树的概念及结构 1&#xff0c;二叉树的定义 2&#xff0c;特殊的二叉树 3&#xff0c;二叉树的性质 4&#xff0c;二叉树的存储结构 1&…...

第三章 USB应用笔记之USB鼠标(以STM32 hal库为例)

第三章 USB应用笔记之USB鼠标&#xff08;以STM32 hal库为例&#xff09; 提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 第三章 USB应用笔记之USB鼠标&#xff08;以STM32 hal库为例&#xff09;前言一、STM32 U…...

微服务01-基本介绍+注册中心EureKa

基本介绍 服务集群&#xff1a;一个请求由多个服务完成&#xff0c;服务接口暴露&#xff0c;以便于相互调用&#xff1b; 注册中心&#xff1a;每个服务的状态&#xff0c;需要进行维护&#xff0c;我们可以在注册中心进行监控维护服务&#xff1b; 配置中心&#xff1a;这些…...

【ES6】JavaScript中的异步编程:async和await

在JavaScript中&#xff0c;异步编程是一种处理长时间运行的操作的方法&#xff0c;这些操作包括读取文件、网络请求或处理大数据等。在传统的回调函数中&#xff0c;代码按照顺序执行&#xff0c;一旦遇到长时间运行的操作&#xff0c;就需要回调函数来处理结果。这使得代码变…...

51单片机热水器温度控制系统仿真设计( proteus仿真+程序+原理图+报告+讲解视频)

51单片机热水器温度控制系统仿真设计 1.主要功能&#xff1a;2.仿真3. 程序代码4. 原理图5. 设计报告6. 设计资料内容清单 &&下载链接 51单片机热水器温度控制系统仿真设计( proteus仿真程序原理图报告讲解视频&#xff09; 仿真图proteus7.8及以上 程序编译器&#x…...

Spring Boot 配置文件加密

方式一&#xff1a;Spring Cloud Config 一、建立config server 1. build.gradle 文件中添加&#xff1a; plugins {id javaid org.springframework.boot version 2.7.0id io.spring.dependency-management version 1.0.11.RELEASE }ext {set(springCloudVersion, "202…...

【树形权限】树形列表权限互斥选择、el-tree设置禁用等等

需求&#xff1a;按照权限管理配置的数据权限树展开&#xff1b;点击查看按钮后进入其他指定机构选择弹窗为一树形结构 本文章对项目中出现得关键点进行总结。 一、实现如上树形列表 在 element 官方表格示例中&#xff0c;实现树形表格列表数据渲染&#xff0c;非常简单。只…...

ubuntu 22.04安装cuda、cudnn、conda、pytorch

1、cuda 视频连接 https://www.bilibili.com/video/BV1bW4y197Mo/?spm_id_from333.999.0.0&vd_source3b42b36e44d271f58e90f86679d77db7cuda 11.8 https://developer.nvidia.com/cuda-toolkit-archive点击进入 https://developer.nvidia.com/cuda-11-8-0-download-arc…...

2023 最新前端面试题 (HTML 篇)

1. src 和 href 的区别 src 用于替换当前元素&#xff08;引入&#xff09;&#xff0c;href 用于在当前文档和引用资源之间确立联系&#xff08;引用&#xff09; &#xff08;1&#xff09;src&#xff08;source&#xff09; 指向外部资源的位置&#xff0c;指向的内容将会嵌…...

华为云银河麒麟V10安装libmcrypt

本次安装是在华为云上执行。cpu是鲲鹏&#xff0c;操作系统是银河麒麟V10. 先下载安装包&#xff1a; wget http://downloads.sourceforge.net/mcrypt/libmcrypt-2.5.8.tar.gz 解包&#xff0c;进入目录中。 执行如下命令&#xff1a; ./configure make make install 执…...

智慧导览|智能导游系统|AR景区导览系统|景区电子导览

随着文旅市场的加快复苏&#xff0c;以及元宇宙、VR、AR、虚拟数字人等新兴技术的快速发展&#xff0c;文旅行业也正在加快数字化转型的步伐&#xff0c;向智慧景区建设迈进。为满足不同年龄段游客的游览需要&#xff0c;提升旅游服务体验&#xff0c;越来越多的旅游景区、博物…...

【Docker】Docker基本使用介绍

Docker是一个开源的应用容器引擎&#xff0c;让开发者可以打包他们的应用以及依赖包到一个可移植的容器中&#xff0c;然后发布到任何流行的Linux机器上&#xff0c;也可以实现虚拟化。 一、安装Docker 首先&#xff0c;你需要从官方网站上下载Docker的安装包&#xff0c;并按…...

Linux命令200例:man用于显示和阅读关于Linux内置命令的使用说明

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;CSDN领军人物&#xff0c;全栈领域优质创作者✌。CSDN专家博主&#xff0c;阿里云社区专家博主&#xff0c;2023年6月csdn上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师&#xff0…...

idea 无法识别maven的解决

问题描述 从git拉取代码或者修改文件夹以后&#xff0c;整个项目所有依赖爆红无法通过修改或者重新加载maven解决版本为idea 2021 问题定位 maven的版本太高&#xff0c;而idea的般本太低&#xff0c;导致识别的时候稳定性差 解决 使用idea原生的maven版本 选择已捆绑的m…...

String底层函数的实现方式

一、常见的String封装函数 1. strcpy函数的实现 char *strcpy(char *dest, const char *src) {char *tmp dest;while ((*dest *src) ! \0)/* nothing */;return tmp; } 2. strncpy函数的实现 char *strncpy(char *dest, const char *src, size_t count) {char *tmp dest…...

uniapp实现微信小程序全局可分享功能

uniapp实现微信小程序全局【发送给朋友】、【分享到朋友圈】、【复制链接】 主要使用 Vue.js 的 全局混入 1.创建一个全局分享的js文件。示例文件路径为&#xff1a;./utils/shareWx.js &#xff0c;在该文件中定义全局分享的内容&#xff1a; export default {data() {retur…...

大数据成为市场营销利器 ,促进金融贷款企业获客精准化

随着大数据技术的不断普及&#xff0c;中国对尖端技术和云计算技术的投资大幅增加。大数据、云计算技术、物联网等一系列新一代信息技术也加速完善。 目前&#xff0c;大数据技术也非常成熟&#xff0c;大数据的应用领域也多种多样。大数据的重要方面“运营商大数据”已经被政…...

Acwing 3472. 八皇后

题目如下&#xff1a; 会下国际象棋的人都很清楚&#xff1a;皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。 如何将 88 个皇后放在棋盘上&#xff08;有 88 个方格&#xff09;&#xff0c;使它们谁也不能被吃掉&#xff01; 这就是著名的八皇后问题。 对于某个满足要…...

Word转为PDF后图片模糊怎么办?Word转为PDF的技巧介绍

将Word文档转为PDF是我们日常办公和文档处理中常见的需求。PDF格式的优势在于跨平台兼容性、保留原始格式、文档保护以及方便共享和分发等方面。本文将探讨Word转为PDF后图片模糊怎么办?Word转为PDF的技巧有哪些?通过这些问题的答案&#xff0c;可以帮助您更好的利用文件转换…...

【django开发手册】详解drf filter中DjangoFilterBackend,SearchFilter,OrderingFilter使用方式

&#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是Zeeland&#xff0c;开源建设者与全栈领域优质创作者。&#x1f4dd; CSDN主页&#xff1a;Zeeland&#x1f525;&#x1f4e3; 我的博客&#xff1a;Zeeland&#x1f4da; Github主页: Undertone0809 (Zeeland)&…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

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

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

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...