树的存储结构以及树,二叉树,森林之间的转换
目录
1.双亲表示法
2.孩子链表
3.孩子兄弟表示法
4.树与二叉树的转换
(1)树转换为二叉树
(2)二叉树转换成树
5.二叉树与森林的转化
(1)森林转换为二叉树
以下树为例

1.双亲表示法
双亲表示法定义了一个结构数组,存放树的结点,每个结点含两个域
数据域:存放结点本身信息
双亲域:指示本结点的双亲结点在数组的位置
如下图所示A,B,C的父节点为R

2.孩子链表

#孩子结点结构
typedef struct CTNode{int child;struct CTNode *next;
}*ChildPtr;#树结构
typedef struct{CTBox nodes[MAX_TREE_SIZE];int n,r;//n表示结点数,r表示根结点的位置
}#双亲结点结构
typedef struct{TElemType data;ChildPtr firstchild;}CTBox;
3.孩子兄弟表示法
用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点
typedef struct CSNode{ElemType data;struct CSNode *firstchild,*nextsibling;}CSNode,*CSTree;
如下图“A”所示,第一个指针域指向他的第一个孩子“D”,第二个指针域指向他的兄弟结点B,以此类推:

4.树与二叉树的转换
树的存储结构如上图所示,第一个指针域指向第一个孩子,第二个指针域指向兄弟结点
而二叉树的存储结构则为第一个指针域指向左孩子,第二个指针域指向右孩子,转换如下:

那转换的方法是什么呢?
(1)树转换为二叉树
•在兄弟之间加连线

•对于每一个结点,除了左孩子外,去掉其与其余孩子之间的关系

•以树的根结点为轴心,将整树顺时针转45度

更复杂的可以看下图:

(2)二叉树转换成树
• 若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子......沿分支找到的所有右孩子,都与p的双亲用线连起来

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

•将结点按层次排列,形成树结构

5.二叉树与森林的转化
(1)森林转换为二叉树
•将每一棵树转换为二叉树

•将每一个根结点连接起来

•旋转45度

(2)二叉树转换为森林
•将二叉树中根结点与其右孩子连线,及沿右分支搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树

•将孤立的二又树还原成树

