二叉树的概念

文章目录

  • 二叉树
    • 一、树的概念
      • 1.树形结构
        • 1.1. 树的特点:
        • 1.2 概念:
        • 1.3 树的表示形式
      • 2.树的应用
    • 二、二叉树
      • 1.二叉数的概念
      • 2.满二叉树
      • 3.完全二叉树
      • 4.二叉树的性质
          • 练习:


二叉树


一、树的概念

1.树形结构

1.1. 树的特点:

1.根节点没有前驱节点
2.除根节点外,其余结点分成了M个互不相交的集合
3.子树的根节点有且只有一个前驱
4.树是递归定义的

在这里插入图片描述

  • 树形结构中,子树不能相交;
  • 除了根节点外,每个结点有且只有一个父结点;
  • 一颗N个结点的树,有N-1条边;
1.2 概念:

在这里插入图片描述

  • 1.结点的度:一个结点含子树的个数 ,如上图:A的度为3;
  • 2.树的度:树中,结点的度最大值 ,数的度为3 ;
  • 3.叶子结点/终端结点:度为0的结点(没有子结点)如J、F、K、L、H、I;
  • 4.父结点/双亲节点:含有子节点的结点. 如A是C的父结点;
  • 5.子结点/孩子结点:如B是A的子结点
  • 6.根结点:一棵树中,没有父结点的结点: A
  • 7.结点的层次:从根结点开始,根为第1层,根的子结点为第2层…
  • 8.树的高度/深度:树中结点的最大层次。 上图中树的高度为4;
  • 9.分支结点/非终端结点:度不为0的结点:E,G…
  • 10.兄弟结点:具有相同的父结点:E、F
  • 11.堂兄弟结点:其父结点都在同一层;F、G
  • 12.森林:多棵互不相交的的数的结合
1.3 树的表示形式

孩子兄弟表示法:
在这里插入图片描述

class Node{int val;//存储的数据Node firstChild;//第一个孩子引用Node nextBrother;//下一个兄弟引用
}

一个结点中,val存储数据
firstChild存该结点的第一个子结点
nextBrother存该结点下一个兄弟结点
没有孩子兄弟的时候为null

孩子双亲表示法

2.树的应用

文件夹结构

二、二叉树

在这里插入图片描述

1.二叉数的概念

  • 一个根节点加上它的左子树和右子树
  • 二叉树不存在度大于2的结点(一个结点只能有两个子节点)
  • 二叉树是有序树,子树的左右不能颠倒

2.满二叉树

在这里插入图片描述

1.每一层的结点都是满的,除了最后一层,每个结点都有两个子结点
2.每层的结点数都达到最大值
3.如果二叉树的层数为K,结点总数为2^k-1,则为满二叉树
4.结点为n,层数 = log2(n+1),向上取整

3.完全二叉树

在这里插入图片描述

1.从0开始依次从左往右按顺序一一对应
2.满二叉树是一种特殊的完全二叉树

4.二叉树的性质

  • 1.根结点的层数为1,则一棵非空二叉树的第i层上最多有 2^(i-1) 个结点
  • 2.根结点的二叉树的深度为1,深度为K的二叉树的最大结点数是 2^K-1
  • 3.具有n个结点的完全二叉树的深度k==log2(n+1) ,向上取整
  • 4.对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i的结点有:

父结点下标为 i : 左孩子的下标:2i+1 ; 右孩子的下标 2i+2;
子结点下标为 i : 父结点下标:(i - 1)/ 2

  • 5.对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1

也就是说:度为0的结点比度为2的结点多一个==有两个子节点的结点数=叶子结点数-1
n0=n2+1

在这里插入图片描述

练习:

在这里插入图片描述

A.n
完全二叉树结点的个数分奇数和偶数两种情况
奇数个结点,度为1的结点数为1
偶数个结点,度为1的结点数为0
联立总结点数之和的式子和 n0-1=n2

在这里插入图片描述

点击移步博客主页,欢迎光临~

偷cyk的图

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

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

相关文章

二进制搭建 Kubernetes+部署网络组件+部署CornDNS+负载均衡部署+部署Dashboard

二进制搭建 Kubernetes v1.20 k8s集群master01:20.0.0.50 kube-apiserver kube-controller-manager kube-scheduler etcd k8s集群master02:20.0.0.100k8s集群node01:20.0.0.110 kubelet kube-proxy docker etcd k8s集群node02:20.…

学习paddle-detection(paddlex的使用)

首先下载paddlex(网页)的本地软件,下载链接如下: paddlex 下载完成后进行安装 打开后选择开发者模式,开发者模式主要是和VScode进行集成 本章节主要介绍在开发者模式下可以查看和编辑的文件及其作用,关于…

【Java 进阶篇】解决Java Web应用中请求参数中文乱码问题

在Java Web应用开发中,处理请求参数时经常会遇到中文乱码的问题。当浏览器向服务器发送包含中文字符的请求参数时,如果不正确处理,可能会导致乱码问题,使得参数无法正确解析和显示。本文将详细探讨Java Web应用中请求参数中文乱码…

nginx请求时找路径问题

nginx请求时找路径问题 你是否遇到过这样的情况: 当你安装了nginx的时候,为nginx配置了如下的location,想要去访问路径下面的内容,可是总是出现404,找不到文件,这是什么原因呢,今天我们就来解…

针对element-plus,跳转jump(快速翻页)

