数据结构:二叉树的基本概念

文章目录

  • 1. 二叉树的定义
  • 2. 二叉树的特点
  • 3. 特殊二叉树
    • 斜树
    • 满二叉树
    • 完全二叉树
  • 4. 二叉树的性质

1. 二叉树的定义

如果我们猜一个100以内的数字,该怎么猜才能理论最快呢?
第一种方式:从1,2一直猜到100, 反正数字都是100以内,总能猜到的
第二种方式:先猜50,如果比结果小,猜75;如果比结果大,猜25.最后也能猜到对应的值

很显然,第二种方式明显优于第一种方式.第一种方式的时间复杂度是 O ( N ) O(N) O(N),而第二种方式的时间复杂度是 O ( l o g N ) O(logN) O(logN).

对于这种在某个阶段都是两种结果的情形,比如开和关,0和1,真和假等等,都适合用树状结构来建模,而这种树就是之前说的很优秀的树状结构,叫做二叉树.


二叉树(Binary Tree)是n(n>=0)个结点的有限集合.

  • 该集合或者为空集(称为空二叉树).
  • 或者由一个根节点和两棵互不相交,分别称为根节点的左子树和右子树的二叉树组成.

在这里插入图片描述

2. 二叉树的特点

根据上面的二叉树的图片,我们可以得到二叉树的以下特点

  • 二叉树不存在度大于 2 的结点
    二叉树每个结点最多度为2,即最多有左右两个子树,不存在或者只有一颗子树是可以的.
  • 二叉树的子树有左右之分,次序不能随意颠倒,因此二叉树是有序树
    正如人的左脚和右脚不能随意颠倒,二叉树也分为左子树和右子树的;
    即使某个结点只有一棵子树,也是要分清楚是左子树还是右子树的

在这里插入图片描述

上图的两棵树虽然是同一棵树,但是不是同一棵二叉树


二叉树具有以下五种基本形态,任意的二叉树都是由下面的情况复合而成的
在这里插入图片描述

  • 空二叉树
  • 只有一个根结点
  • 根节点只有左子树
  • 根节点只有右子树
  • 根节点既有左子树又有右子树

如果只从形态上考虑,三个结点的树只有两种情况,就是下图的树1和后面四个中的任意一种.
但是对于二叉树这个有序树而言,左右子树是由区别的,所以下面五种情况都表示不同的二叉树.
在这里插入图片描述


现实中的二叉树很漂亮,正如在数据结构中,二叉树这个树形结构也占据很重要的地位一样,有时候数学的美和大自然的美都是相通的.

在这里插入图片描述

3. 特殊二叉树

斜树

所有的结点都只有左子树的叫左斜树,所有的结点都只有右子树的叫右斜树.
这两者统称为斜树.

在这里插入图片描述

其实,线性表就是一种特殊的斜树,但是两者的逻辑结构还是不一样的,线性表是一对一线性结构的,而斜树是一对多树形结构的


满二叉树

在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有的叶子都在同一层上,这样的二叉树称为满二叉树

在这里插入图片描述

满二叉树有以下特点

  • 叶子结点只能出现在最下一层
  • 非叶子结点的度一定是 2
  • 满二叉树的结点个数最多,叶子数最多.如果一个满二叉树有 K 层, 那么一共有 2 k − 1 2^k-1 2k1个结点

完全二叉树

对一个具有 n 个节点的二叉树按层序编号, 如果编号为 i( 1 ⩽ i ⩽ n 1\leqslant i \leqslant n 1in)的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同, 则这颗二叉树称为完全二叉树.

在这里插入图片描述

最重要的是按层序编号
例如下面的三个二叉树,就不是完全二叉树.它们对应满二叉树的结点编号缺少了.
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

总而言之就是,除了最后一层的不满并且最后一层的从第一个结点开始是连续的,这就是完全二叉树.

完全二叉树有以下特点:

  • 叶子结点只能出现在最下两层
  • 最下层的叶子一定集中在左部连续位置
  • 倒数两层,若有叶子结点,一定都在右部连续位置
  • 如果结点度为1, 则该结点只有左孩子
  • 同样节点数的二叉树,完全二叉树的深度最小

如果有h层, 那么完全二叉树的结点数为 [ 2 h − 1 , 2 h − 1 ] [2^{h-1}, 2^h - 1] [2h1,2h1]

