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

第五章 树与二叉树 二、二叉树的定义和常考考点

一、定义

二叉树可以用以下方式详细定义:

  • 二叉树是由节点构成的树形结构,每个节点最多可以有两个子节点。
  • 每个节点有以下几个属性:
    • 值:存储该节点的数据。
    • 左子节点:有一个左子节点,如果没有则为空。
    • 右子节点:有一个右子节点,如果没有则为空。
    • 父节点:有一个父节点,如果没有则为空(除根节点外)。
  • 根节点:二叉树的顶部节点,没有父节点。
  • 叶子节点:没有子节点的节点,也称为终端节点。
  • 子树:以某个节点作为根节点的二叉树称为它的子树。
  • 遍历:二叉树的节点遍历可以分为前序遍历、中序遍历和后序遍历,还有层次遍历。

注意:二叉树中的节点数量可以为0,1或多个,空的二叉树也是一棵有效的二叉树。

二、几种特殊的二叉树

1、满二叉树,一个高度为h含有2^h-1个结点的二叉树

特点:

1.只有最后一层有叶子结点。

2.不存在度为1的结点。

3.按层序从1开始编号,结点i的左孩子为2i,右孩子为2i+1,父结点为\frac{i}{2}

 2、完全二叉树,与同高的满二叉树的子节点编号一致

此图的4层的编号与上图的第4层一一对应,称之为完全二叉树。

特点:

1.只有最后两层有叶子结点。

2.最多存在一个度为1的结点。

3.按层序从1开始编号,结点i的左孩子为2i,右孩子为2i+1,父结点为\frac{i}{2}

4.i<=\frac{i}{2}为分支结点,i>=\frac{i}{2}为叶子节点。

 3.二叉排序树

一棵二叉树或者是空二叉树,或者是具有如下性质的二叉树:

左子树上所有结点的关键字均小于根结点的关键字;
右子树上所有结点的关键字均大于根结点的关键字。

左子树和右子树又各是一棵二叉排序树。

 4.平衡二叉树,树上任一结点的左子树和右子树的深度之差不超过1

 三、考点

常见考点1:

设非空二叉树中度为0、1和2的结点个数分别为n0、n1,和n2,则n0= n2+1

★★★★★(叶子结点比二分支结点多一个)

常见考点2:

