二叉树基础

前言

我们好久没有更新数据结构的博文了,今天来更新一期树!前几期我们已经介绍了顺序表、链表,栈和队列等基本的线性数据结构并对其分别做了实现,本期我们再来介绍一个灰常重要的非线性基本结构 ---- 树型结构。

本期内容介绍

树的概念和结构

二叉树的概念和结构

一、树的概念和结构

树的概念

是一种线性(逻辑上非连续)的数据结构,它是由n(n >= 0)个有限结点组成的一个具有层次关系的集合!把他称为树是因为它的逻辑结构和一颗倒挂的树相似!

注意点:

(1)树中有一个特殊的结点被称为根节点,根节点没有前驱结点

(2)除了根节点以外,其余结点被分成了M(M > 0)个互不相交的集合(即子树之间不能相交)!其中每个集合又是一颗结构与树类似的子树!每颗子树的根结点有且只有一个前驱,可以有0个或多个后继!

所以综上树是更合适用递归定义的!

OK,画个图来理解一下:

注意:

树形结构中,子树与子树是不能相交的,如果相交就是我们后期介绍的图了!

除了根结点外,其余结点有且只有一个父节点

一个N个节点的树有N-1条边

树的相关概念

节点的度:一个节点含有的子树的个数被称为该节点的度;