相关文章:
树的存储结构以及树,二叉树,森林之间的转换
目录 1.双亲表示法 2.孩子链表 3.孩子兄弟表示法 4.树与二叉树的转换 (1)树转换为二叉树 (2)二叉树转换成树 5.二叉树与森林的转化 (1)森林转换为二叉树 以下树为例 1.双亲表示法 双亲表示法定义了…...
【AI视野·今日NLP 自然语言处理论文速览 第四十二期】Wed, 27 Sep 2023
AI视野今日CS.NLP 自然语言处理论文速览 Wed, 27 Sep 2023 Totally 50 papers 👉上期速览✈更多精彩请移步主页 Daily Computation and Language Papers Attention Satisfies: A Constraint-Satisfaction Lens on Factual Errors of Language Models Authors Mert …...
华为云云耀云服务器L实例评测|部署个人在线电子书库 calibre
华为云云耀云服务器L实例评测|部署个人在线电子书库 calibre 一、云耀云服务器L实例介绍1.1 云服务器介绍1.2 应用场景1.3 支持镜像 二、云耀云服务器L实例配置2.1 重置密码2.2 服务器连接2.3 安全组配置 三、部署 calibre3.1 calibre 介绍3.2 Docker 环境搭建3.3 c…...
代码随想录刷题 Day28
216.组合总和III 和前一个题一样,照着自己就能写出来,就多了一个判断结果是不是等于n的逻辑。有两个地方可以剪纸,一个是当和已经大于要找的时候直接返回,另一个是当剩余元素少于三个的时候直接返回(第一层递归是少于…...
【生命周期】
生命周期 1 引出生命周期2 分析生命周期3 总结生命周期 1 引出生命周期 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta …...
【C语言 模拟实现memcpy函数、memcpy函数】
C语言程序设计笔记---027 C语言之模拟实现memcpy函数、memcpy函数1、介绍memcpy函数1.1、模拟实现memcpy函数 2、介绍memmove函数2.1、模拟实现memmove函数 3、结语 C语言之模拟实现memcpy函数、memcpy函数 前言: 通过C语言内存函数的知识,这篇将对memc…...
opencv视频文件的读取,处理与保存
文章目录 opencv视频文件的读取,处理与保存一、视频文件的读取:1、cv::VideoCapture是OpenCV库中用于处理视频输入的类,它提供了一种简单的方法来从摄像头,视频文件、或图像序列中读取帧;(1)打开…...
java - 七大比较排序 - 详解
前言 本篇介绍了七大比较排序,直接插入排序,希尔排序,冒泡排序,堆排序,选择排序,快速排序,归并排序,一些简单思想代码实现,如有错误,请在评论区指正…...
项目集成七牛云存储sdk
以PHP为例 第一步:下载sdk PHP SDK_SDK 下载_对象存储 - 七牛开发者中心 sdk下载成功之后,将sdk放入项目中,目录选择以自己项目实际情况而定。 注意:在examples目录中有各种上传文件的参考示例,这里我们主要参考的是…...
docker-compose一键启动neo4j
下载镜像 docker pull neo4j:3.5.22-community 编写配置文件 参考文档 编写docker-compose.yml文件 version: "3"services:neo4j:image: neo4j:3.5.22-communitycontainer_name: neo4j restart: alwaysports:- 7474:7474- 7687:7687environment:- NEO4J_AUTH:ne…...
深入剖析@ConfigurationProperties注解
当我们构建Spring Boot应用程序时,配置属性通常是不可或缺的一部分。Spring Boot提供了多种方式来管理这些属性,其中之一是使用ConfigurationProperties注解。这篇博客将详细解释ConfigurationProperties注解以及如何使用它来管理和映射配置属性。 什么…...
北京开发APP需要多少钱
北京开发一个移动应用(APP)的费用因多种因素而异,包括项目的规模、复杂性、所需功能、设计要求、技术选择、开发团队的经验和地理位置等。一般来说,北京的APP开发费用通常较高,因为这是中国的主要技术和创新中心之一&a…...
self-attention、transformer、bert理解
参考李宏毅老师的视频 https://www.bilibili.com/video/BV1LP411b7zS?p2&spm_id_frompageDriver&vd_sourcec67a2725ac3ca01c38eb3916d221e708 一个输入,一个输出,未考虑输入之间的关系!!! self-attention…...
junit @ExcludePackages排除多个包
在JUnit中,可以使用ExcludePackages注解来排除多个包。该注解可以用在测试类或测试方法上。 如果要排除多个包,可以在ExcludePackages注解的value属性中使用数组来指定要排除的包名。例如,要排除包com.example.package1和com.example.packag…...
Explain执行计划字段解释说明---select_type、table、patitions字段说明
1、select_type的类型有哪些 2、select_type的查询类型说明 1、SIMPLE 简单的 select 查询,查询中不包含子查询或者UNION 2、PRIMARY 查询中若包含任何复杂的子部分,最外层查询则被标记为Primary 3、DERIVED 在FROM列表中包含的子查询被标记为DERIVED(衍生)&…...
云原生微服务 第六章 Spring Cloud Netflix Eureka集成远程调用、负载均衡组件OpenFeign
系列文章目录 第一章 Java线程池技术应用 第二章 CountDownLatch和Semaphone的应用 第三章 Spring Cloud 简介 第四章 Spring Cloud Netflix 之 Eureka 第五章 Spring Cloud Netflix 之 Ribbon 第六章 Spring Cloud 之 OpenFeign 文章目录 系列文章目录前言1、OpenFeign的实现…...
四、2023.9.30.C++面向对象end.4
文章目录 49、 简述一下什么是常函数,有什么作用?50、 说说什么是虚继承,解决什么问题,如何实现?51、简述一下虚函数和纯虚函数,以及实现原理?52、说说纯虚函数能实例化吗,为什么&am…...
【Java】包
package 包(package):其实就是文件夹。 作用:对类进行分类管理。 包的定义格式 格式:package 包名(多级包用 . 分开) 范例:package com.mayikt.demo01 带包的Java类编译和执行 1. 手动建包 安装…...
Hive【Hive(二)DML】
启动 hive 命令行: hive DML 数据操作 1、数据导入 1.1、向表中装载数据(load) 语法: hive> load data [local] inpath 数据的path [overwrite] into table student [partition (partcol1val1,…)];(1&#x…...
HTTP的请求方法,空行,body,介绍请求报头的内部以及粘包问题
目录 一、GET与POST简介 二、空行和body 三、初识请求报头以及粘包问题 四、认识请求报头剩余部分 一、GET与POST简介 GET https://www.sogou.com/HTTP/1.1 请求报文中的方法,是最常规的方法(获取资源) POST:传输实体主体的方法…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
