数据结构---二叉树

二叉树的概念及结构

1.概念

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

从上图可以看出:
  1. 二叉树不存在度大于2的结点
  2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

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

2.现实中的二叉树

3.特殊的二叉树

  1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是2^k-1,则它就是满二叉树
    如果一个树是满二叉树,结点总数是N,那它的高度h=log2(N+1)

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

    前h-1层是满的,最后一层不一定满,但是最后一层从左到右都是连续的

4.二叉树的性质

  1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1)个结点.
  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数2^h-1
  3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0=n2+1
  4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度h= log2(n+1). (long2(n+1)是log以2为底,n+1为对数)
  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
1. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
2. 若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
3. 若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子

5.二叉树的存储结构

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

1. 顺序存储

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

只有满二叉树或者完全二叉树才适合这种存储

父子节点间下标有一个规律关系:

  • leftchild = parent*2+1;
  • rightchild = parent*2+2;
  • parent = (child-1)/2;

2. 链式存储

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

 

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

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

相关文章

某60物联网安全之IoT漏洞利用实操2学习记录

物联网安全 文章目录 物联网安全IoT漏洞利用实操2&#xff08;内存破坏漏洞&#xff09;实验目的实验环境实验工具实验原理实验内容实验步骤ARM ROP构造与调试MIPS栈溢出漏洞逆向分析 IoT漏洞利用实操2&#xff08;内存破坏漏洞&#xff09; 实验目的 学会ARM栈溢出漏洞的原理…

Unity C++交互

一、设置Dll输出。 两种方式&#xff1a; 第一&#xff1a;直接创建动态链接库工程第二&#xff1a;创建的是可执行程序&#xff0c;在visual studio&#xff0c;右键项目->属性(由exe改成dll) 二、生成Dll 根据选项Release或Debug&#xff0c;运行完上面的生成解决方案后…

FPGA设计时序约束十、others类约束之Set_Disable_Timing

目录 一、序言 二、Set Disable Timing 2.1 基本概念 2.2 设置界面 2.3 命令语法 2.4 命令示例 三、工程示例 四、参考资料 一、序言 在Vivado的时序约束窗口中&#xff0c;存在一类特殊的约束&#xff0c;划分在others目录下&#xff0c;可用于设置忽略或修改默认的时…

7.浮点数转为整数【2023.11.29】

1.问题描述 给出一个浮点数&#xff0c;请将这个浮点数转换成整数。 2.解决思路 输入一个浮点数。 输出程序将浮点数转换为整数并输出。 3.代码实现 numfloat(input("请输入一个浮点数")) num1int(num) print(num1)4.运行结果

智能优化算法应用:基于萤火虫算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于萤火虫算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于萤火虫算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.萤火虫算法4.实验参数设定5.算法结果6.参考文献7.…

机关单位档案分类及整理方法

机关单位档案主要包含文书档案、干部职工档案&#xff08;人事档案&#xff09;、会计档案、科技档案&#xff08;科学研究、基本建设、设备仪器、产品&#xff09;、诉讼档案、音像档案、照片档案、电子档案等等&#xff0c;这其中&#xff0c;不同种类&#xff0c;不同载体的…

技术前沿丨Teranode如何实现无限扩容

​​发表时间&#xff1a;2023年9月15日 BSV区块链协会的技术团队目前正在努力开发Teranode&#xff0c;这是一款比特币节点软件&#xff0c;其最终目标是实现比特币的无限扩容。然而&#xff0c;正如BSV区块链协会网络基础设施负责人Jake Jones在2023年6月举行的伦敦区块链大会…

Java---抽象类讲解

文章目录 1. 抽象类概述2. 抽象类特点3. 抽象类的成员特点4. 抽象类猫狗应用 1. 抽象类概述 在Java中&#xff0c;一个没有方法体的方法应该定义为抽象方法&#xff1b;而类中如果有抽象方法&#xff0c;该类必须定义为抽象类。 2. 抽象类特点 1. 抽象类和抽象方法必须使用abst…

Redis-Redis 高级数据结构 HyperLogLog与事务

Redis 高级数据结构 HyperLogLog HyperLogLog(Hyper [ˈhaɪpə(r)] ) 并不是一种新的数据结构 ( 实际类型为字符串类 型) &#xff0c;而是一种基数算法 , 通过 HyperLogLog 可以利用极小的内存空间完成独立总数的统计&#xff0c;数据集可以是 IP 、 Email 、 ID 等。 如…

