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

【数据结构】树和二叉树概念及其结构

目录

一 树概念及结构

1 树的概念

2 树的相关概念

3 树的表示

二 二叉树概念及结构

1 概念

2 特殊二叉树

3 二叉树的性质 


一 树概念及结构

1 树的概念

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

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

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

 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)棵互不相交的树的集合称为森林;

3 树的表示

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

二 二叉树概念及结构

1 概念

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

1. 或者为空

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

从上图可以看出:

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

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

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

2 特殊二叉树

1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是 说,如果一个二叉树的层数为K,且结点总数是 ,则它就是满二叉树。

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

 

3 二叉树的性质 

1. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点

2. 若2i+1=n否则无左孩子

3. 若2i+2=n否则无右孩子

相关文章:

【数据结构】树和二叉树概念及其结构

目录 一 树概念及结构 1 树的概念 2 树的相关概念 3 树的表示 二 二叉树概念及结构 1 概念 2 特殊二叉树 3 二叉树的性质 一 树概念及结构 1 树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系的集…...

刘京城:我的《软件方法》学习经历(有彩蛋)

DDD领域驱动设计批评文集 做强化自测题获得“软件方法建模师”称号 《软件方法》各章合集 写在前面&#xff08;潘加宇&#xff09; 下面是刘京城写的关于他学习《软件方法》的经历。我在前面啰嗦几句。 我做软件建模方面的研究和普及工作已经24年了&#xff0c;和各行各业…...

浏览器详解(四) 渲染

大家好&#xff0c;我是半虹&#xff0c;这篇文章来讲浏览器渲染 1、基本介绍 浏览器是多进程多线程的架构&#xff0c;包括有浏览器进程、渲染器进程、GPU 进程、插件进程等 在上篇文章中我们介绍过浏览器进程&#xff0c;作为浏览器主进程&#xff0c;负责浏览器基本界面的…...

idea新建一个module时,文件夹显示灰色/pom.xml文件显示灰色且中间有条横线

1.问题 2.解决方法 File->Settings->Ignored Files->找到勾选的pom.xml文件&#xff0c;取消勾选&#xff0c;点击ok即可。 3.已解决...

NoSQL数据库(林子雨慕课课程)

文章目录 5.1 NoSQL数据库5.2 NoSQL和关系数据库的比较5.3 四大类型NoSQL数据库5.3.1 键值数据库和列族数据库5.3.2 文档数据库、图数据库、以及不同数据库比较分析 5.4 NoSQL数据库的理论基石CAP理论&#xff1a;BASE理论&#xff1a;Eventual consistency&#xff08;最终一致…...

模拟器运行在AndroidStudio内部,设置其独立窗口显示

在窗口内部运行 设置成独立窗口 Android Studio->Settings或Preferences->Tools->Emulator->取消勾选Launch in the Running Devices tool window --->点击右下角的OK按钮 ---> 重启Android Studio 再次启动模拟器...

计算机网络 | 体系结构

计算机网络 | 体系结构 计算机网络 | 体系结构概念及功能计算机网络简介计算机网络的功能因特网发展阶段小结 组成与分类计算机网络的组成计算机网络的分类小结 标准化工作及相关组织速率相关性能指标速率带宽吞吐量小结 时延相关性能指标时延时延带宽积往返时延RTT利用率小结 …...

ELK 处理 SpringCloud 日志

在排查线上异常的过程中&#xff0c;查询日志总是必不可缺的一部分。现今大多采用的微服务架构&#xff0c;日志被分散在不同的机器上&#xff0c;使得日志的查询变得异常困难。工欲善其事&#xff0c;必先利其器。如果此时有一个统一的实时日志分析平台&#xff0c;那可谓是雪…...

mac使用python递归删除文件夹下所有的.DS_Store文件

import osfolder_path "yourself file path"for root, dirs, files in os.walk(folder_path):for filename in files:if filename .DS_Store:file_path os.path.join(root, filename)os.remove(file_path)print("delete ok")...

Gitlab+Jenkins自动化部署,解放双手

项目打包 ​ 在部署项目前需要对源码进行打包&#xff0c;一个简单的SpringBoot项目默认是打包为jar包&#xff0c;也就是在pom.xml中的<packaging>jar</packaging>方式&#xff0c;当然也会有一些打包成war包方式&#xff0c;使用外置的Tomcat应用服务器部署war包…...