二叉树第i层至多有2^{i-1}个结点( i≥1)
m叉树第i层至多有m^{i-1}个结点(( i≥1)

常见考点3:

高度为h的二叉树至多有2^h-1个结点(满二叉树)

常见考点4:

具有n个(n>0)结点的完全二叉树的高度h为\log_{2}(n+1)(\log_{2}n)+1

常见考点5:

 

 

相关文章:

第五章 树与二叉树 二、二叉树的定义和常考考点

一、定义 二叉树可以用以下方式详细定义&#xff1a; 二叉树是由节点构成的树形结构&#xff0c;每个节点最多可以有两个子节点。每个节点有以下几个属性&#xff1a; 值&#xff1a;存储该节点的数据。左子节点&#xff1a;有一个左子节点&#xff0c;如果没有则为空。右子节…...

算法笔记/USACO Guide GOLD金组DP 1. Introduction to DP

USACO Guide中金组的内容分为一下六个章节 DP数学图论数据结构树一些附加主题 今天学习DP&#xff0c;以下内容&#xff1a; 初入DP背包DP图表中的路线最长递增序列状态压缩DP区间DP数位DP 初入DP Dynamic Programming (DP) is an important algorithmic technique in Comp…...

天锐绿盾安全U盘系统

安全U盘系统 01 简介 天锐绿盾安全U盘系统&#xff0c;是一款致力于保障U盘数据内容安全的产品。通过严格身份认证、便捷安全的密保机制、智能的U盘锁定或自毁设置、详细的文件操作日志、文件粉碎、设置还原等&#xff0c;天锐绿盾安全U盘系统为您U盘的数据保驾护航&#xff0…...

灰色预测模型

当谈论灰色预测时&#xff0c;通常是指灰色系统理论&#xff0c;它是一种用于处理少量数据或缺乏充分信息的情况下进行预测和分析的数学方法。灰色预测的核心思想是通过建立灰色模型来分析和预测数据的变化趋势。 我会解释灰色预测的基本原理、步骤和方法&#xff1a; 1. 灰色…...

Yolo系列-yolov1

YOLO-V1 经典的one-stage方法 YouOnlyLookOnce&#xff0c;名字就已经说明了一切&#xff01;把检测问题转化成回归问题&#xff0c;一个CNN就搞定了&#xff01;可以对视频进行实时检测&#xff0c;应用领域非常广&#xff01; 核心思想&#xff1a; Yolov1的核心思想是将对象…...

单片机TVS/ESD二极管防护

TVS 瞬态电压抑制二极管Transient Voltage Suppressor ESD 静电释放二极管 Electro-Static discharge 这两种本质上都是二极管。都是利用了二极管正向导通、反向截止的特性。二极管在反向截止截止条件下&#xff0c;如果电压继续增大&#xff0c;将会引发雪崩&#xff0c;使得…...

TCP协议的重点知识点

TCP协议的重点知识点 TCP(传输控制协议)是一种面向连接、可靠的数据传输协议,工作在传输层,提供可靠的字节流服务。它是互联网协议栈中最重要、最复杂的协议之一,也是面试中常被问到的知识点。本文将详细介绍TCP协议的各个重要概念。 TCP基本特性 TCP主要具有以下基本特性: …...

大数据——一文熟悉HBase

1、HBase是什么 HBase是基于HDFS的数据存储&#xff0c;它建立在HDFS文件系统上面&#xff0c;利用了HDFS的容错能力&#xff0c;内部还有哈希表并利用索引&#xff0c;可以快速对HDFS上的数据进行随时读写功能。 Hadoop在已经有一个HiveMapReduce结构的数据读写功能&#x…...

如何有效进行RLHF的数据标注?

编者按&#xff1a;随着大语言模型在自然语言处理领域的广泛应用&#xff0c;如何从人类反馈进行强化学习&#xff08;RLHF&#xff09;已成为一个重要的技术挑战。并且RLHF需要大量高质量的人工数据标注&#xff0c;这是一个非常费力的过程。 本文作者在数据标注领域具有丰富经…...

2023年8月22日OpenAI推出了革命性更新:ChatGPT-3.5 Turbo微调和API更新,为您的业务量身打造AI模型

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…...

windows配置wsl,Unbuntu启动GPU加速

wsl全称Windows Subsystem for Linux&#xff0c;windows电脑下的linux子系统&#xff0c;对于想用Linux的Windows用户来说wsl是一个不错的选择。 安装wsl 两种方法可以安装wsl&#xff0c;这个默认安装在C盘。 方法一运行命令安装 wsl --install方法二&#xff0c;在windo…...

Postman测WebSocket接口

01、WebSocket 简介 WebSocket是一种在单个TCP连接上进行全双工通信的协议。 WebSocket使得客户端和服务器之间的数据交换变得更加简单&#xff0c;允许服务端主动向客户端推送数据。在WebSocket API中&#xff0c;浏览器和服务器只需要完成一次握手&#xff0c;两者之间就直…...

【内网穿透】搭建我的世界Java版服务器,公网远程联机

目录 前言 1. 搭建我的世界服务器 1.1 服务器安装java环境 1.2 配置服务端 2. 测试局域网联机 3. 公网远程联机 3.1 安装cpolar内网穿透 3.1.1 windows系统 3.1.2 linux系统&#xff08;支持一键自动安装脚本&#xff09; 3.2 创建隧道映射内网端口 3.3 测试公网远程…...

Unable to Locate package python2| Linux Ubuntu系统下python2的安装

Linux Ubuntu系统下python2的安装 FSL的安装脚本是用Python2写的&#xff0c;新版本的Ubuntu &#xff08;16以后&#xff09;在默认情况下没有安装Python2。在终端输入 python2&#xff0c;若提示没有相应的命令&#xff0c;则需要先安装Python2&#xff0c;如下指令&#xf…...

从上帝视角俯瞰vue2路由(简单易懂)

文章目录 路由原理&#xff08;hash&#xff09;路由安装和使用&#xff08;vue2&#xff09;路由跳转路由的传参和取值嵌套路由路由守卫完整代码 路由原理&#xff08;hash&#xff09; 单页应用的路由模式有两种 哈希模式&#xff08;利用hashchange 事件监听 url的hash 的…...

STL-空间配置器的了解

前言 空间配置器&#xff0c;顾名思义就是为了各个容器高效的管理空间&#xff08;空间的申请与回收&#xff09;的&#xff0c;在默默的工作的。虽然在常规上使用STL时&#xff0c;可能用不上它&#xff0c;但是站在学习研究的角度&#xff0c;学习它的实现原理对我们有很大的…...

哔哩哔哩 B站 bilibili 视频视频音效调节 清澈人声

视频音效调节方式&#xff1a;直接视频播放内容界面内鼠标右键点击视频音效调节 注意&#xff1a;需要使用的是谷歌浏览器&#xff0c;我的火狐浏览器试了不行&#xff0c;都没选项&#xff0c;火狐的出来的界面是这样的&#xff1a; 目录 具体操作如下&#xff1a; 1、谷歌…...

下一代存储解决方案:湖仓一体

文章首发地址 湖仓一体是将数据湖和数据仓库相结合的一种数据架构&#xff0c;它可以同时满足大数据存储和传统数据仓库的需求。具体来说&#xff0c;湖仓一体可以实现以下几个方面的功能&#xff1a; 数据集成&#xff1a; 湖仓一体可以集成多个数据源&#xff0c;包括结构…...

IntelliJ IDEA 2023.2.1 修复版本日志

我们刚刚发布了 v2023.2 的第一个错误修复更新。 您可以从 IDE 内部、使用工具箱应用程序或通过快照&#xff08;如果您使用的是 Ubuntu&#xff09;更新到此版本。您也可以直接从我们的网站下载。 以下是最新版本中包含的最值得注意的改进和修复的列表&#xff1a; 我们已经解…...

算法通关村十三关 | 数组字符串加法专题

1. 数组实现整数加法 题目&#xff1a;LeetCode66&#xff0c;66. 加一 - 力扣&#xff08;LeetCode&#xff09; 思路 我们只需要从头到尾依次运算&#xff0c;用常量标记是否进位&#xff0c;需要考虑的特殊情况是digits [9,9,9]的时候进位&#xff0c;我们组要创建长度加1…...

大模型赋能多尺度空间智能:从具身感知到地球系统建模的跨学科探索

1. 大模型如何重构空间智能的认知框架 当AlphaGo击败人类棋手时&#xff0c;我们惊叹于AI的策略能力&#xff1b;但当大语言模型开始理解三维空间关系时&#xff0c;这标志着机器认知的质变。空间智能的本质是理解物体间的相对位置、距离和运动规律&#xff0c;这种能力对人类而…...

汽车智能制造时代,哪些服务商助力智慧供应链?

一辆汽车的诞生&#xff0c;背后是一场精密到分钟的大合唱。当生产线以每小时数十台的速度流转时&#xff0c;任何一个零部件的迟到&#xff0c;都可能导致整条线停摆。一个汽车工厂里&#xff0c;单一产线同时生产多种车型&#xff0c;涉及数以万计的SKU零部件。这些物料必须从…...

别再手动算置信区间了!ArcGIS里用Python脚本批量计算FVC,效率提升90%

遥感植被覆盖度自动化计算&#xff1a;用Python脚本解放ArcGIS生产力 当面对数百景遥感数据需要计算植被覆盖度(FVC)时&#xff0c;手动操作ArcGIS界面不仅耗时费力&#xff0c;还容易因人为失误导致结果不一致。我曾在一个省级生态评估项目中&#xff0c;需要处理3年共36期Lan…...

HCIA复习作业

一、 实验拓扑二、 实验需求1.学校内HTTP客户端可以正常通过域名www.baidu.com访问百度的服务器 2.学校网络内部基于192.168.1.0/24划分&#xff0c;PC1可以访问3.3.3.0/24网段&#xff0c;PC2不允许 3.学校内部使用静态路由&#xff0c;R1和R2之间浮动静态路由 4.运营商使用动…...

GB28181协议实战:WVP开源项目+ZLM流媒体服务联调配置详解

GB28181协议实战&#xff1a;WVP开源项目ZLM流媒体服务联调配置详解 在视频监控领域&#xff0c;GB28181协议作为国家标准协议&#xff0c;已经成为设备互联互通的重要基础。而将WVP&#xff08;Web Video Platform&#xff09;开源项目与ZLM&#xff08;ZLMediaKit&#xff09…...

大疆L1点云数据导出后,用CloudCompare做可视化与简单分析的完整流程

大疆L1点云数据从导出到分析&#xff1a;CloudCompare实战全流程指南 当你从DJI Terra中导出L1激光雷达的LAS文件时&#xff0c;真正的数据价值挖掘才刚刚开始。作为测绘工程师或三维建模从业者&#xff0c;如何将这些原始点云转化为可操作的洞察&#xff1f;本文将带你用开源神…...

5G赋能下的车联网协同感知:自动驾驶感知盲区消除新思路

1. 为什么自动驾驶需要"组队开黑"模式&#xff1f; 想象一下你开车经过一个十字路口&#xff0c;左侧突然冲出一辆外卖电动车——这是典型的A柱盲区问题。传统自动驾驶就像闭着眼睛打游戏&#xff0c;全靠本车传感器"听声辨位"。而5G车联网协同感知&#x…...

如何快速搭建Kafka Docker集群:broker-list.sh工作原理与实用指南

如何快速搭建Kafka Docker集群&#xff1a;broker-list.sh工作原理与实用指南 【免费下载链接】kafka-docker Dockerfile for Apache Kafka 项目地址: https://gitcode.com/gh_mirrors/ka/kafka-docker GitHub 加速计划 / ka / kafka-docker 项目提供了基于 Docker 的 A…...

从零推导贝尔曼方程:强化学习中的价值函数与策略优化

1. 强化学习中的价值函数基础 想象你正在玩一个迷宫游戏&#xff0c;每走一步都会消耗体力&#xff0c;找到出口能获得大奖。这时候你会想&#xff1a;**"从当前位置出发&#xff0c;最终能获得多少奖励&#xff1f;"这个问题的答案就是价值函数&#xff08;Value Fu…...

Spring Boot新手必看:从零搭建Web项目的5个关键步骤(附常见报错解决方案)

Spring Boot新手实战指南&#xff1a;从零构建Web应用的完整路线图 为什么选择Spring Boot作为你的第一个Java Web框架&#xff1f; 当你第一次接触Java Web开发时&#xff0c;面对众多框架的选择可能会感到迷茫。Spring Boot之所以成为大多数开发者的首选&#xff0c;是因为…...