数据结构与算法之树和二叉树--树和二叉树的一些性质

目录

前言

一、树的定义

二、树的若干术语

1.结点的度

2.叶子

3.双亲与孩子

4.兄弟

5.祖先

6.树的度

7.结点的层次

8.树的深度

9.有序树和无序树

10.森林

三、树的逻辑结构

四、树的存储结构

1.顺序存储

2.链式存储

五、二叉树

1.定义

2.二叉树的五种状态

3.树和二叉树之间的转换

1.树转二叉树

2.二叉树转树


前言

        这边博客主要是介绍树和二叉树。

一、树的定义

        树是由n(n>=0)个结点组成的有限集合T,如果n>0,并且满足两个条件:

  1. 有且仅有一个结点称为根(root)
  2. 当n>1的时候,其余的结点分为几个互不相交的有限集合,每个集合本身又是颗树,被称为这个根的子树。

二、树的若干术语


图1.树

1.结点的度

        结点的度也就是当前节点的子结点的个数。

        例如在上图中A结点的度为3,B结点的度为2,H结点的度为1。

2.叶子

        度为0的结点。

3.双亲与孩子

        E是B的孩子,E是K和L的父结点

4.兄弟

        B、C、D为兄弟结点

5.祖先

        M的祖先结点为H、D、A

6.树的度

        树中最大结点的度

7.结点的层次

        根结点是第一层,根的结点为第二层,依次类推

8.树的深度

       树的深度指的是从根节点到树中任意节点的最长路径的长度。换句话说,树的深度是根节点到最深层节点的路径的长度。

9.有序树和无序树

        左右结点不能变的树为有序树,反之称为无序树。

10.森林

        两个或者两个以上的树组成森林

三、树的逻辑结构

        一个结点可能有多个直接后继,但只有一个直接前驱,且子树之间互不相交。

四、树的存储结构

1.顺序存储

    按照从上到下、从左到右的顺序存储。

    我们在结点和结点的双亲结点的个数存储树的信息。

     图2.树的顺序存储结构

    顺序存储有个缺点:我们需要存储所有的结点信息,当树只有左节点或者右节点的时候,我们需要再顺序表的位置补充好多个空节点,这样会造成存储空间的浪费,而且操作很不方便。依次我们一般使用顺序存储表示完全二叉树。

2.链式存储

        我们使用链表存储树。这样也有一个问题,表示树的指针的个数是不确定的。        

图3.使用链表存储树

        有没有更好的办法呢,答案是有的,我们可以把树转成二叉树来存储。

五、二叉树

1.定义

        二叉树或为空树,或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成。

2.二叉树的五种状态

图4.二叉树的五种状态

3.树和二叉树之间的转换

1.树转二叉树

        长子作为左孩子节点,兄弟节点作为右结点。

        方法:加线(兄弟相连)-- 抹线(长兄为父)--旋转

        以图1的树为例。第一步我们把结点的长子作为二叉树的左节点,其余的兄弟结点作为右结点。

        操作之后,树的形状为下图5

图5.长子作为左结点,兄弟结点作为右结点

        然后旋转兄弟结点。旋转之后的二叉树为下图6

图6.树转二叉树

2.二叉树转树

        和上述树转二叉树的顺序相反即可。

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

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

相关文章

PPT职场课:话术+技巧+框架+案例,告别只会念PPT不会讲(8节课)

课程目录 001-讲PPT如何开场及导入?5个简单实用的方法.mp4 002-讲PPT如何过渡衔接结尾?6类话术争来就用.mp4 003-掌握这3个逻辑表达万能框架,搞定98的PPT.mp4 004-学会这3种PPT结构讲解技巧告别只会念不会讲(上).mp4 005-学会这3种PPT结构讲解技巧告别只会念…

关于如何取消数据请求的操作