4. 二叉树的性质

  1. 若规定根节点的层数为 1, 则一棵非空二叉树的第 i 层最多有 2 i − 1 2^{i-1} 2i1个结点.
  1. 若规定根节点的层数为 1, 则深度为 h 的二叉树的最大结点数是 2 h − 1 2^h - 1 2h1.
  1. 对任何一棵二叉树,如果度为 0 的叶子结点个数为 n 0 n_0 n0, 度为 2 的分支节点个数为 n 2 n_2 n2, 则有 n 0 = n 2 + 1 n_0 = n_2 + 1 n0=n2+1.
  1. 若规定根节点的层数为 1 , 具有n个结点的满二叉树的深度, h = l o g 2 n + 1 log_2n + 1 log2n+1.
  1. 对于具有 n 个结点的完全二叉树, 如果按照从上至下, 从左至右的数组顺序对所有结点开始从 0 编号, 则对于序号为 i 的结点有:
  • 若 i > 0, i位置结点的双亲序号: (i-1)/2; i=0, i为根节点编号, 无双亲结点.
  • 若 2i+1<n, 左孩子序号: 2i+1, 2i+1 >=n 则无左孩子
    i > 0, i位置结点的双亲序号: (i-1)/2**; i=0, i为根节点编号, 无双亲结点.
  • 若 2i+1<n, 左孩子序号: 2i+1, 2i+1 >=n 则无左孩子
  • 若 2i+2<n, 右孩子序号: 2i+2, 2i+2 >=n 则无右孩子

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

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

相关文章

Unity Urp无线延申的网格效果

