当前位置: 首页 > 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语言 虚拟头…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

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

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

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

boost::filesystem::path文件路径使用详解和示例

boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类&#xff0c;封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解&#xff0c;包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...