直接上码: class RequestManager {constructor() {this.requestQueue []}addRequestQueue(axios) {// 创建取消令牌const cancelToken axios.CancelToken.source()this.requestQueue.push(cancelToken.cancel)return cancelToken.token}clearRequestQueue() {thi…

【半夜学习MySQL】数据库概念详解探索数据库到底是如何存储的?

🏠关于专栏:半夜学习MySQL专栏用于记录MySQL数据相关内容。 🎯每天努力一点点,技术变化看得见 文章目录 什么是数据库主流数据库与数据库分类数据库的基本使用数据库的启动及关闭查看配置文件与数据库存储位置连接数据库服务器服务…

微型显示器可以实时监测大脑活动

美国团队开发基于LED的设备,以可视化大脑活动,在脑外科手术中指导神经外科医生 来自加州大学圣地亚哥分校和马萨诸塞州总医院的工程师和医生开发了一种薄膜显示设备,该设备结合了电极网格和特殊的GaN LED,可以在手术过程中实时跟…

5月9日作业

1&#xff0c;创建一对父子进程&#xff1a;父进程负责向文件中写入 长方形的长和宽子进程负责读取文件中的长宽信息后&#xff0c;计算长方形的面积。 1 #include <stdio.h> 2 #include <string.h> 3 #include <unistd.h> 4 #include <stdlib.h> 5 #…

中国4月进口以美元计同比增长8.4%,出口同比增长1.5%

中国按美元计4月进出口同比增速均转负为正&#xff0c;双双超预期。 5月9日周四&#xff0c;海关总署公布数据显示&#xff0c;以美元计价&#xff0c;中国2024年4月进口同比增长8.4%至2201亿美元&#xff0c;前值同比下降1.9%&#xff0c;出口同比增长1.5%至2924.5亿美元&…

基于Spring Boot的公司OA系统设计与实现

基于Spring Boot的银行OA系统设计与实现 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea 系统部分展示 用户登录界面&#xff0c;在银行OA系统运行后&#x…

ThingsBoard如何接受设备通过TCP发送的报文

1、概述 2、案例 2.1、阐述 2.2、导入依赖 2.3、构建Netty服务链接&#xff0c;接受的端口为8092 2.4、对数据进行相应的处理发送到ThingsBoard客户端 2.5、通过TCP链接工具 ​2.6、查看遥测数据 1、概述 TCP&#xff08;Transmission Control Protocol&#xff0c;传输…

【备战软考(嵌入式系统设计师)】11 - 硬件电路基础

逻辑门电路 首先我们需要先了解三个最基础的门电路&#xff0c;可以说我们一切的电子产品的基石就是这哥仨&#xff0c;它们就与&#xff0c;或&#xff0c;非。 与门和或门有两个输入端&#xff0c;一个输出端&#xff1b;非门有一个输入端一个输出端。 在我们数字电路中&a…

IOS Xcode证书配置和ipa打包流程(附详细图文教程)

IOS Xcode证书配置和ipa打包流程&#xff08;附图文教程&#xff09; 前言ipa文件简介证书文件简介Provisioning Profile描述文件简介当前环境版本Xcode证书配置和ipa打包流程生成Apple Distribution Certificates证书创建描述文件&#xff08;Provisioning Profiles&#xff0…

车载测试系列:车载以太网测试(一)

汽车行业对可靠性和安全性要求越来越高&#xff0c;车载以太网在应用过程中&#xff0c;为了保证其可靠性与安全性&#xff0c;需要对其开展测试工作。 传统的以太网测试和车载以太网测试存在一定差异&#xff0c;传统以太网测试方法并不适用汽车以太网测试。 汽车行业对测试…

代码随想录第四十三天|最后一块石头的重量 II 、目标和

题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 代码如下&#xff1a; 题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 代码如下&#xff1a;

986: 哈夫曼译码

解法&#xff1a;先把代码粘贴到编译器&#xff08;vs&#xff09;上&#xff0c;分享一个一键去除空白行的操作&#xff0c;ctrlf调出查找窗口&#xff0c;输入查找(?<\r\n)\r\n&#xff0c;选择正则表达式&#xff0c;替换就可以发现会去掉一百多行空白行。 本题只需要利…

通用型产品发布解决方案(基础环境搭建)

文章目录 1.项目技术栈和前置技术2.创建Linux平台1.需求分析2.安装Virtual Box1.BIOS里修改设置开启虚拟化设备支持&#xff08;f2 或f10&#xff09;2.任务管理器 -> cpu 查看虚拟化是否开启3.卸载方式4.安装6.1.265.管理员身份运行&#xff0c;选择安装位置6.一直下一步&a…

我的Transformer专栏来啦

五一节前吹的牛&#xff0c;五一期间没完成&#xff0c;今天忙里偷闲&#xff0c;给完成了。 那就是初步拟定了一个《Transformer最后一公里》的写作大纲。 之前一直想写一系列Transformer架构的算法解析文章&#xff0c;但因为一直在忙&#xff08;虽然不知道在忙啥&#xf…

银行职员向媒体投稿发文章我找到了好方法

作为一名基层银行的媒体联络专员,我的日常工作中有一项至关重要的任务,那就是代表我所在的支行向各大媒体投稿,传播我们的金融服务、产品动态以及社会责任实践。起初,这项看似简单的工作却成了我职业生涯中的一大挑战。传统的邮件投稿方式,不仅耗时费力,而且审核流程严格,稿件从…

【DSIN】深度 Session 兴趣网络

一、提出动机 这个模型依然是研究如何更好地从用户的历史行为中捕捉到用户的动态兴趣演化规律。 1.1、序列本身的特点&#xff1a; 其实用户点击序列有他自己本身的特点&#xff1a;用户过去可能有很多历史点击行为&#xff0c;按照用户的点击时间排好序&#xff0c;比如[it…

【Linux】yum与vim

文章目录 软件包管理器&#xff1a;yumLinux安装和卸载软件包Linux中的编辑器&#xff1a;vimvim下的底行模式vim下的正常模式vim下的替换模式vim下的视图模式vim下的多线程 软件包管理器&#xff1a;yum yum其实就是一个软件,也可以叫商店 和你手机上的应用商店或app store一…

【FreeRTOS 快速入门】-- 1、STM32工程移植FreeRTOS

目录 一、新建STM32工程 为了示范完整的移植过程&#xff0c;我们从0开始&#xff0c;新建一个标准的STM32点灯工程。 &#xff08;本篇以CubeMX作示范&#xff0c;CubeIDE操作近同&#xff0c;可作对比参考&#xff09; 1、新建工程 选择 芯片型号 新建工程 2、搜索芯片型号…

计算方法实验9:Romberg积分求解速度、位移

任务 输出质点的轨迹 ( x ( t ) , y ( t ) ) , t ∈ { 0.1 , 0.2 , 0.3 , . . . , 10 } (x(t), y(t)), t\in \{0.1, 0.2, 0.3, ..., 10\} (x(t),y(t)),t∈{0.1,0.2,0.3,...,10}&#xff0c;并在二维平面中画出该轨迹.请比较M分别取4, 8, 12, 16, 20 时&#xff0c;Romberg积分达…
最新文章