树的存储结构以及树,二叉树,森林之间的转换
目录
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:传输实体主体的方法…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...