NNDL:作业3

在Softmax回归的风险函数(公式(3.39))中如果加上正则化项会有什么影响? (1) 在 Softmax 回归的风险函数中加入正则化项会对模型的训练产生影响。正则化项的作用是对模型的复杂度进行惩罚&#xff0c;防止过拟合的发生。 (2) 原书公式为&#xff1a; 在加入正则化后损失函数…...

dockers --cap-add 哪些值可以设置

--cap-add 参数可以用于向 Docker 容器添加不同的权限。除了 NET_ADMIN&#xff0c;还有一些其他常用的权限值&#xff0c;包括&#xff1a; SYS_ADMIN&#xff1a;添加系统管理员权限&#xff0c;允许容器内的进程执行系统级别的管理操作&#xff0c;如挂载文件系统、设置时间…...

golang常用库之-HTTP客户端请求库 grequests

文章目录 golang常用库之-HTTP客户端请求库 grequests什么是grequests使用 golang常用库之-HTTP客户端请求库 grequests 什么是grequests 官网&#xff1a;github.com/levigross/grequests A Go “clone” of the great and famous Requests library Go语言的grequests库是一…...

17基于matlab卡尔曼滤波的行人跟踪算法,并给出算法估计误差结果,判断算法的跟踪精确性,程序已调通,可直接运行,基于MATLAB平台,可直接拍下。

17基于matlab卡尔曼滤波的行人跟踪算法&#xff0c;并给出算法估计误差结果&#xff0c;判断算法的跟踪精确性&#xff0c;程序已调通&#xff0c;可直接运行&#xff0c;基于MATLAB平台&#xff0c;可直接拍下。 17matlab卡尔曼滤波行人跟踪 (xiaohongshu.com)...

SpringCloud之Stream框架集成RocketMQ消息中间件

Spring Cloud Stream 是一个用来为微服务应用构建消息驱动能力的框架。它可以基于 Spring Boot 来创建独立的、可用于生产的 Spring 应用程序。Spring Cloud Stream 为一些供应商的消息中间件产品提供了个性化的自动化配置实现&#xff0c;并引入了发布-订阅、消费组、分区这三…...

与创新者同行!Apache Doris 首届线下峰会即将开启,最新议程公开!|即刻预约

点击此处 即刻报名 Doris Summit Asia 2023 回顾人类的发展史&#xff0c;地球起源于 46 亿年前的原始星云、地球生命最初出现于 35 亿年前的原始海洋、人类物种诞生于数百万年前&#xff0c;而人类生产力的真正提升源于十八世纪六十年代的工业革命&#xff0c;自此以后&#…...

vue解决:Parsing error: No Babel config file detected for ....

报错信息 Parsing error: No Babel config file detected for C:\Users\Admin\Desktop\shabi\work\src\App.vue. Either disable config file checking with requireConfigFile: false, or configure Babel so that it can find the config files. 分析错误&#xff1a;没有检测…...

算法题:K 次取反后最大化的数组和(典型的贪心算法问题)

这道题没有看题解&#xff0c;直接提交&#xff0c;成绩超越99.5%&#xff0c;说明思路是优的。就是考虑的情况里面弯弯绕比较多&#xff0c;需要考虑全面一点。&#xff08;本题完整题目附在了最后面&#xff09; 具体思路如下&#xff1a; 1、首先排序&#xff0c;然后从最…...

Go语言中向[]byte数组中增加一个元素

要向http.Request的body中添加一个键值对&#xff0c;可以先将其转换为一个map&#xff0c;然后对其进行修改&#xff0c;最后再将其转回为byte数组。 以下是一个示例代码&#xff1a; import ("net/http""io/ioutil""encoding/json" )type Re…...

CSS 布局案例: 2行、多行每行格数不定,最后一列对齐

布局期望的效果如下&#xff1a; 第二行最后一格与第一行最后一格对齐。每行格数不定。自动拉伸填充整个宽度 实现&#xff1a; 一开始打算用display:flex&#xff0c; 自动分散&#xff0c;但是第二行对齐第一行最后一格控制不了。 使用grid fr均分单位控制。 <!DOCTYPE…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...