无线延申的网格 该项目必须是再Urp项目 shader代码实现 Shader "Unlit/infTutorial1" {Properties{_Alpha ("Alpha", Range(0, 0.5)) 0.5}SubShader{Tags{"RenderPipeline""UniversalRenderPipeline""RenderType""…

VMware下的ubuntu虚拟机,实现虚拟机与本地硬盘间的文件互传

本次安装vmware tools工具&#xff0c;以实现二者间的文件互传。 1、打开VMware软件&#xff0c;运行Ubuntu系统虚拟机 安装过程需在ubuntu虚拟机启动的情况下&#xff0c;才能进行安装&#xff1b; 2、安装VMware Tools 在VM主菜单栏中&#xff0c;点击 “虚拟机&#xff0…

Linux ❀ 进程出现process information unavailable时的消除方法

[rootmaster ~]# jps 74963 -- process information unavailable 78678 Jps [rootmaster ~]# cd /tmp/hsperfdata_redhat/ # redhat为启动该java进程的用户ps -ef | grep $pid查找 [rootmaster hsperfdata_redhat]# ll total 32 -rw------- 1 redhat redhat 32768 Sep 27 15:…

使用日志分析工具了解网络情况

日志分析&#xff08;或日志文件分析&#xff09;是检查整个网络中生成的日志数据的过程&#xff0c;日志数据从各种来源生成&#xff0c;包括外围设备、工作站、服务器、应用程序以及其他硬件和软件组件&#xff0c;将它们收集到一个中心位置并进行分析&#xff0c;可以为了解…

深入解析JVM:双亲委派机制的原理与实践

双亲委派机制 引言概述流程工作原理&#xff1a; 优势自定义类加载器实际应用 主页传送门&#xff1a;&#x1f4c0; 传送 引言 在Java虚拟机&#xff08;JVM&#xff09;中&#xff0c;类加载是一个重要的概念&#xff0c;而双亲委派机制是类加载的核心之一。本文将深入研究双…

写代码生成流程图

我们在写文档&#xff0c;博客的时候&#xff0c;一般都会使用markdown语法&#xff0c;最常见的就是一些github开源项目的README。有时候会去画一些流程图&#xff0c;例如使用process.on或者xmind等第三方网站&#xff0c;然后截图插入到文档中。 今天我们介绍一种使用代码直…

分布式搜索引擎Elasticsearch

一、Elasticsearch介绍 1.Elasticsearch产生背景 大数据量的检索NoSql: not only sql,泛指非关系型的数据库Nginx的7层负载均衡和4层负载均衡2.Elasticsearch是什么 一个基于Lucene的分布式搜索和分析引擎,一个开源的高扩展的分布式全文检索引擎 Elasticsearch使用Java开发…

一次ES检索的性能优化经验记录

优化功能: 统一检索能力&#xff0c;为各服务所调用。 该接口并发压力大&#xff0c;压测效果不理想。 初步2k线程两台压测机预发环境压测结果两pod下为400qps左右&#xff0c;单pod 平均qps200&#xff0c;响应时间在五分钟之后达到了峰值&#xff0c;平响达到几十秒开外。 压…

跨境电商引流之Reddit营销,入门保姆级攻略

在当今竞争激烈的在线市场中&#xff0c;企业不断寻求新的方法来加强其数字营销工作。Reddit 是最受欢迎的社交媒体平台之一&#xff0c;为企业提供了巨大的潜力&#xff0c;可以通过引人入胜且相关的内容来接触目标受众。然而&#xff0c;将 Reddit 用于营销目的需要仔细考虑某…

企业专线成本高?贝锐蒲公英轻松实现财务系统远程访问

在办公及信息系统领域&#xff0c;许多企业纷纷采用金蝶等财务管理软件来提升运营效率。以某食品制造企业为例&#xff0c;该企业总部位于广州&#xff0c;并拥有湖北仙桃工厂、广州从化工厂和湖南平江工厂三大生产基地。为提高管理效率&#xff0c;该企业在广州总部局域网内部…

游戏社区-搭建的目的和意义是什么

在游戏社区中&#xff0c;用户的活跃度指标是至关重要的&#xff0c;因此在必要时&#xff0c;我们会进行指标转化&#xff0c;以丰富的内容形式来促进用户的活跃度&#xff1b;作为一个垂直社区&#xff0c;我们可以通过聚合和培养一批游戏KOL&#xff0c;建立用户之间的紧密联…

成都瀚网科技:抖音上线地方方言自动翻译功能

为了让很多方言的地域历史、文化、习俗能够以短视频的形式生产、传播和保存&#xff0c;解决方言难以被更多用户阅读和理解的问题&#xff0c;平台正式上线推出当地方言自动翻译功能。创作者可以利用该功能&#xff0c;将多个方言视频“一键”转换为普通话字幕供大众观看。 具体…

leetcode 23. 合并 K 个升序链表

2023.9.25 本题要合并k个有序链表&#xff0c;最朴素的方法可以联想到之前做的合并两个有序链表。 用一个for循环遍历lists数组&#xff0c;利用合并两个有序链表的代码&#xff0c;不断合并lists中的链表&#xff0c;最后返回头节点即可。 代码如下&#xff1a; /*** Definit…

vue-cli创建项目、vue项目目录结(运行vue项目)、ES6导入导出语法、vue项目编写规范

vue-cli创建项目、vue项目目录结构、 ES6导入导出语法、vue项目编写规范 1 vue-cli创建项目 1.1 vue-cli 命令行创建项目 1.2 使用vue-cli-ui创建 2 vue项目目录结构 2.1 运行vue项目 2.2 vue项目的目录结构 3 es6导入导出语法 4 vue项目编写规范 4.1 修改项目 4.2 以后…

VC++判断程序是否已经运行;仅运行一次

VC判断程序是否已经运行&#xff1b;仅运行一次 BOOL CClientApp::InitInstance() {...//判断程序是否已经运行&#xff1b;仅运行一次CreateMutex(NULL,true,_T("xxxxx")); //xxxxx&#xff1a;为程序标识码if(GetLastError()ERROR_ALREADY_EXISTS) { AfxMess…

C#求100-999之间的水仙花数,你知道多少个?让我们一起来探索!

目录 背景: 扩展: 水仙花数例子: 效果展示:​ 总结: 背景: 水仙花数&#xff08;Narcissistic number&#xff09;也被称为超完全数字不变数&#xff08;pluperfect digital invariant, PPDI&#xff09;、自恋数、自幂数、阿姆斯壮数或阿姆斯特朗数&#xff08;Armstrong…

博主老程序员长期个人接单

主要技术栈 &#xff1a; 后端: .net winform webapi 前端&#xff1a;vue2 vue3 微信小程序 数据库&#xff1a; sqlserver mysql 小程序案例&#xff1a;快猪小寓微信小程序客户端 后台管理系统 联系微信 或 QQ 35568701

网络编程day04(网络属性函数、广播、组播、TCP并发)

今日任务 对于newfd的话&#xff0c;最好是另存然后传入给分支线程&#xff0c;避免父子线程操作同一个文件描述符 ------------在tcp多线程服务端---------- 如果使用全局变量&#xff0c;或者指针方式间接访问&#xff0c;会导致所有线程共用一份newfd和cin&#xff0c;那么…

冲刺十五届蓝桥杯P0001阶乘求和

文章目录 题目描述思路分析代码解析 题目描述 思路分析 阶乘是蓝桥杯中常考的知识。 首先我们需要知道 int 和long的最大值是多少。 我们可以知道19的阶乘就已经超过了long的最大值&#xff0c;所以让我们直接计算202320232023&#xff01;的阶乘是不现实的。 所以我们需要…