`
249326109
  • 浏览: 56245 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

pat 1020. Tree Traversals (25)

 
阅读更多

链接:http://pat.zju.edu.cn/contests/pat-a-practise/1020

 

题意:给定二叉树的后序遍历和中序遍历,求层序遍历。

 

分析:根据后续遍历和中序遍历,可以递归的构建树,建好树之后利用queue层序遍历。

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct Node{
	int val;
	struct Node* left;
	struct Node* right;
}Node;

int post[35];
int in[35];
int n;

Node* root;


int* findRoot(int num){
	int i;
	for(i=0;i<n;i++)
	{
		if(in[i]==num)
			return &in[i];
	}
	return NULL;

}


Node* build(int n,int *post,int *in){
	if(n<=0)
		return NULL;
	Node* root=(Node*)malloc(sizeof(Node));
	root->val=post[n-1];
	int p=findRoot(post[n-1])-in;
	root->left=build(p,post,in);
	root->right=build(n-1-p,post+p,in+p+1);
	return root;
}


int main(){
//	freopen("in.txt","r",stdin);

	scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)
		scanf("%d",&post[i]);
	for(i=0;i<n;i++)
		scanf("%d",&in[i]);
	root=build(n,post,in);

	Node queue[1000];
	int front=0;
	int rear=0;
	memcpy(&queue[rear++],root,sizeof(Node));
	Node* cur;
	int count=n;
	while(front<rear){
		cur=&queue[front++];
		printf("%d",cur->val);
		if(--count)
			printf(" ");
		if(cur->left)
			memcpy(&queue[rear++],cur->left,sizeof(Node));
		if(cur->right)
			memcpy(&queue[rear++],cur->right,sizeof(Node));

	}

	printf("\n");

	return 0;
}

 

 

 

分享到:
评论

相关推荐

    03-树2. Tree Traversals Again.zip

    在计算机科学中,树是一种非线性数据结构,它由节点(或称为顶点)以及连接这些节点的边构成。树遍历是处理树数据结构时的重要操作,它包括多种方法,如前序遍历、中序遍历和后序遍历。本主题将深入探讨后序遍历,...

    陈越、何钦铭-数据结构作业11:Tree Traversals Again二叉树非递归遍历/栈遍历

    An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the ...

    Heyinsen#LeetcodeOrPat#1020 Tree Traversals (25 分) 后序和中序构建树1

    思路后序和中序构造二叉树唯一一个注意的地方,在注释中。// 注意这里是pos-right_num-1而不是想当然的pos_inr-1,这两个的位置并不一定对应。

    7-1 Tree Traversals Again_DS_pta_C++_AgainAgain_

    标题 "7-1 Tree Traversals Again_DS_pta_C++_AgainAgain_" 指向的是一个关于数据结构(DS)的问题,特别是关于树遍历的议题,它源自编程训练平台 PTA(Programming Training Arena)的一个练习。"C++" 暗示了这个...

    pat题目分类.docx

    这些PAT甲级题目涵盖了多个计算机科学的基础知识点,主要包括字符串处理、哈希表的应用、图论问题和树结构的处理。接下来我们将对这些知识点进行详细解释。 1. **字符串处理**: - **修复键盘坏损** (1112 Stucked...

    c(数据结构).

    4. Tree Traversals(树遍历):树遍历包括前序遍历(根-左-右)、中序遍历(左-根-右)和后序遍历(左-右-根)。这些遍历方法在操作树结构时非常有用,例如复制树、打印树、计算表达式树等。 5. Calculator_Stack...

    数据结构MOOC源代码

    Tree Traversals Again”可能包含树的不同遍历方法,如前序遍历、中序遍历和后序遍历,这些都是理解树结构的关键。 “05-图3. 六度空间 (30)”可能探讨社交网络中的人际连接,六度空间理论指出每个人与其他人之间...

    BinaryTree-traversals:React Application呈现二叉树遍历

    cd BinaryTree遍历 npm安装 npm开始 浏览到htpp:// localhost:3000 登陆页面 包含一棵静态树。 用户可以选择任何遍历(顺序,前顺序或后顺序),遍历的结果将显示在树下。 您也可以同时签出算法。 预购遍历 后...

    Binary_tree_order_traversals

    Binary_tree_order_traversals 在该项目中,我们可以看到树的顺序,前顺序和后顺序。 该程序将打开一个菜单,并允许用户通过一个接一个地导入数据(节点)来创建他/她的树: '''0。退出 插入 展示 搜索 为了 预购...

    pta题库答案c语言之树结构3TreeTraversalsAgain.zip

    本题库答案主要聚焦于树的遍历,特别是"Tree Traversals Again"这一主题,这通常涉及到深度优先搜索(DFS)和广度优先搜索(BFS)两种策略。 首先,我们要理解树的基本概念。树是由n(n&gt;=1)个有限节点组成一个具有...

    浙江大学《数据结构》上课笔记 + 数据结构实现 + 课后题题解

    中国大学MOOC上浙大的《数据结构》广受好评,原因有二,一是基础,简单易懂,老师讲得也清楚,另一大优点就是配套的...Tree Traversals Again 树的遍历 中等 是否同一棵二叉搜索树 BST的建立与遍历 简单 Root of AVL T

    FileOutputBuffer.rar_Cause

    In debug build this will cause full traversals of the tree when the validate is called on insert and remove. Useful for debugging but very slow.

    数据结构英文教学课件:16_Trees_04.pdf

    1. **通用树遍历**(General Tree Traversals): - 预序遍历(Preorder Traversal):首先访问根节点,然后递归地对左子树进行预序遍历,最后遍历右子树。对于非二叉树,预序遍历依然适用,先访问根,再遍历其每个...

    leetcode焦虑-Interview-Notes:采访笔记

    Tree traversals, search Stack Queue Graph traversals(BFS, DFS) 最短路径数学题 从之前的采访中吸取的错误和教训: 调度: 更加注意时间安排,在公司现场面试前保持2-3天的开放时间。 除非非常关键,否则不要立即...

    Python 算法与数据结构

    包括树的基本概念(Examples Of Trees)、二叉堆(Binary Heaps)的优先队列实现(Priority Queues with Binary Heaps)、二叉搜索树(Binary Search Trees)以及树的遍历(Tree Traversals)。树是计算机科学中非常...

    Programming Interview Problems and Algorithms in Ruby

    Tree Serialization, Finding the Top k Elements of Data Streams, MapReduce, Partial Sorting, the Skyline Problem, DFS, BFS and Topological Sorting of Dags, the Alternative Alphabet and the Phone Words...

    程序MARKOV.rar

    `group.asv`、`group.m` 和 `traversals.m` 可能涉及到数据分组和遍历策略。分组是为了更好地理解和处理复杂的数据模式,而遍历策略则优化了状态间的搜索过程,确保找到最佳的预测路径。 最后,`read.txt` 文件可能...

    PURE-FTPD for WINDOWS 源码

    Before all : Pure-FTPd was designed on Unix and for Unix. The Windows port has been done because some people are forced to work on Win32 by their ...traversals, device opening, etc) .

    Killtest 分享000-M77 题库

    题目询问:What identifies the tables, relationship traversals, and selection criteria for the data to be archived? A. Access Definition B. Archive File C. Browse Utility D. Storage Profile 正确...

Global site tag (gtag.js) - Google Analytics