数据结构【树+二叉树】

news/2024/2/25 21:04:31/文章来源:https://blog.csdn.net/m0_74841364/article/details/135553360

目录

线性表和非线性表

树的概念

树的存储表示

二叉树的概念

特殊二叉树

满二叉树

完全二叉树

二叉树的性质

二叉树的存储结构

顺序存储

链式存储


本篇我们开始进入数据结构中【树】的学习。 

线性表和非线性表

  • 逻辑结构:人想象出来的
  • 物理结构:内存中实际存储的结构
  • 线性表:线性表(linear list)是n个具有相同特性的数据元素的有限序列
  • 顺序表:物理结构和逻辑结构一样
  • 链表:物理结构是逻辑结构不一样
  • 非线性表:无序序列

树的概念

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

  • 有一个特殊的结点,称为根结点,根节点没有前驱结点
  • 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
  • 因此,树是递归定义的。 

 

  • 节点的度:一个节点含有的子树的个数称为该节点的度。如上图: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)棵互不相交的树的集合称为森林。(并查集就是深林)

不难发现,数和人类的亲缘关系描述。 注意:树形结构中,子树之间不能有交集,否则就不是树形结构。是后面学习的图结构。【树=一个根+n棵子树(n>=0)】

 

树的存储表示

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

//假设树的度为6
#define N 6
struct treenode
{int val;struct treenode* childAree[N];//指针数组
};
struct Treenode
{int val;Seqlist childSL;//顺序表存储孩子
};
struct Treenode
{int val;struct Treenode* leftChild;struct Treenode* rightBrother;
};

 【遍历左孩子右兄弟】

struct TreeNode* Child = A->leftChild;
while (Childe)
{Child = Child->rightBrother;
}

二叉树的概念

 一棵二叉树是结点的一个有限集合,该集合:
1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

  •  二叉树不存在度大于2的结点
  •  二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
  • 二叉树是一个特殊的树,度最大为2

 

二叉树存在多种情况&注意:对于任意的二叉树都是由以下几种情况复合而成的:

特殊二叉树

满二叉树

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

(每一层都是满的)。

完全二叉树

完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。(前h-1层是满的,最后一层不一定满,但是从左到右必须连续)二叉树的子树有左右之分,次序不能颠倒。[2^(h-1),2^h-1]

 

二叉树的性质

二叉树的存储结构

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

顺序存储

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

链式存储

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面学到高阶数据结构如红黑树等会用到三叉链。

  • 一个节点既可能是父节点同时又可能是子节点
  • 度为2的树一定是二叉树,但是二叉树不一定是度为2的树
  • 二叉树度最大为2,并不是说二叉树的度一定为2
  • 二叉树是一棵特殊的树
  •  满二叉树是一个特殊的完全二叉树,完全二叉树不一定是满二叉树

下篇【二叉树-堆】

🙂感谢大家的阅读,若有错误和不足,欢迎指正

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

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

相关文章

css 怎么绘制一个带圆角的渐变色的边框

1&#xff0c;可以写两个样式最外面的div设置一个渐变的背景色。里面的元素使用纯色。但是宽高要比外面元素的小。可以利用里面的元素设置padding这样挡住部分渐变色。漏出来的渐变色就像边框一样。 <div class"cover-wrapper"> <div class"item-cover…

MongoDB-数据库文档操作(2)

任务描述 文档数据在 MongoDB 中的查询和删除。 相关知识 本文将教你掌握&#xff1a; 查询文档命令&#xff1b;删除文档命令。 查询文档 我们先插入文档到集合 stu1 &#xff1a; document([{ name:张小华, sex:男, age:20, phone:12356986594, hobbies:[打篮球,踢足球…

【软件测试】学习笔记-测试基础架构

这篇文章探讨什么是测试基础架构。 什么是测试基础架构&#xff1f; 测试基础架构指的是&#xff0c;执行测试的过程中用到的所有基础硬件设施以及相关的软件设施。因此&#xff0c;我们也把测试基础架构称之为广义的测试执行环境。通常来讲&#xff0c;测试基础 架构主要包括…

【PostgreSQL内核学习(二十三)—— 执行器(ExecEndPlan)】

执行器&#xff08;ExecEndPlan&#xff09; 概述ExecEndPlan 函数ExecEndNode 函数 总结 声明&#xff1a;本文的部分内容参考了他人的文章。在编写过程中&#xff0c;我们尊重他人的知识产权和学术成果&#xff0c;力求遵循合理使用原则&#xff0c;并在适用的情况下注明引用…

压力测试+接口测试(工具jmeter)

jmeter是apache公司基于java开发的一款开源压力测试工具&#xff0c;体积小&#xff0c;功能全&#xff0c;使用方便&#xff0c;是一个比较轻量级的测试工具&#xff0c;使用起来非常简单。因 为jmeter是java开发的&#xff0c;所以运行的时候必须先要安装jdk才可以。jmeter是…

opencv-4.8.0编译及使用

1 编译 opencv的编译总体来说比较简单&#xff0c;但必须记住一点&#xff1a;opencv的版本必须和opencv_contrib的版本保持一致。例如opencv使用4.8.0&#xff0c;opencv_contrib也必须使用4.8.0。 进入opencv和opencv_contrib的github页面后&#xff0c;默认看到的是git分支&…

DC电源模块与AC电源模块的对比分析

