树和森林.
目录
一、树
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控制器,积分分离控制器以及滑模控制器。通过对比三个算法可知,采用滑模控制算法,其具有最快的收敛性能,较强的鲁棒性&…...
Node.js 渲染三维模型并导出为图片
Node.js 渲染三维模型并导出为图片 1. 前言 本文将介绍如何在 Node.js 中使用 Three.js 进行 3D 模型渲染。通过结合 gl 和 canvas 这两个主要依赖库,我们能够在服务器端实现高效的 3D 渲染。这个方法解决了在服务器端生成和处理 3D 图形的需求,使得可…...
Win11下安装VS2022失败的解决办法
前几天我把我的HP Z840的操作系统换成了Win11,在重装VS2022时遇到了麻烦,提示无法安装 Microsoft.VisualStudio.Devenv.Msi。 查看安装日志提示:Could not write value devenv.exe to key \SOFTWARE\Microsoft\Internet Explorer\Main\Featur…...
动态规划:基本概念
Dynamic Programming 动态规划(Dynamic Programming, DP) 是一种算法设计技巧,通常用来解决具有重叠子问题和最优子结构性质的问题。它通过将问题分解为更小的子问题,逐步解决这些子问题并将结果存储起来,以避免重复计…...
小山菌_代码随想录算法训练营第二十九天| 455. 分发饼干 、376. 摆动序列、53. 最大子序和
455. 分发饼干 文档讲解:代码随想录.分发饼干 视频讲解:贪心算法,你想先喂哪个小孩?| LeetCode:455.分发饼干 状态:已完成 代码实现 class Solution { public:int findContentChildren(vector<int>&…...
快手可灵大模型开放视频续写功能,可生成最长约3分钟视频
6月21日,可灵再度进化,正式推出图生视频功能,支持用任意静态图像生成5s视频,并且可搭配不同的文本内容,实现丰富的视觉叙事 。 同时,可灵还发布了业内领先的视频续写功能,可为已生成的视频&…...
【代码随想录】【算法训练营】【第45天】 [198]打家劫舍 [213]打家劫舍II [337]打家劫舍III
前言 思路及算法思维,指路 代码随想录。 题目来自 LeetCode。 day 45,周五,坚持不了一点~ 题目详情 [198] 打家劫舍 题目描述 198 打家劫舍 解题思路 前提: 思路: 重点: 代码实现 C语言 虚拟头…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架
1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...
算法刷题-回溯
今天给大家分享的还是一道关于dfs回溯的问题,对于这类问题大家还是要多刷和总结,总体难度还是偏大。 对于回溯问题有几个关键点: 1.首先对于这类回溯可以节点可以随机选择的问题,要做mian函数中循环调用dfs(i&#x…...
