树和森林.
目录
一、树
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语言 虚拟头…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
解析“道作为序位生成器”的核心原理
解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制,重点解析"道作为序位生成器"的核心原理与实现框架: 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...
电脑桌面太单调,用Python写一个桌面小宠物应用。
下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡,可以响应鼠标点击,并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...
