森林的带度数层次序列存储

2023-10-25 09:30

本文主要是介绍森林的带度数层次序列存储,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

总时间限制: 

1000ms

内存限制: 

65536kB

描述

对于树和森林等非线性结构,我们往往需要将其序列化以便存储。有一种树的存储方式称为带度数的层次序列。我们可以通过层次遍历的方式将森林序列转化为多个带度数的层次序列。

例如对于以下森林:

两棵树的层次遍历序列分别为:C E F G K H J / D X I

每个结点对应的度数为:3 3 0 0 0 0 0 / 2 0 0

我们将以上序列存储起来,就可以在以后的应用中恢复这个森林。在存储中,我们可以将第一棵树表示为C 3 E 3 F 0 G 0 K 0 H 0 J 0,第二棵树表示为D 2 X 0 I 0。

现在有一些通过带度数的层次遍历序列存储的森林数据,为了能够对这些数据进行进一步处理,首先需要恢复他们。

输入

输入数据的第一行包括一个正整数n,表示森林中非空的树的数目。
随后的 n 行,每行给出一棵树的带度数的层次序列。
树的节点名称为A-Z的单个大写字母。

输出

输出包括一行,输出对应森林的后根遍历序列。

样例输入

2
C 3 E 3 F 0 G 0 K 0 H 0 J 0
D 2 X 0 I 0

样例输出

K H J E F G C X I D

解决:注意是层次结构,应该采用队列帮助恢复。

为了得到节点在树中的真实地址,可以采用添加节点时返回具体位置的方法。

为一个节点增加子节点,如果子节点指针为空则直接增加,否则应该为子节点增加兄弟节点

为一个节点增加兄弟节点,如果兄弟节点指针为空则直接曾姐,否则应该为兄弟节点增加兄弟节点。

具体实现:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<memory.h>
#include<queue>
using namespace std;struct leaf {char ch;int n;leaf* child, * brother;leaf(){}leaf(char x,int num) {ch = x;n = num;child = brother = NULL;};leaf* add_brother(char x, int num) {if (!brother) {brother = new leaf(x, num);return brother;}else return brother->add_brother(x, num);}leaf* add_child(char x,int num) {if (!child) {child = new leaf(x, num);return child;}else return child->add_brother(x, num);}void read() {if(child)child->read();cout <<ch<< " ";if(brother)brother->read();}
};queue <leaf*> line;int main(){int n; cin >> n;while (n--) {while (!line.empty())line.pop();char q; int p;cin >> q >> p;leaf* tree = new leaf(q, p);int howMany = p;leaf* index = tree;while (!line.empty()||howMany) {if (!howMany) {index = line.front();howMany = index->n;line.pop();}//cout<<howMany<<" "<<line.size() << endl;cin >> q >> p;howMany--;if (p)line.push(index->add_child(q, p));else index->add_child(q, p);}tree->read();}
}

这篇关于森林的带度数层次序列存储的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/281636

相关文章

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

MySQL之InnoDB存储引擎中的索引用法及说明

《MySQL之InnoDB存储引擎中的索引用法及说明》:本文主要介绍MySQL之InnoDB存储引擎中的索引用法及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录1、背景2、准备3、正篇【1】存储用户记录的数据页【2】存储目录项记录的数据页【3】聚簇索引【4】二

MySQL之InnoDB存储页的独立表空间解读

《MySQL之InnoDB存储页的独立表空间解读》:本文主要介绍MySQL之InnoDB存储页的独立表空间,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、独立表空间【1】表空间大小【2】区【3】组【4】段【5】区的类型【6】XDES Entry区结构【

SQLite3 在嵌入式C环境中存储音频/视频文件的最优方案

《SQLite3在嵌入式C环境中存储音频/视频文件的最优方案》本文探讨了SQLite3在嵌入式C环境中存储音视频文件的优化方案,推荐采用文件路径存储结合元数据管理,兼顾效率与资源限制,小文件可使用B... 目录SQLite3 在嵌入式C环境中存储音频/视频文件的专业方案一、存储策略选择1. 直接存储 vs

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

MySQL 存储引擎 MyISAM详解(最新推荐)

《MySQL存储引擎MyISAM详解(最新推荐)》使用MyISAM存储引擎的表占用空间很小,但是由于使用表级锁定,所以限制了读/写操作的性能,通常用于中小型的Web应用和数据仓库配置中的只读或主要... 目录mysql 5.5 之前默认的存储引擎️‍一、MyISAM 存储引擎的特性️‍二、MyISAM 的主

Linux lvm实例之如何创建一个专用于MySQL数据存储的LVM卷组

《Linuxlvm实例之如何创建一个专用于MySQL数据存储的LVM卷组》:本文主要介绍使用Linux创建一个专用于MySQL数据存储的LVM卷组的实例,具有很好的参考价值,希望对大家有所帮助,... 目录在Centos 7上创建卷China编程组并配置mysql数据目录1. 检查现有磁盘2. 创建物理卷3. 创

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

使用Python实现调用API获取图片存储到本地的方法

《使用Python实现调用API获取图片存储到本地的方法》开发一个自动化工具,用于从JSON数据源中提取图像ID,通过调用指定API获取未经压缩的原始图像文件,并确保下载结果与Postman等工具直接... 目录使用python实现调用API获取图片存储到本地1、项目概述2、核心功能3、环境准备4、代码实现