IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> PAT甲级1020 Battle Over Cities (C++) -> 正文阅读

[数据结构与算法]PAT甲级1020 Battle Over Cities (C++)

题意:第一行几棵树,下面一行就是后序序列,在后面一行是中序序列。
题解:这是一道数据结构题,基本上就是可以通过后序和中序来确定层序,基本思路就是根据后序确定根节点,然后根据中序的根节点,分成左子树和右子树,然后不断的回溯直到左子树和右子树不能再分位置,所得到的就是排序好的树,然后再通过输出遍历的方式得到层序,这个可以用到树的输出,一般用的是队列。
详细代码样例:

#include <bits/stdc++.h>
using namespace std;
//建树
//先建立树的节点
int N;
int Post[40],In[40];//建立数组存后序和中序 
struct node{
	int value;//树的全脂
	node * right;//右子树指针 
	node * left;//左子树指针 
}; 
//根据树后序和中序建立树
node * maketree(int h1,int t1,int h2,int t2){//表示后序从h1到t1,中序从h2到t2 
	//递归先写返回条件 
	if(h1>t1) return NULL;
	node *p = new node;
	p->value = Post[t1];//后序的最后一个数就是根节点
	//在中序里面找到根节点的位置,准备递归
	int index;
	for(index=h2;Post[t1]!=In[index];index++);//利用for找到根节点在中序的index 
	//开始递归,左子树和右子树的递归
	p->left=maketree(h1,index-h2-1+h1,h2,index-1);//难点在于index与左子树后序里面的尾数 以及右子树头数 
	p->right=maketree(index-h2+h1,t1-1,index+1,t2);
	return p; 
}
int main(){
	//存数据 
	cin>>N;
	for(int i=0;i<N;i++) cin>>Post[i];
	for(int i=0;i<N;i++) cin>>In[i];
	node *root = maketree(0,N-1,0,N-1);//建树 建立好根节点 
	//建好了之后需要取出来,利用队列取树
	node *Queue[40]; 
	int head=0,tail=0;//像指针往后移动 
	Queue[tail++] = root;//第一个根节点存入队列
	while(head<tail){//循环取数 
		if(head!=0) cout<<' ';//符合输出格式
		node *p = Queue[head++];
		cout<<p->value;
		if(p->left) Queue[tail++]=p->left;
		if(p->right) Queue[tail++]=p->right;//先左子树再右子树 这样左右子树就是顺序出来的了 
	} 
}

在这里插入图片描述
这道题难度着在于如何对于一个后序和中序,进行一个回溯得到一个指针形式的树,再通过树的遍历方式得到层序,该题目对于数据结构的要求比较高。
在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-07 11:22:23  更:2022-05-07 11:23:14 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 3:44:33-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码