二叉树(完全二叉树、满二叉树)

树的概念及结构

树的概念

树是一种 非线性 的数据结构,它是由 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 )棵互不相交的树的集合称为森林;

树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了, 既然保存值域,也要保存结点和结点之间 的关系 ,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法
typedef int DataType;
struct Node
{
 struct Node* firstChild1; // 第一个孩子结点
 struct Node* pNextBrother; // 指向其下一个兄弟结点
 DataType data; // 结点中的数据域
};

树在实际中的应用(表示文件系统的目录树结构)

 

二叉树的概念及结构

二叉树的概念

二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树 ),或者由一个根节点和两个互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

由上图可以看出二叉树的特点
1. 二叉树不存在度大于 2 的结点
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
注意:对于任意的二叉树都是由以下几种情况复合而成的:

自然界中的二叉树

特殊的二叉树

1. 满二叉树 :一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是 说,如果一个二叉树的层数为K ,且结点总数是2^k-1,则它就是满二叉树。
2. 完全二叉树 :完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为 K 的,有n 个结点的二叉树,当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 n 的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

 

 二叉树的性质

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

二叉树的存储结构

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

顺序存储

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

链式存储

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

 

 

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

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

相关文章

Linux 秋招必知必会(四、信号、高级 I/O)

八、信号 57. 信号的基本特征 定义&#xff1a;信号是事件发生时对进程的通知机制&#xff0c;也可以把它称为软件中断信号处理方式 忽略信号 大多数信号都可以使用这种方式进行处理&#xff0c;但 SIGKILL 和 SIGSTOP 绝对不能被忽略如果忽略某些由硬件异常产生的信号&#…

lv_micropython to download and building

想要在ESP32-C3使用Micropython开发GUI&#xff0c;所以需要编译lv_micropython&#xff0c;当前github上的版本是9.1.0。 一、开发环境 因为编译lv_micropython需要在linux系统下&#xff0c;但是我的电脑是windows系统&#xff0c;所以我在windows系统上安装了VMware虚拟机&…

【matlab非线性规划工具箱安装1 SeDuMi 1.3工具箱】

【matlab非线性规划工具箱安装1 SeDuMi 1.3工具箱】 该博客是非线性手眼标定代码中所依赖的matlab工具箱的安装内容&#xff0c;除了进行手眼标定以外&#xff0c;该工具箱还可以用于其他的非线性规划问题 手眼标定传送门&#xff1a; 【从零开始进行高精度手眼标定 eye in …

Steam平台游戏发行流程

Steam平台游戏发行流程 大家好我是艾西&#xff0c;一个做服务器租用的网络架构师也是游戏热爱者&#xff0c;经常在steam平台玩各种游戏享受快乐生活。去年幻兽帕鲁以及雾锁王国在年底横空出世&#xff0c;幻兽帕鲁更是在短短一星期取得了非常好的成绩&#xff0c;那么作为游戏…

计算机网络——CSMA/CD协议以及相关习题

目录 前言 引言 CSMA/CD协议 CSMA与CSMA/CD的区别 CSMA/CD流程 前言 本博客是博主用于复习计算机网络的博客&#xff0c;如果疏忽出现错误&#xff0c;还望各位指正。 引言 最早的以太网&#xff0c;许多计算机都连接在一根总线上工作——广播通信方式。 总线的特点想…

JavaScript教程(十二)--- 使用‘类’

使用类 JavaScript 是一个基于原型的语言——一个对象的行为取决于它自身的属性及其原型的属性。对类来说&#xff0c;相较于与其他面向对象的语言&#xff0c;譬如 Java&#xff0c;创建对象的多层级结构及其属性的继承关系需要更多的代码行。本节&#xff0c;我们将展示如何…

windows搭建ftp服务器

安装iis 点击安装即可,搜索iis打开 创建ftp服务器 身份验证&#xff1a;只勾选匿名&#xff0c;不勾选基本&#xff0c;网上的很多教程会添加基本&#xff0c;导致的问题会出现浏览提需要输入账号密码的情况&#xff0c;这里为了方便大家更直观的感受FTP建立的过程&#xff0…

新手做抖店这个操作赶快停止!不听“废店”只是早晚的事!

哈喽~我是电商月月 互联网的发展&#xff0c;做什么事情都是公开透明的&#xff0c;做抖音小店也是 大家都会在网上搜索教程&#xff0c;技巧&#xff0c;但最终还是有好多人都失败了 那是因为这些流程技巧不正确吗&#xff1f;其实并不是&#xff0c;很多小技巧都是有用的&…

CTF-遗留的压缩包