叶子节点(终端节点度为0的节点称为叶子结点;

非终端节点(分支节点度不为0的节点

父亲节点(双亲节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;

子节点(孩子节点):一个节点含有的子树的根节点称为该节点的子节点;

兄弟节点具有相同父节点的节点互称为心底节点;

树的度:一棵树中,最大节点的度被称为树的度。

节点的层次:从根节点开始定义第一层,根的子节点为第二层,依次类推!

树的高度(深度):树中节点的最大层次;

堂兄弟节点:双亲在同层的节点互成称堂兄弟节点;

节点的祖先从根到该节点所经分支上的所有节点;

子孙:以某节点为根的子树中任一节点都称为该节点的子孙;

森林:由m(m>0)棵互不相交的树的集合称为森林;


树的表示

树结构相较于线性结构就复杂了,要存储起来也比较麻烦!既要存储值域,也要存储结点之间的关系!树的表示方式有很多种例如:双亲表示法、孩子表示法、孩子双亲表示法、孩子双亲表示法

这里大概介绍一下,后面重要的会在介绍例如双亲表示法(并查集)和孩子表示法(图的邻接表)!

双亲表示法是:用数组存储每个节点,每个节点中存入他们的父亲节点的下标!

孩子表示法:采用顺序表个链表进行存储,顺序表存各个节点,每个节点中保存第一个孩子的头指针

这些其实都不是最优结构,最优结构是下面我要介绍的这个----孩子兄弟表示法!

孩子兄弟表示法:有两个指针域和一个数据域。一个是孩子指针域,另一个是兄弟指针域!只要是当前节点的孩子就挂到孩子节点后面,如果是兄弟节点则挂到兄弟节点的后面,这样就可以把非二叉树转换为二叉树来处理了!

typedef char DataType;
struct Node
{
	struct Node* _LeftChild;
	struct Node* _RightBother;
	DataType _data;
};

树结构在现实中的应用

树这种结构其实在现实中应用的地方不多,最典型的就是文件系统的目录结构!

这就是Linux下的一个文件目录系统结构,他就是一棵多叉树!

二、二叉树的概念和结构

二叉树的概念

二叉树:至多为2的树,被称为二叉树!

注意:这里是至多,也就是说度可以为0,1 ,  2都可以!

二叉树是由一个根节点和左右子树构成的!

二叉树有左右之分!次序不能颠倒!

二叉树的5种特殊情况:

所有的二叉树都是由以上5中组成的!

特殊的二叉树

满二叉树:一个二叉树,如果每一层的节点数都达到最大值,则称该二叉树为满二叉树!(也就是说如果一个二叉树有K层它的节点总数是:2^k  - 1就说明他是满二叉树)

完全二叉树:对于深度为K,节点数是n的二叉树,当且仅当每一个节点与深度为K的那一层的每一个编号都对应(也就是说前K-1层是满的,第K层按序号依次存放的)的树被称为完全二叉树!也就是说满二叉树实际上是完全二叉树的特例

OK,画个图理解一下:

完全二叉树是很有用的!后面我们玩的堆、堆排序、TopK问题都是基于完全二叉树实现的!

二叉树的性质

(1)若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1)个节点

(2)若规定根节点的层数为1,则一棵高度为h的二叉树的最大节点数是2^(h) - 1

(3)若规定根节点的层数为1,则具有n个节点的满二叉树的深度h = log2(N+1)

(4)对于任意一棵二叉树,假设度为0的节点(叶子结点)的个数为n0,度为2的节点的个数为n2,则有n0 = n2 + 1

(5)对于高度为h的二叉树的节点范围[2^(h-1), 2^(h)-1]

(6)对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:

若i > 0,位置节点的双亲下标为:(i-1)/2,根节点无双亲

若2i+1 < n, 则左孩子的下标为2i+1,否则如果2i+1 >= n则无左孩子

若2i+1 < n, 则右孩子的下标为2i+2,否则如果2i+2 >= n则无右孩子

二叉树的存储

二叉树的存储一般分为:顺序存储链式存储两种~!

1、顺序存储

顺序存储就是用数组来存储一般的二叉树都是不适合用数组存的,因为会有空间的浪费,只有完全二叉树才适合用数组来存储!堆就是这样搞的(后面会介绍)!二叉树用数组存储(顺序存储)在物理上是一个数组,在逻辑上是一棵二叉树!

2、链式存储

二叉树的链式存储是指,用链表表示(存储)一棵二叉树,也就是用链表来指示各个节点的逻辑关系!一般每个节点都有三个域,一个数据域,两个指针域(左右指针域),它两分别指向二叉树的左右节点。链式存储又可以分为二叉链和三叉链,我们这里玩的是二叉链,三叉连后期在介绍,他是玩那个红黑树的!

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType datal;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BT;

OK,本期二叉树的基础知识就介绍到这里,我们下期再来对顺序存储和链式存储来实现!

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

计算机 - - - 浏览器网页打开本地exe程序,网页打开微信,网页打开迅雷

效果 在电脑中安装了微信和迅雷&#xff0c;可以通过在地址栏中输入weixin:打开微信&#xff0c;输入magnet:打开迅雷。 同理&#xff1a;在网页中使用a标签&#xff0c;点击后跳转链接打开weixin:&#xff0c;也会同样打开微信。 运用同样的原理&#xff0c;在网页中点击超…

第3关:集合操作100

任务描述相关知识编程要求测试说明 任务描述 本关任务&#xff1a;使用 集合操作解决实际问题 相关知识 1.集合并操作符 可转换为SQL 若R,S的属性名不同&#xff0c;可使用重命名使相应列名一致后进行并操作 例如&#xff1a;R(A,B,C) S(D,E,F) select A,B from R union sel…

【STM32】串口和printf

1.数据通信的基本知识 1.串行/并行通信 2.单工/半双工/全双工通信 类似于【广播 对讲 电话】 不是有两根线就是全双工&#xff0c;而是输入和输出都有对应的数据线。 3.同步/异步通信 区分同步/异步通信的根本&#xff1a;判断是否有时钟信号&#xff08;时钟线&#xff09;。…

开源维修上门服务小程序SAAS系统源码 带完整搭建教程

在现代生活中&#xff0c;家电设备维修往往是一个耗时且繁琐的过程。消费者需要花费大量时间寻找合适的维修人员&#xff0c;并面临服务质量不稳定的风险。同时&#xff0c;对于维修人员来说&#xff0c;寻找客户和接收订单的过程也十分繁琐。因此&#xff0c;开发一款基于小程…

深入理解JVM虚拟机第二十五篇:详解JVM方法的绑定机制静态绑定和动态绑定,早期绑定晚期绑定,并编写代码从字节码角度证明这件事情

大神链接&#xff1a;作者有幸结识技术大神孙哥为好友&#xff0c;获益匪浅。现在把孙哥视频分享给大家。 孙哥链接&#xff1a;孙哥个人主页 作者简介&#xff1a;一个颜值99分&#xff0c;只比孙哥差一点的程序员 本专栏简介&#xff1a;话不多说&#xff0c;让我们一起干翻J…

【MediaFoundation】相关的概念

MF 概览 Media Foundation 提供了两种不同的编程模型&#xff0c;左边展示的是端到端的媒体数据模型&#xff0c;主要用在&#xff1a;播放URL或者文件&#xff0c;以及控制流。 在图表右侧展示的第二种模型中&#xff0c;应用程序可以从源头拉取数据&#xff0c;也可以将数据…

一文了解VR全景拍摄设备如何选择,全景图片如何处理

引言&#xff1a; 在如今的数字化时代&#xff0c;虚拟现实&#xff08;VR&#xff09;技术不仅为我们的生活增添了许多乐趣&#xff0c;也为摄影领域带来了新的摄影方式&#xff0c;那么VR全景拍摄如何选择设备&#xff0c;全景图片又怎样处理呢&#xff1f; 一. VR全景拍摄设…

uniapp项目笔记

1.生成二维码 import uqrCode from /static/erweima.js uqrCode.make({canvasId: qrcode,componentInstance: this,text: JSON.stringify(item.id),size: 150,margin: 0,backgroundColor: #ffffff,foregroundColor: #000000,fileType: jpg,errorCorrectLevel: uqrCode.errorCor…

高质量实时渲染笔记

文章目录 Real-time shadows1 自遮挡问题2 解决阴影detach问题&#xff1f;3 Aliasing4 近似积分5 percentage closer soft shadows(PCSS)percenta closer filtering(PCF)PCSS的思想 6 Variance Soft Shadow Mapping (VSSM)步骤Moment Shadow Mapping 7 Distance field shadow …

LeetCode - 232.用栈实现队列 225.用队列模拟实现栈 (C语言,配图)

目录 232.用栈实现队列 225.用队列模拟实现栈 注&#xff1a;本文是基于C语言实现的代码&#xff0c;所以栈和队列是在力扣上制造实现的&#xff0c;如果你使用C等语言&#xff0c;可以忽略前面相当大部分的代码。 在栈模拟实现栈和队列之前&#xff0c;我们先来复习一下栈和…

Skywalking流程分析_4(插件的加载和不同版本的识别)

插件的结构 之前我们介绍了插件的加载&#xff0c;接下来就是真正开始进行插件的执行了&#xff0c;首先要看下插件的结构是怎么样的&#xff0c;以阿里的druid数据源为例 skywalking-plugin.def: druid-1.xorg.apache.skywalking.apm.plugin.druid.v1.define.DruidPooledCo…

【PG】PostgreSQL高可用方案repmgr部署(非常详细)

目录 简介 1 概述 1.1 术语 1.2 组件 1.2.1 repmgr 1.2.2 repmgrd 1.3 Repmgr用户与元数据 2 安装部署 2.0 部署环境 2.1 安装要求 2.1.1 操作系统 2.1.2 PostgreSQL 版本 2.1.3 操作系统用户 2.1.4 安装位置 2.1.5 版本要求 2.2 安装 2.2.1 软件包安装 2.2…

使用Filebeat+Kafka+Logstash+Elasticsearch构建日志分析系统

随着时间的积累&#xff0c;日志数据会越来越多&#xff0c;当您需要查看并分析庞杂的日志数据时&#xff0c;可通过FilebeatKafkaLogstashElasticsearch采集日志数据到Elasticsearch中&#xff0c;并通过Kibana进行可视化展示与分析。本文介绍具体的实现方法。 一、背景信息 …

科学上网导致Adobe软件运行弹出This non-genuine Adobe app will be disabled soon,尝试解决办法

之前介绍用防火墙拦截Adobe软件的出站规则可以解决软件的非正版弹窗&#xff0c;但是有的用户却不行是为什么&#xff0c;原因是使用了代理网络。因为Adobe此时跑的不是本地的流量而是代理的流量。所以防火墙拦截就不起作用了。 首先是之前介绍过的拦截方法&#xff0c;如果你没…

百度飞浆环境安装

前言&#xff1a; 在安装飞浆环境之前得先把pytorch环境安装好&#xff0c;不过关于pytorch网上教程最多的都是通过Anaconda来安装&#xff0c;但是Anaconda环境安装容易遇到安装超时导致安装失败的问题&#xff0c;本文将叫你如何通过pip安装的方式快速安装&#xff0c;其实这…

14——1

这句话的意思是&#xff0c;如图中月份12天数23时&#xff0c;就是1223&#xff1b;当月份9天数2时&#xff0c;就是0902. 可以看到在上面给出的数组元素中&#xff0c;并没有连续挨在一起的2023数字元素——就有人可能输出答案0。 所以这里要看一下—— ——子序列的含义&…

The 8th China Open Source Conference Successfully Concludes

由开源社主办的第八届中国开源年会&#xff08;COSCon23&#xff09;于 2023年10月29日在成都圆满收官。本次大会&#xff0c;为期两天&#xff0c;线下参会报名逾千人次&#xff0c;在线直播观看人数总计 168610 人&#xff0c;直播观看次数达 248725 次&#xff0c;官网累计浏…

网络编程 —— TCP 和 UDP 编程详解

目录 网络编程主要函数介绍 1. socket 函数 2. bind 函数 3. listen 函数 4. accept 函数 5. connect 函数 6. send 函数 7. recv 函数 8. recvfrom 函数 9. sendto 函数 TCP 和 UDP 原理上的区别 TCP 编程 服务端代码&#xff1a; 客户端代码&#xff1a; UDP 编…

nodejs+vue公益帮学网站的设计与实现-微信小程序-安卓-python-PHP-计算机毕业设计

在当今高度发达的信息中&#xff0c;信息管理改革已成为一种更加广泛和全面的趋势。为确保中国经济的持续发展&#xff0c; 如何用方便快捷的方式使管理者在广阔的数据海洋里面查询、存储、管理和共享有效的数据信息&#xff0c;对我们的学习&#xff0c;工作和生活具有重要的现…

创造者设计模式

Bike package com.jmj.pattern.builder.demo01;public class Bike {private String frame;//车架private String seat;//车座public String getFrame() {return frame;}public void setFrame(String frame) {this.frame frame;}public String getSeat() {return seat;}public…