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

树和森林.

目录

一、树

1.1树的存储结构

1.1.1双亲表示法

1.1.2孩子链表

1.1.3孩子兄弟表示法

1.2树与二叉树的转换

1.2.1将树转换成二叉树:

 1.2.2将二叉树转换成树

二、森林

2.1森林与二叉树的转换

2.1.1将森林转换成二叉树

2.1.2二叉树转换成森林

三、树和森林的遍历

3.1树的遍历

3.2森林的遍历

3.2.1先序遍历

 3.2.2中序遍历


一、树

1.1树的存储结构

1.1.1双亲表示法

实现:定义结构数组,存放树的结点,每个结点含两个域:

数据域——存放结点本身信息;双亲域——指示本结点的双亲结点在数组中的位置

根结点数组下标为0,个数n=10

(找双亲容易,找孩子难)

1.1.2孩子链表

孩子结点结构:child next ;双亲结构特点: data firstchild

(找孩子容易,找双亲难)

带双亲的孩子链表

1.1.3孩子兄弟表示法

实现:用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。

1.2树与二叉树的转换

给定一棵树,可以找到唯一的一棵二叉树与之对应。

1.2.1将树转换成二叉树:

①加线:在兄弟之间加一条线

②抹线:对每个结点,除了其左孩子外,去除其与其余孩子之间的关系

③以树的根结点为轴心,将整树顺时针旋转45°

树变二叉树:兄弟相连留长子

例:

 1.2.2将二叉树转换成树

①加线:若p结点时双亲结点的左孩子,则将p的右孩子,右孩子的右孩子,沿分支找到的所有右孩子,都与p的双亲用线连起来

②抹线:抹掉原二叉树中双亲与右孩子之间的连线

③调整:将结点按层次排列,形成树结构

二叉树变树:左孩右右连双亲,去掉原来右孩线

例:

 

二、森林

2.1森林与二叉树的转换

2.1.1将森林转换成二叉树

①将各棵树分别转换成二叉树

②将每棵树的根结点用线相连

③以第一棵树的根结点作为二叉树的根,再以根结点为轴心,顺时针旋转,构成二叉树型结构

森林变二叉树:树变二叉根相连

例:

2.1.2二叉树转换成森林

①抹线:将二叉树中根结点与其右孩子连线,及沿有分支搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树

②还原:将孤立的二叉树还原成树

二叉树变森林:去掉全部右孩线,孤立二叉再还原

例:

三、树和森林的遍历

3.1树的遍历

先根遍历:若树不空,则先访问根结点,再依次先根遍历各棵子树

后根遍历:若树不空,则先依次后根遍历各棵子树,然后访问根结点

层次遍历:若树不空,则自上而下自左至右访问树中每个结点

例:

3.2森林的遍历

把森林看作由三部分构成:

①森林中第一棵树的根结点

②森林中第一棵树的子树森林

③森林中其他树构成的森林

3.2.1先序遍历

若森林不空,则:

①访问森林中第一棵树的根结点

②先序遍历森林中第一棵树的子树森林

③先序遍历森林中(除第一棵树之外)其余树构成的森林

即:依次从左至右对森林中的每一棵树进行先根遍历

例:

 3.2.2中序遍历

若森林不空,则:

①中序遍历森林中第一棵树的子树森林

②访问森林中第一棵树的根结点

③中序遍历森林中(除第一棵树之外)其余树构成的森林

即:依次从左至右对森林中的每一棵树进行后根遍历

例:

相关文章:

树和森林.

目录 一、树 1.1树的存储结构 1.1.1双亲表示法 1.1.2孩子链表 1.1.3孩子兄弟表示法 1.2树与二叉树的转换 1.2.1将树转换成二叉树: 1.2.2将二叉树转换成树 二、森林 2.1森林与二叉树的转换 2.1.1将森林转换成二叉树 2.1.2二叉树转换成森林 三、树和森林的…...

ubuntu下同时安装和使用不同版本的库 librealsense

