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

树与二叉树与森林的相关性质

文章目录

  • 树的度
  • 树的性质
  • 二叉树的性质
  • 二叉树与森林

树的度

树的度指的是树内所有节点的度数的最大值。

  1. 节点的度:节点所拥有的子树的数量。简单来说,我们直接数分支即可,例如下图:

在这颗二叉树中,节点2的度为2(他有两个子树),节点6的度为2(他也有两个子树),根节点1的度数也为2(有两个子树),其中叶子节点的度全部为0。
因此度为0的节点一定是叶子节点,度非零,则一定是非叶子节点。

  1. 树的度:树的度指的是所有的树中的内部节点的度数的最大值。如上图所示,所有节点的度数最大值为2(节点2和节点6和节点1),因此整个树的度为2

在这里插入图片描述

树的性质

  1. 树中所有的节点数等于树的度数+1。如上图所示,所有节点所具有的度数之和为 6,因此节点的总数: n = d+1
  2. 度为m的树中第 i 层至少有 m^(i-1) 个节点。图中树的度为2,因此m=2。第1层的节点数为1,第2层的节点数为2 ^ 1,第3层的节点数为 2 ^ 2
  3. 高度为 h 的 m 叉树最多有 (m ^ h - 1)/(m-1)。图中m=2,h=3,因此此树最多有 7 个节点。
  4. 具有 n 个节点的 m 叉树的最小高度为 logm(n(m-1)+1)。图中 n =7,m=2,因此此树的最小高度为 log2(8) ,因此高度为 3.

二叉树的性质

  1. 非空二叉树的叶子节点总数等于度为2的节点数+1。 上图中度为2的节点数为3,因此+1得叶子节点的个数为4
  2. 非空二叉树的第 k 层上最多有 2^k -1 个节点。上图中第 1 层有1个节点,第2层有两个,第3层有四个。
  3. 高度为 h 的二叉树最多有 2^ h-1 个节点。上图中高度 h =3,因此最多有 7个节点
  4. 具有n个节点的完全二叉树的高度为 log2(n+1) 或者 [log2(n)]+1。上图中有7个节点,因此高度为 log2(7+1) = 3

二叉树与森林

如何将一颗树转换为二叉树?

  1. 同一节点的各个孩子串联起来。
  2. 将每个节点的左右分支,从左往右除了第一个以外,全部删除

如何将二叉树转换为树?

  1. 二叉树从上往下分层,调整成水平方向,左孩子为一层的开始。
  2. 找到每层的双亲节点,方法为找到与这一层左孩子相连的上一个节点,即是这一层的公共双亲节点。
  3. 连接双亲节点之后,删除同层的相连关系。

图片演示:
在这里插入图片描述


森林的概念:森林是 m 棵 互不相交的树的集合(不一定是二叉树)

如何将森林转换为二叉树?

  1. 首先将森林中每一棵树转换为二叉树。
  2. 然后将第二棵树作为第一颗树的右子树,第三棵树作为第二棵树的右子树,以此类推。

如何将二叉树转换为森林?

  1. 反复断开二叉树的根节点的右孩子子树,直到不存在右孩子指针为止。

森林与二叉树的转换:
在这里插入图片描述


树与森林的遍历:

  1. 树的先序遍历等于它所对应二叉树的先序遍历
  2. 树的后序遍历等于它所对应二叉树的中序遍历

相关文章:

树与二叉树与森林的相关性质

文章目录树的度树的性质二叉树的性质二叉树与森林树的度 树的度指的是树内所有节点的度数的最大值。 节点的度:节点所拥有的子树的数量。简单来说,我们直接数分支即可,例如下图: 在这颗二叉树中,节点2的度为2&#…...

MySQL面试题

文章目录MySQL索引Mysql索引分类InnDB索引与MyISAM索引实现有什么区别一个表中如果没有创建索引,那么还会创建B树么?B树原理B树怎么来的B树 叶子节点和非叶子节点B树能存储多少数据?MySQL索引 Mysql索引分类 mysql 索引分为三类&#xff1a…...

【蓝桥OJ—C语言】高斯日记、马虎的算式、第39级台阶

文章目录高斯日记马虎的算式第39级台阶总结高斯日记 题目: 大数学家高斯有个好习惯:无论如何都要记日记。 他的日记有个与众不同的地方,他从不注明年月日,而是用一个整数代替,比如:4210。 后来人们知道&am…...

基于深度学习的三维重建网络PatchMatchNet(二):dtu数据集介绍及PatchMatchNet中加载数据部分代码解析

目录 1.dtu数据集介绍 2. PatchMatchNet中数据加载模块详解(dtu_yao_eval.py) 1.dtu数据集介绍 dtu数据集下载地址:dtu...