待补充 const goToPage () > {const inputElement document.querySelector(.el-pagination .el-input__inner);console.log(inputElement, inputElement); } 打印之后可以看到分页跳转的数字输入框,是有进行处理的,max"102",是我自己的…

什么是 Node.js

目标 什么是 Node.js,有什么用,为何能独立执行 JS 代码,演示安装和执行 JS 文件内代码 讲解 Node.js 是一个独立的 JavaScript 运行环境,能独立执行 JS 代码,因为这个特点,它可以用来编写服务器后端的应用…

智能矩阵,引领商业新纪元!拓世方案:打破线上线下界限,开启无限营销可能!

在科技赋能商业大潮中,一切行业都在经历巨大变革,传统的营销策略被彻底改变,催生着无数企业去打造横跨线上线下、多维度、全方位的矩阵营销帝国。无数的成功案例已经告诉我们,营销不再只是宣传,而是建立品牌与消费者之…

基于物联网云平台的分布式光伏监控系统的设计与实现

贾丽丽 安科瑞电气股份有限公司 上海嘉定 201801 摘要:针对国内光伏发电监控系统的研究现状,文中提出了基于云平台的光伏发电监控体系。构建基于B/S架构的数据实时采集与推送,以SSH(strutsspringhibernate)作为Web开发框架,开发基…

TSINGSEE青犀基于AI视频识别技术的平安校园安防视频监控方案

一、背景需求 因学校频频出治安事件,所以必须要加强学校的安防工作,目前来看,大部分校园都建设了视频监控来预防保障校园安全。但是传统的视频监控系统,主要通过设备来录像以及人员时时监控来进行。这种监管方式效率十分低下&…

STM32F103的中断

文章目录 STM32F103的NVICSTM32F103 的中断优先级分组 STM32F103的NVIC CM3 内核支持 256 个中断,其中包含了 16 个内核中断和 240 个外部中断,并且具有 256级的可编程中断设置。 CM3中每个中断通道都具备自己的8位中断优先级控制字节, 但ST…

SOLIDWORKS PDM 2024数据管理5大新功能

1. 改进的视觉内容 • 通过装配体可视化功能,在 SOLIDWORKS 中以图形方式查看零部件数据,如工作流程状态。• 使用特定图标迅速识别焊件切割清单零部件。 优点:重要数据和系统信息一目了然。 2.增强的数据保护和跟踪功能 •保护“包含”和…

conda 实践

1. 环境部署 1.1. 下载 anaconda 安装包 下面这个网址查找自己需要的版本 https://repo.anaconda.com/archive/ 或者手动下载。 wget https://repo.anaconda.com/archive/Anaconda3-5.3.0-Linux-x86_64.sh 1.2. 执行安装程序 #安装依赖: sudo yum install bzip2…

Unity地面交互效果——1、局部UV采样和混合轨迹

大家好,我是阿赵。   这期开始,打算介绍一下地面交互的一些做法。 比如: Unity引擎制作沙地实时凹陷网格的脚印效果 或者: Unity引擎制作雪地效果 这些效果的实现,需要基于一些基础的知识。所以这一篇先介绍一下简单…

传奇服务器配置如何搭建

传奇服务器在中国页游发展中作为一个经典制作吸引了很多玩家的喜欢,很多人也想搭建一个属于自己团队的传奇游戏服务器,今天就让小编来讲一讲该如何搭建吧! 首先是硬件配置,传奇游戏的服务器需要较高的硬件配置,选择双路…

CSS色域、色彩空间、CSS Color 4新标准 | 京东云技术团队

引言 近期,三大主流浏览器引擎均发布最新版本,支持W3C的CSS Color 4标准,包含新的取色方法color()和相应语法,可展示更多的色域及色彩空间,这意味着web端能展示更丰富更高清的色彩。虽然目前只有最新版本的现代浏览器…

同一个页面同一区域两个el-table在v-if下样式重叠问题

🍉正常情况下在radio切换时两个表格的样式应如下 🍉实际上用v-if显示时会出现以下问题(本该属于时间段相同模块的表格却出现在时间段自定义的表格中) 🍉解决方案: 🍃一、将v-if替换成v-show(…

【C++】STL容器——list类的使用指南(含代码演示)(13)

前言 大家好吖,欢迎来到 YY 滴C系列 ,热烈欢迎! 本章主要内容面向接触过C的老铁 主要内容含: 欢迎订阅 YY滴C专栏!更多干货持续更新!以下是传送门! 目录 一、list 类——基本介绍二、list 类——…

基于springboot,vue校园社团管理系统

开发工具:IDEA 服务器:Tomcat9.0, jdk1.8 项目构建:maven 数据库:mysql5.7 系统分前后台,项目采用前后端分离 前端技术:vueelementUI 服务端技术:springbootmybatis-plus 本系…

剑指JUC原理-5.synchronized底层原理

Java对象头 以32位虚拟机为例: 普通对象 在Java虚拟机中,每个对象都有一个对象头(Object Header),其中包含了一些用于管理对象的元数据信息。对象头通常由两部分组成:mark word(标记字&#x…

JAVA实现校园失物招领管理系统 开源

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、研究内容2.1 招领管理模块2.2 寻物管理模块2.3 系统公告模块2.4 感谢留言模块 三、界面展示3.1 登录注册3.2 招领模块3.3 寻物模块3.4 公告模块3.5 感谢留言模块3.6 系统基础模块 四、免责说明 一、摘要 1.1 项目介绍 基于VueSpri…