apt 安装的最新版本在/usr 源码安装的旧版本在/usr/local set(realsense2_DIR /usr/local/) find_package(realsense2 2.50.0 REQUIRED) message( "\n\n ${realsense2_INCLUDE_DIR} ${realsense2_VERSION} RealSense SDK 2.0 is FINDINGING, please install it from…...

openEuler操作系统下静默安装Oracle19c

在openEuler-23.09上安装Oracle19c,创建非容器数据库实例(含静默安装) 操作系统版本 openEuler-23.09-x86_64-dvd.iso ,安装步骤此处省略。。。 最常用且直接的方法来查看openEuler的版本号是查看/etc/os-release文件 [root@openEuler ~]$ cat /etc/os-release NAME="…...

Linux CPU常见命令行详解

在Linux系统中,命令行是管理和监控系统资源的重要工具。特别是当我们需要了解CPU的状态、性能和利用率时,一系列命令行工具就显得尤为重要。本文将详细介绍Linux中与CPU相关的常见命令行工具及其使用方法,帮助大家更好地理解和利用这些工具来…...

防止更新或保存 Laravel 模型

例如,创建模型后,我不希望任何人能够再次更新该记录。相反,它应该被全新的记录覆盖并存档。 这是一个简单的特征,您可以在模型上使用它来禁用更新: trait PreventsUpdating {public static function bootPreventsUpd…...

Cadence:Conformal系列形式验证工具

Conformal 工具最早由Verplex Systems开发。Verplex是一家专注于形式验证工具开发的公司,其核心产品是Conformal等效性检查工具。由于其技术的先进性和市场需求,Verplex的 Conformal工具迅速在半导体行业内获得了认可。 2003 年,Cadence Desi…...

一般人不要学Python?一般人怎么学Python!!

关于“建议一般人真的不要学Python”这一观点,我认为这是一个过于绝对的说法。实际上,Python作为一种流行的编程语言,具有许多优点,适合不同背景和需求的人学习。以下是一些反驳这一观点的理由: 易于学习和理解&#x…...

微服务架构中间件安装部署

微服务架构中间件安装部署 jdk安装 安装包jdk-8u144-linux-x64.tar.gz 先检查系统原版本的jdk并卸载 rpm -qa | grep java 显示信息如下: tzdata-java-2014g-1.el6.noarch java-1.6.0-openjdk-1.6.0.0-11.1.13.4.el6.x86_64 java-1.7.0-openjdk-1.7.0.65-2.5.1.2.…...

车辆数据的提取、定位和融合(其一 共十二篇)

第一篇: System Introduction 第二篇:State of the Art 第三篇:localization 第四篇:Submapping and temporal weighting 第五篇:Mapping of Point-shaped landmark data 第六篇:Clustering of landma…...

Vue3组件通信全解析:利用props、emit、provide/inject跨层级传递数据,expose与ref实现父子组件方法调用

文章目录 一、父组件数据传递N个层级的子组件vue3 provide 与 injectA组件名称 app.vueB组件名称 provideB.vueC组件名称 provideCSetup.vue 二、使用v-model指令实现父子组件的双向绑定父组件名称 app.vue子组件名称 v-modelSetup.vue 三、父组件props向子组件传值子组件 prop…...

华为---OSPF被动接口配置(四)

9.4 OSPF被动接口配置 9.4.1 原理概述 OSPF被动接口也称抑制接口,成为被动接口后,将不会接收和发送OSPF报文。如果要使OSPF路由信息不被某一网络中的路由器获得且使本地路由器不接收网络中其他路由器发布的路由更新信息,即已运行在OSPF协议…...

前端将Markdown文本转换为富文本显示/编辑,并保存为word文件

参考:https://www.wangeditor.com/ https://blog.csdn.net/weixin_43797577/article/details/138854324 插件: markdown-it traptitech/markdown-it-katex markdown-it-link-attributes highlight.js wangeditor/editor wangeditor/editor-for-vue html…...

git-shortlog详解

作用 git-shortlog - Summarize git log output 语法 git shortlog [<options>] [<revision-range>] [[--] <path>…​] git log --prettyshort | git shortlog [<options>] 功能描述 Summarizes git log output in a format suitable for inclus…...

通过MATLAB实现PID控制器,积分分离控制器以及滑模控制器

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 5.完整工程文件 1.课题概述 通过MATLAB实现PID控制器,积分分离控制器以及滑模控制器。通过对比三个算法可知&#xff0c;采用滑模控制算法&#xff0c;其具有最快的收敛性能&#xff0c;较强的鲁棒性&…...

Node.js 渲染三维模型并导出为图片

Node.js 渲染三维模型并导出为图片 1. 前言 本文将介绍如何在 Node.js 中使用 Three.js 进行 3D 模型渲染。通过结合 gl 和 canvas 这两个主要依赖库&#xff0c;我们能够在服务器端实现高效的 3D 渲染。这个方法解决了在服务器端生成和处理 3D 图形的需求&#xff0c;使得可…...

Win11下安装VS2022失败的解决办法

前几天我把我的HP Z840的操作系统换成了Win11&#xff0c;在重装VS2022时遇到了麻烦&#xff0c;提示无法安装 Microsoft.VisualStudio.Devenv.Msi。 查看安装日志提示&#xff1a;Could not write value devenv.exe to key \SOFTWARE\Microsoft\Internet Explorer\Main\Featur…...

动态规划:基本概念

Dynamic Programming 动态规划&#xff08;Dynamic Programming, DP&#xff09; 是一种算法设计技巧&#xff0c;通常用来解决具有重叠子问题和最优子结构性质的问题。它通过将问题分解为更小的子问题&#xff0c;逐步解决这些子问题并将结果存储起来&#xff0c;以避免重复计…...

小山菌_代码随想录算法训练营第二十九天| 455. 分发饼干 、376. 摆动序列、53. 最大子序和

455. 分发饼干 文档讲解&#xff1a;代码随想录.分发饼干 视频讲解&#xff1a;贪心算法&#xff0c;你想先喂哪个小孩&#xff1f;| LeetCode&#xff1a;455.分发饼干 状态&#xff1a;已完成 代码实现 class Solution { public:int findContentChildren(vector<int>&…...

快手可灵大模型开放视频续写功能,可生成最长约3分钟视频

6月21日&#xff0c;可灵再度进化&#xff0c;正式推出图生视频功能&#xff0c;支持用任意静态图像生成5s视频&#xff0c;并且可搭配不同的文本内容&#xff0c;实现丰富的视觉叙事 。 同时&#xff0c;可灵还发布了业内领先的视频续写功能&#xff0c;可为已生成的视频&…...

【代码随想录】【算法训练营】【第45天】 [198]打家劫舍 [213]打家劫舍II [337]打家劫舍III

前言 思路及算法思维&#xff0c;指路 代码随想录。 题目来自 LeetCode。 day 45&#xff0c;周五&#xff0c;坚持不了一点~ 题目详情 [198] 打家劫舍 题目描述 198 打家劫舍 解题思路 前提&#xff1a; 思路&#xff1a; 重点&#xff1a; 代码实现 C语言 虚拟头…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

React父子组件通信:Props怎么用?如何从父组件向子组件传递数据?

系列回顾&#xff1a; 在上一篇《React核心概念&#xff1a;State是什么&#xff1f;》中&#xff0c;我们学习了如何使用useState让一个组件拥有自己的内部数据&#xff08;State&#xff09;&#xff0c;并通过一个计数器案例&#xff0c;实现了组件的自我更新。这很棒&#…...

32位寻址与64位寻址

32位寻址与64位寻址 32位寻址是什么&#xff1f; 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元&#xff08;地址&#xff09;&#xff0c;其核心含义与能力如下&#xff1a; 1. 核心定义 地址位宽&#xff1a;CPU或内存控制器用32位…...