题目描述&#xff1a;小蓝同学给你发来了他自己开发的网站链接&#xff0c;他说他故意留下了一个压缩包文件&#xff0c;里面有网站的源代码&#xff0c;他想考验一下你的网络安全技能。 下发容器&#xff0c;访问链接&#xff0c;发现都是无关内容 联想到标题说有遗留的压缩…

数模 线性规划模型理论与实践

线性规划模型理论与实践 1.1 线性规划问题 在人们的生产实践中&#xff0c;经常会遇到如何利用现有资源来安排生产&#xff0c;以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支一数学规划&#xff0c;而线性规划(Linear Programming 简记LP)则是数学规划的一个…

openjudge_2.5基本算法之搜索_166:The Castle

题目 166:The Castle 总时间限制: 1000ms 内存限制: 65536kB 描述 Figure 1 shows the map of a castle.Write a program that calculates how many rooms the castle hashow big the largest room is The castle is divided into m * n (m<50, n<50) square modules.…

Linux 内核学习(1) --- 时钟子系统

标题 时钟系统说明时钟树Clock Provider时钟通用数据结构clock_device 的注册clock_provider DTS配置和注册clock consumer时钟系统总结 时钟系统说明 时钟就是 SoC 中的脉搏&#xff0c;由它来控制各个部件按各自的节奏跳动。比如&#xff0c;CPU主频设置&#xff0c;串口的波…

切面条(蓝桥杯)

目录 题目 分析 代码实现 题目 一根高筋拉面&#xff0c;中间切一刀&#xff0c;可以得到2根面条。 如果先对折1次&#xff0c;中间切一刀&#xff0c;可以得到3根面条。 如果连续对折2次&#xff0c;中间切一刀&#xff0c;可以得到5根面条。 那么&#xff0c;连续对折1…

【报名指南】2023-2024学年AILD劳动技能大赛初赛报名流程

温馨提示&#xff1a; 1.AILD劳动技能大赛免费报名参赛。报名网址&#xff1a;aild.org.cn 2.报名时间即日起至5月31日。&#xff08;上海赛区线下挑战项目4月25日报名截止&#xff0c;线上挑战项目5月31日报名截止&#xff09;。 3.指导教师只能为行政备案学校的在职教师。…

C语言 数据输入输出

本文 我们来说 数据的输入与输出 及数据的运算 在程序的运算工程中 往往需要输入一些数据 而程序的运算 所得到的运算结果又需要输出给用户 因此 数据的输入与输出 就显得非常重要 在C语言中 不提供专门的输入输出语句 所有的输入输出 都是通过对标准库的调用 来实现的 一般 …

itop4412内核编译_编译自定义函数到内核

我的itop4412开发板是半路捡的&#xff0c;所以没办法加他们的售后群&#xff0c;遇到的问题只好一点点记录吧 内核驱动编译 在日常工作过程中&#xff0c;编写内核程序可能机会不多&#xff0c;但是将厂商提供的内核源码编译到固件中&#xff0c;这个技能还是必须掌握的。 i…

认识异常(1)

❤️❤️前言~&#x1f973;&#x1f389;&#x1f389;&#x1f389; hellohello~&#xff0c;大家好&#x1f495;&#x1f495;&#xff0c;这里是E绵绵呀✋✋ &#xff0c;如果觉得这篇文章还不错的话还请点赞❤️❤️收藏&#x1f49e; &#x1f49e; 关注&#x1f4a5;&a…

系统架构最佳实践 -- 一般优惠券平台系统架构设计

优惠券是商城的一种基础的营销工具&#xff0c;在目前c端用户对于电子优惠券已经非常熟悉的情况下&#xff0c;一般自营商城的营销活动系统&#xff0c;都是从优惠券开始搭建。 一、名词定义 基于个人理解&#xff0c;为方便表述&#xff0c;首先对可能产生歧义的名词进行如下…

十九.案例演示---天猫订单分析

目录 1.数据预处理 2.对订单状况进行分析 3.不同省份订单数详情 4.省份地图绘制 5.不同星期&#xff0c;订单分布 6.订单金额与订单数量 本次案例演示数据条数为:28010 import pandas as pd from pyecharts import options as optsdf_data pd.read_excel(../data/天猫订单…

【笔记】探索生成范式:大型语言模型在信息提取中的作用

探索生成范式&#xff1a;大型语言模型在信息提取中的作用 摘要介绍 &#x1f308;你好呀&#xff01;我是 是Yu欸 &#x1f30c; 2024每日百字篆刻时光&#xff0c;感谢你的陪伴与支持 ~ &#x1f680; 欢迎一起踏上探险之旅&#xff0c;挖掘无限可能&#xff0c;共同成长&am…