科研学习|论文解读——Deep learning for anomaly detection in log data: a survey

摘要 自动日志文件分析能够及早发现系统故障等相关事件。特别是&#xff0c;自学习异常检测技术能够捕捉日志数据中的模式&#xff0c;然后向系统操作员报告意外的日志发生&#xff0c;而无需提前提供或手动建模异常场景。最近&#xff0c;越来越多的利用深度学习方法来实现此目…

损失函数与反向传播

计算l1loss mseloss import torch from torch.nn import L1Loss from torch import nninputs torch.tensor([1,2,3],dtypetorch.float32) targets torch.tensor([1,2,5],dtypetorch.float32)inputs torch.reshape(inputs,(1,1,1,3)) targets torch.reshape(targets,(1,1,1…

蓝桥杯第199题 扫地机器人 暴力优化 二分法 简单题 C++

题目 扫地机器人 - 蓝桥云课 (lanqiao.cn)https://www.lanqiao.cn/problems/199/learning/?page1&first_category_id1&name%E6%89%AB%E5%9C%B0%E6%9C%BA%E5%99%A8%E4%BA%BA 思路和解题方法 首先&#xff0c;通过cin语句输入了终点位置n和障碍物数量k。使用一个数组a来…

element-plus el-dialog 弹窗隐藏遮罩并且可以控制弹窗后的元素、点击、滚动、其他事件操作等

场景 el-dialog 隐藏遮罩并且可以控制弹窗后的元素、点击、滚动、其他事件操作&#xff0c;比如一个弹窗打开了&#xff0c;我要能控制弹窗后面的滚动、点击等等一系列事件。 修改方法 首先我们需要隐藏弹窗遮罩 :modal"false"&#xff0c;并且给 el-dialog 弹窗…

C语言基础--#if与#endif

目录 一、C语言中的 #if()和 #end if 用法 1. #if 表达式 程序段 #endif 形式 2. #ifdef标示符 标识符 #endif 形式 3. #if 0/ #if 1 #endif 形式 4. \可用于一行的结尾&#xff0c;表示本行与下一行连接起来 二、xTaskCreate函数 三、指针相关…

Java容器合集

目录 浅谈 Array数组 初始化(动与静) 动态初始化 静态初始化 CRUD 增 查 索引取值 遍历 改 删 走进底层 栈与堆 一个数组的诞生 多数组 避坑指南 索引越界 空指针异常 小试牛刀 Collection List部落 介绍和特点 方法 ArrayList 介绍 方法 遍历 Li…

docker搭建node环境开发服务器

docker搭建node环境开发服务器 本文章是我自己搭建node环境开发服务器的过程记录&#xff0c;不一定完全适用所有人。根据个人情况&#xff0c;按需取用。 命名项目路径 为了方便cd到项目路径&#xff0c;将项目路径重命名&#xff0c;方便输入。 vim /etc/profile # 修改p…

创建Asp.net MVC项目Ajax实现视图页面数据与后端Json传值显示

简述回顾 继上篇文章创建的mvc传值这里说明一下Json传值。在mvc框架中&#xff0c;不可避免地会遇到前台传值到后台&#xff0c;前台接收后台的值的情况&#xff08;前台指view&#xff0c;后台指controller&#xff09;&#xff0c;有时只需要从控制器中返回一个处理的结果&a…

Steps步骤条(antd-design组件库)简单用法

1.Steps步骤条 引导用户按照流程完成任务的导航条。 2.何时使用 当任务复杂或者存在先后关系时&#xff0c;将其分解成一系列步骤&#xff0c;从而简化任务。 组件代码来自&#xff1a; 步骤条 Steps - Ant Design 3.本地验证前的准备 参考文章【react项目antd组件-demo:hello-…

用bat制作图片马——一句话木马

效果图 代码 ECHO OFF TITLE PtoR MODE con COLS55 LINES25 color 0A:main cls echo.当前时间&#xff1a;%date% %time% echo.欢迎使用图片马制作工具 echo.请确保图片和php在同一路径下 echo.echo 请将图像文件拖放到此窗口并按 Enter&#xff1a; set /p "imagefile&q…

项目demo —— GPT 聊天机器人

本文介绍我的开源项目 TelegramChatBot&#xff0c;这是一个基于 OpenAI GPT API 开发的 telegram 机器人&#xff0c;具有多模态交互能力&#xff0c;求 star&#xff01;感谢大家&#xff01;在 telegram jokerController_bot 立即体验&#xff01;欢迎对 GPT 应用开发或对 t…