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

树的存储结构以及树,二叉树,森林之间的转换

目录

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函数 前言&#xff1a; 通过C语言内存函数的知识&#xff0c;这篇将对memc…...

opencv视频文件的读取,处理与保存

文章目录 opencv视频文件的读取&#xff0c;处理与保存一、视频文件的读取&#xff1a;1、cv::VideoCapture是OpenCV库中用于处理视频输入的类&#xff0c;它提供了一种简单的方法来从摄像头&#xff0c;视频文件、或图像序列中读取帧&#xff1b;&#xff08;1&#xff09;打开…...

java - 七大比较排序 - 详解

前言 本篇介绍了七大比较排序&#xff0c;直接插入排序&#xff0c;希尔排序&#xff0c;冒泡排序&#xff0c;堆排序&#xff0c;选择排序&#xff0c;快速排序&#xff0c;归并排序&#xff0c;一些简单思想代码实现&#xff0c;如有错误&#xff0c;请在评论区指正&#xf…...

项目集成七牛云存储sdk

以PHP为例 第一步&#xff1a;下载sdk PHP SDK_SDK 下载_对象存储 - 七牛开发者中心 sdk下载成功之后&#xff0c;将sdk放入项目中&#xff0c;目录选择以自己项目实际情况而定。 注意&#xff1a;在examples目录中有各种上传文件的参考示例&#xff0c;这里我们主要参考的是…...

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应用程序时&#xff0c;配置属性通常是不可或缺的一部分。Spring Boot提供了多种方式来管理这些属性&#xff0c;其中之一是使用ConfigurationProperties注解。这篇博客将详细解释ConfigurationProperties注解以及如何使用它来管理和映射配置属性。 什么…...

北京开发APP需要多少钱

北京开发一个移动应用&#xff08;APP&#xff09;的费用因多种因素而异&#xff0c;包括项目的规模、复杂性、所需功能、设计要求、技术选择、开发团队的经验和地理位置等。一般来说&#xff0c;北京的APP开发费用通常较高&#xff0c;因为这是中国的主要技术和创新中心之一&a…...

self-attention、transformer、bert理解

参考李宏毅老师的视频 https://www.bilibili.com/video/BV1LP411b7zS?p2&spm_id_frompageDriver&vd_sourcec67a2725ac3ca01c38eb3916d221e708 一个输入&#xff0c;一个输出&#xff0c;未考虑输入之间的关系&#xff01;&#xff01;&#xff01; self-attention…...

junit @ExcludePackages排除多个包

在JUnit中&#xff0c;可以使用ExcludePackages注解来排除多个包。该注解可以用在测试类或测试方法上。 如果要排除多个包&#xff0c;可以在ExcludePackages注解的value属性中使用数组来指定要排除的包名。例如&#xff0c;要排除包com.example.package1和com.example.packag…...

Explain执行计划字段解释说明---select_type、table、patitions字段说明

1、select_type的类型有哪些 2、select_type的查询类型说明 1、SIMPLE 简单的 select 查询,查询中不包含子查询或者UNION 2、PRIMARY 查询中若包含任何复杂的子部分&#xff0c;最外层查询则被标记为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、 简述一下什么是常函数&#xff0c;有什么作用&#xff1f;50、 说说什么是虚继承&#xff0c;解决什么问题&#xff0c;如何实现&#xff1f;51、简述一下虚函数和纯虚函数&#xff0c;以及实现原理&#xff1f;52、说说纯虚函数能实例化吗&#xff0c;为什么&am…...

【Java】包

package 包&#xff08;package&#xff09;:其实就是文件夹。 作用&#xff1a;对类进行分类管理。 包的定义格式 格式&#xff1a;package 包名&#xff08;多级包用 . 分开&#xff09; 范例&#xff1a;package com.mayikt.demo01 带包的Java类编译和执行 1. 手动建包 安装…...

Hive【Hive(二)DML】

启动 hive 命令行&#xff1a; hive DML 数据操作 1、数据导入 1.1、向表中装载数据&#xff08;load&#xff09; 语法&#xff1a; hive> load data [local] inpath 数据的path [overwrite] into table student [partition (partcol1val1,…)];&#xff08;1&#x…...

HTTP的请求方法,空行,body,介绍请求报头的内部以及粘包问题

目录 一、GET与POST简介 二、空行和body 三、初识请求报头以及粘包问题 四、认识请求报头剩余部分 一、GET与POST简介 GET https://www.sogou.com/HTTP/1.1 请求报文中的方法&#xff0c;是最常规的方法&#xff08;获取资源&#xff09; POST&#xff1a;传输实体主体的方法…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

C++ 类基础:封装、继承、多态与多线程模板实现

前言 C 是一门强大的面向对象编程语言&#xff0c;而类&#xff08;Class&#xff09;作为其核心特性之一&#xff0c;是理解和使用 C 的关键。本文将深入探讨 C 类的基本特性&#xff0c;包括封装、继承和多态&#xff0c;同时讨论类中的权限控制&#xff0c;并展示如何使用类…...

基于Uniapp的HarmonyOS 5.0体育应用开发攻略

一、技术架构设计 1.混合开发框架选型 &#xff08;1&#xff09;使用Uniapp 3.8版本支持ArkTS编译 &#xff08;2&#xff09;通过uni-harmony插件调用原生能力 &#xff08;3&#xff09;分层架构设计&#xff1a; graph TDA[UI层] -->|Vue语法| B(Uniapp框架)B --&g…...