一文3000字从0到1实现基于requests框架接口自动化测试项目实战(建议收藏)

requests库是一个常用的用于http请求的模块,它使用python语言编写,在当下python系列的接口自动化中应用广泛,本文将带领大家深入学习这个库 Python环境的安装就不在这里赘述了,我们直接开干。 01、requests的安装 windows下执行…...

【RockerMQ】001-RockerMQ 概述

【RockerMQ】001-RockerMQ 概述 文章目录【RockerMQ】001-RockerMQ 概述一、MQ 概述1、MQ 简介2、MQ 用途限流削峰异步解耦数据收集3、常见 MQ 产品概述对比4、MQ 常见协议二、RocketMQ 概述1、简介2、发展历史一、MQ 概述 1、MQ 简介 MQ,Message Queue&#xff0…...

阿里是如何做Code Review的?

作为卓越工程文化的一部分,Code Review其实一直在进行中,只是各团队根据自身情况张驰有度,松紧可能也不一,这里简单梳理一下CR的方法和团队实践。 一、为什么要CR 提前发现缺陷 在CodeReview阶段发现的逻辑错误、业务理解偏差、性…...

内核调试:一次多线程调试与KASAN检测实例

内核调试:一次多线程调试与KASAN检测实例1. 环境说明2. 问题描述3. 问题排查与定位3.1 线程并发问题(减少线程数)3.2 轻量地跟踪对象的分配与释放3.3 检查空指针与潜在修改者3.4 KASAN检查4. 总结博主最近遇到一个非常顽固的多线程BUG&#x…...

Java - 数据结构,队列

一、什么是队列 普通队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(FirstIn First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列&#xf…...

ccc-pytorch-感知机算法(3)

文章目录单一输出感知机多输出感知机MLP反向传播单一输出感知机 内容解释: w001w^1_{00}w001​:输入标号1连接标号0(第一层)x00x_0^0x00​:第0层的标号为0的值O11O_1^1O11​:第一层的标号为0的输出值t:真实…...

LeetCode 225.用队列实现栈

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。实现 MyStack 类:void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() …...

【面试】spring控制反转IOC

目录一.说明二.ioc的概念和作用三.优点四.实现机制五.IOC和DI的区别六.设计原则一.说明 1.ioc的概念2.ioc的作用3.ioc的优点4.ioc的实现机制 二.ioc的概念和作用 1.全称Inversion of Control2.控制:创建对象的控制权3.反转:以前对象是程序员主动去new…...

Spring 事务管理详解及使用

✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...

LeetCode 232.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):实现 MyQueue 类:void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元…...

go面向对象思想封装继承多态

go貌似都没有听说过继承,当然这个继承不像c中通过class类的方式去继承,还是通过struct的方式,所以go严格来说不是面向对象编程的语言,c和java才是,不过还是可以基于自身的一些的特性实现面向对象的功能,面向…...

【网络原理9】HTTP响应篇

在前两篇文章当中,已经分别介绍了HTTP是什么,以及常见的请求头当中的属性。【网络原理7】认识HTTP_革凡成圣211的博客-CSDN博客HTTP抓包,Fiddler的使用https://blog.csdn.net/weixin_56738054/article/details/129148515?spm1001.2014.3001.…...

SpringCloud之Seata(二)

4.Seata如何应用于项目? 安装seata及修改配置 4.1 官网下载Seata安装包 4.2 修改seata/config.txt 4.2.1 修改存储方式 store.db.dbTypemysql store.db.driverClassNamecom.mysql.jdbc.Driver store.db.urljdbc:mysql://你的IP:3306/seata?useUnicodetrue sto…...

【Redis-入门阶段】基本数据结构

Redis支持多种数据结构,包括字符串、列表、哈希、集合和有序集合。这些数据结构在Redis中被称为键值对,其中键是一个字符串,值可以是一个字符串、列表、哈希、集合或有序集合。接下来,我们将详细介绍这些数据结构的使用方法。字符…...

BACnet协议详解————MS/TP物理层,数据链路层和网络层

文章目录写在前面1 物理层2 数据链路层MSTP的流程如下noteMS/TP帧格式3 网络层写在前面 这周加更一篇,来弥补一下之前落下的进度。简单的说两句,之前讲应用层的时候,只是跟官方的手册来同步一下,但是从个人理解来说,自…...

Tomcat

Tomcat 1 简介 1.1 什么是Web服务器 Web服务器是一个应用程序(软件),对HTTP协议的操作进行封装,使得程序员不必直接对协议进行操作,让Web开发更加便捷。主要功能是"提供网上信息浏览服务"。 Web服务器是安…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...