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

树,二叉树及其相关知识

1.树概念及结构

1.1树的概念

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

  • 有一个特殊的结点,称为根结点,根节点没有前驱结点

  • 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继

  • 因此,树是递归定义的。

在这里插入图片描述

注意:树形结构中,子树之间不能有交集,否则就不是树形结构

1.2 树的相关概念

在这里插入图片描述

  • 节点的度:一个节点含有的子树的个数称为该节点的度; 如上图: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)棵互不相交的树的集合称为森林

1.3 树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法

typedef int DataType;struct Node {struct Node* _firstChild1; // 第一个孩子结点 struct Node* _pNextBrother; // 指向其下一个兄弟结点 DataType _data; // 结点中的数据域 };

在这里插入图片描述

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

在这里插入图片描述

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合,该集合:

  1. 或者为空

  2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

在这里插入图片描述

从上图可以看出:

  1. 二叉树不存在度大于2的结点

  2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

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

在这里插入图片描述

2.2 特殊的二叉树:

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

在这里插入图片描述

2.3二叉树的性质

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

2.5 二叉树的存储结构

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
1. 顺序存储
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
在这里插入图片描述
2. 链式存储
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,

相关文章:

树,二叉树及其相关知识

1.树概念及结构 1.1树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;而叶朝下的。 有一个特殊的结点&#…...

NumPy必知必会50例 | 5. 高级数组操作:成为 NumPy 数组的忍者

文章目录 5. 高级数组操作&#xff1a;成为 NumPy 数组的忍者数组重塑&#xff1a;变形大师例子&#xff1a;从一维到二维 数组合并&#xff1a;忍者团队联合例子&#xff1a;水平和垂直合并 数组分割&#xff1a;忍者的快速撤退例子&#xff1a;水平和垂直分割 5. 高级数组操作…...

《WebKit 技术内幕》学习之五(3): HTML解释器和DOM 模型

3 DOM的事件机制 基于 WebKit 的浏览器事件处理过程&#xff1a;首先检测事件发生处的元素有无监听者&#xff0c;如果网页的相关节点注册了事件的监听者则浏览器会将事件派发给 WebKit 内核来处理。另外浏览器可能也需要处理这样的事件&#xff08;浏览器对于有些事件必须响应…...

extends 和 implements

以下是 extends 和 implements 在Java代码中的区别和示例&#xff1a; 示例1&#xff1a;使用 extends 实现类继承 // 定义一个父类 Animal public class Animal {public void eat() {System.out.println("动物在吃东西");}public void sleep() {System.out.printl…...

响应拦截器的 return Promise.reject(res.data.message)

今天在看老师讲解代码的时候,解决了我心中的一些疑惑。 在做excel文件导出的时候,没有告诉浏览器文件的格式是Blod产生了报错。 看下图: 可以看到下面的内容:如果业务成功 返回 res.data 如果业务失败,给出错误信息的提示&#xff0c;将这个错误抛出去。 因此我们在发送一个…...

Windows下 VS2022 编译OpenSSL 库

SSL是Secure Sockets Layer(安全套接层协议)的缩写,可以在Internet上提供秘密性传输。Netscape公司在推出第一个Web浏览器的同时,提出了SSL协议标准。其目标是保证两个应用间通信的保密性和可靠性,可在服务器端和用户端同时实现支持。已经成为Internet上保密通讯的工业标准…...

【GitHub项目推荐--一个简单的绘图应用程序(Rust + GTK4)】【转载】

一个用 Rust 和 GTK4 编写的简单的绘图应用程序来创建手写笔记。 Rnote 旨在成为一个简单但实用的笔记应用程序&#xff0c;用于手绘或注释图片或文档。它最终能够导入/导出各种媒体文件格式。而且输出的作品是基于矢量的&#xff0c;这使其在编辑和更改内容时非常灵活。 地址…...

【算法小记】——机器学习中的概率论和线性代数,附线性回归matlab例程

内容包含笔者个人理解&#xff0c;如果错误欢迎评论私信告诉我 线性回归matlab部分参考了up主DR_CAN博士的课程 机器学习与概率论 在回归拟合数据时&#xff0c;根据拟合对象&#xff0c;可以把分类问题视为一种简答的逻辑回归。在逻辑回归中算法不去拟合一段数据而是判断输入…...

MySQL数据库的锁机制

目录 一、引言 二、锁的类型及作用 2.1 行级锁 2.2 间隙锁与临键锁 2.3 共享锁与排他锁 2.4 意向锁 2.5 表级锁 2.6 元数据锁 三、锁的管理与优化 3.1 合理设置事务隔离级别 3.2 避免长事务 3.3 索引优化 3.4 明确锁定范围 3.5 避免不必要的全表扫描 四、实战分…...

解决 conda新建虚拟环境只有一个conda-meta文件&conda新建虚拟环境不干净

像以前一样通过conda 新建虚拟环境时发现环境一团糟&#xff0c;首先新建虚拟环境 conda create -n newenv这时候activate newenv&#xff0c;通过pip list&#xff0c;会发现有很多很多的包&#xff0c;都是我在其他环境用到的。但诡异的是&#xff0c;来到anaconda下env的目…...

React16源码: React中的completeWork对HostText处理含更新的源码实现

HostText 1 &#xff09;概述 在 completeWork 中 对 HostText的处理在第一次挂载和后续更新的不同条件下进行操作 第一次挂载主要是创建实例后续更新其实也是重新创建实例 2 &#xff09;源码 定位到 packages/react-reconciler/src/ReactFiberCompleteWork.js#L663 到 c…...

网络协议与攻击模拟_07UDP协议

一、简单概念 1、UDP协议简介 UDP&#xff08;用户数据报&#xff09;协议&#xff0c;是传输层的协议。不需要建立连接&#xff0c;直接发送数据&#xff0c;不会重新排序&#xff0c;不需要确认。 2、UDP报文字段 源端口目的端口UDP长度UDP校验和 3、常见的UDP端口号 5…...

生命在于折腾——WeChat机器人的研究和探索

一、前言 2022年&#xff0c;我玩过原神&#xff0c;当时看到了云崽的QQ机器人&#xff0c;很是感兴趣&#xff0c;支持各种插件&#xff0c;查询游戏内角色相关信息&#xff0c;当时我也自己写了几个插件&#xff0c;也看到很多大佬编写的好玩的插件&#xff0c;后来因为QQ不…...

融资项目——EasyExcel将Excel文件保存至数据库

上一篇博客已经基本介绍了EasyExcel的配置与基本使用方法。现在准备使用EasyExcel将Excel文件保存至数据库。 1.由于我们想每读取Excel中的N条记录后将这些记录全部写入数据库中。所以首先我们在Mybatis文件内先要写一个批量保存Excel文件中的记录的sql语句。 <insert id&q…...

【Oracle】设置FGA(Fine-Grained Audit)细粒度审计

文章目录 【Oracle】设置FGA(Fine-Grained Audit)细粒度审计参考 【声明】文章仅供学习交流&#xff0c;观点代表个人&#xff0c;与任何公司无关。 编辑|SQL和数据库技术(ID:SQLplusDB) 收集Oracle数据库内存相关的信息 【Oracle】ORA-32017和ORA-00384错误处理 【Oracle】设…...

js vue调用activex ocx

js vue调用activex ocx 与IE调用方式不同处 CLSID和TYPE <OBJECT id"MultiplyDemo" refocx1 CLSID"{8EEF7302-1FC8-4BA0-8EA5-EC29FDBCA45B}" TYPE"application/x-itst-activex" width15% height15%></OBJECT>//调用方式1 //或是 …...

Hbas简介:数据模型和概念、物理视图

文章目录 说明零 BigTable一 Hbase简介二 HBase 访问接口简介三 行式&列式存储四 HBase 数据模型4.1 HBase 列族数据模型4.2 数据模型的相关概念4.3 数据坐标 五 概念&物理视图 说明 本文参考自林子雨老师的大数据技术原理与应用(第三版)教材内容&#xff0c;仅供学习…...

uniapp css样式穿透

目录 前言css样式穿透方法不加css样式穿透的代码加css样式穿透的代码不加css样式穿透的代码 与 加css样式穿透的代码 的差别参考 前言 略 css样式穿透方法 使用 /deep/ 进行css样式穿透 不加css样式穿透的代码 <style>div {background-color: #ddd;} </style>…...

【立创EDA-PCB设计基础完结】7.DRC设计规则检查+优化与丝印调整+打样与PCB生产进度跟踪

前言&#xff1a;本文为PCB设计基础的最后一讲&#xff0c;在本专栏中【立创EDA-PCB设计基础】前面已经将所有网络布线铺铜好了&#xff0c;接下来进行DRC设计规则检查优化与丝印调整打样与PCB生产进度跟踪 目录 1.DRC设计规则检查 2.优化与丝印调整 1.过孔连接优化 2.泪滴…...

android 线程池的管理工具类

封装了各种类型的线程池&#xff0c;方便直接使用 看下有哪些类型&#xff1a; 默认线程池&#xff0c;搜索模块专用线程池&#xff0c;网络请求专用线程池&#xff0c;U盘更新&#xff0c;同步SDK读写操作线程池&#xff0c;日志打印使用线程池 DEFALUT&#xff0c;SEARCH&…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

WebRTC调研

WebRTC是什么&#xff0c;为什么&#xff0c;如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...