DC电源模块与AC电源模块的对比分析 BOSHIDA DC电源模块和AC电源模块是两种常见的电源模块&#xff0c;它们在供电方式、稳定性、适用范围等方面有所不同&#xff0c;下面是它们的对比分析&#xff1a; 1. 供电方式&#xff1a; DC电源模块通过直流电源供电&#xff0c;通常使用…

shiro实战

接下来我将用编码的方式&#xff0c;来演示如何使用shirojwt实现认证并下发token&#xff0c;但是没有整合到springboot中。只是shiro的API的调用 1. shirojwt 实现登录认证、获取资源的流程图 2.编码实现 &#xff08;1&#xff09;工程结构 &#xff08;2&#xff09;核心代…

msvcr110.dll缺失怎么解决,修复msvcr110.dll缺失的方法分享

首先&#xff0c;我们来了解一下msvcr110.dll是什么文件。msvcr110.dll是Microsoft Visual C 2012 Redistributable的一个组件&#xff0c;它包含了许多运行库函数&#xff0c;这些函数在编译和运行使用Visual C编写的程序时是必不可少的。简单来说&#xff0c;msvcr110.dll就是…

Unity解决Udp客户端无法接收数据的问题

Unity解决Udp客户端无法接收数据的问题 在我之前做过的项目中&#xff0c;其中不少涉及Udp客户端的项目。在这些项目中&#xff0c;一般只需要实现客户端向服务器端发送数据的功能就可以了&#xff0c;一般都不用接收服务器端发送的数据&#xff0c;但是也有同学使用了我分享的…

[C#]winform部署官方yolov8-obb旋转框检测的onnx模型

【官方框架地址】 https://github.com/ultralytics/ultralytics 【算法介绍】 Yolov8-obb&#xff08;You Only Look Once version 8 with Oriented Bounding Boxes&#xff09;是一种先进的对象检测算法&#xff0c;它在传统的Yolov3和Yolov4基础上进行了优化&#xff0c;加…

Next.js 开发指​南(GitHub 115k star​)

Next.js 是一个构建于 Node.js 之上的开源 Web 开发框架&#xff0c;它扩展了最新的 React 特性&#xff0c;集成了基于 Rust 的 JavaScript 工具&#xff0c;可以帮助你快速创建全栈 Web 应用 &#xff08;full-stack Web applications&#xff09; 。 对于有一定 React 基础…

软件测试|使用selenium进行多窗口操作

简介 在我们进行自动化测试的工作中&#xff0c;经常会点击某个元素或者链接就会自动打开一个新页面&#xff0c;需要我们转到新打开的页面去进行操作&#xff0c;这个时候我们就需要能够自动切换到新页面进行后续的操作&#xff0c;selenium同样支持这个功能&#xff0c;本文…

FineBI报表页面大屏小屏自适应显示问题

大屏正常显示 显示正常 小屏BI自适应显示 存在遮挡字体情况 小屏浏览器缩放显示 等比缩放后显示正常

【CV】使用 matplotlib 画统计图,并用 OpenCV 显示静图和动图

1. 效果 静图 动图 2.思路 准备数据使用 pyplot 画统计图图片写入流&#xff0c;流转图&#xff08;numpy&#xff09;matplotlib 颜色 RGB 转 OpenCV 颜色 BRG 4. 静图 代码过程有注释&#xff0c;很简单的实现。注意 matplotlib RGB 转 OpenCV BGR image image[:, :,…

【51单片机系列】proteus仿真单片机的串口通信

本文参考&#xff1a;https://zhuanlan.zhihu.com/p/425809292。 在proteus之外使用串口软件和单片机通信。通过在proteus设计一个单片机接收PC发送的数据&#xff0c;并将接收的数据发送出去&#xff0c;利用软件【Configure Virtual Serial Port Driver】创建一对虚拟串口&am…

网络安全技术新手入门:利用永恒之蓝获取靶机控制权限

目录 前言 一、搜索永恒之蓝可用模块 二、使用攻击模块 三、配置攻击模块 四、攻击 五、总结 前言 相关法律声明&#xff1a;《中华人民共和国网络安全法》第二十七条 任何个人和组织不得从事非法侵入他人网络、干扰他人网络正常功能、窃取网络数据等危害网络安全的活动&…

php 的数学常用函数

目录 1.常用列表 2.代码示例 1.常用列表 函数名描述输入输出abs()求绝对值数字绝对值数字ceil()进一法取整浮点数进一取整floor()舍去法求整浮点数直接舍去小数部分fmod()浮点数取余 两个浮点 数,x>y 浮点余数 pow()返回数的n次方基础数n次方乘方值round()浮点数四舍五入…

数据结构期末复习(4)串 树和二叉树

串 在数据结构中&#xff0c;串是由零个或多个字符组成的有限序列。它是一种线性数据结构&#xff0c;常用于表示和处理文本、字符串等信息。 串的特点包括&#xff1a; 顺序性&#xff1a;串中的字符按照一定的先后顺序排列&#xff0c;每个字符都有一个唯一的位置。有限性&…

关于并发十道常见面试题

面试题一&#xff1a;线程中的start和run方法有什么区别 Java中线程是通过Thread类来实现的&#xff0c;每个线程都是通过特定的Thread对象所对应的run方法来完成 start&#xff08;&#xff09;方法来启动线程&#xff0c;真正的实现多线程&#xff0c;这时无需等待run&…