`
249326109
  • 浏览: 53183 次
  • 性别: 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

    给你inorder的栈操作步骤,让你写出postorder后的序列。 http://blog.csdn.net/xkzju2010/article/details/46325457

    陈越、何钦铭-数据结构作业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_

    PTA 7-1 Tree Traversals Again

    Data Structure and Algorithms

    3.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.7.1 Preorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 I 3.7.2 Postorder . . . . . . . . . . . . . . ....

    Data Structures Succinctly Part 1

    25 IsReadOnly .......................................................................................................................................... 25 Doubly Linked List ...........................

    c(数据结构).

    c (数据结构) AVLTree Graph Heap Tree Traversals Again 计算器_栈 二叉排序树 二分法查找 线性表 等 值得学习

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

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

    Binary_tree_order_traversals

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

    Data Structures & Algorithms in Swift 4th Edition

    * Traversals: Traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network...

    BFS.zip_bfs_in

    Breadth first search algorithm in C. Example are countries in Romania traversals.

    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.

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

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

    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...

    Scala.Functional.Programming.Patterns.178398

    Grok and perform effective ...Chapter 8: Traversals – Mapping/Filtering/Folding/Reducing Chapter 9: Higher Order Functions Chapter 10: Actors and Message Passing Chapter 11: It's a Paradigm Shift

    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) .

    开源项目-mdempsky-unbed.zip

    开源项目-mdempsky-unbed.zip,unbed: refactoring tool to remove implicit field traversals

    Neo4j High Performance(PACKT,2015)

    Study the in-built graph algorithms for better traversals and discover Spring-Data-Neo4j Look under the hood of Neo4j, covering concepts from the core classes in the source to the internal storage ...

    ProjectOZ

    The interrupt execution environment is recorded in a PCB and subsequent portal traversals chain PCBs as a stack. &lt;br&gt;Resume() restores the most recent PCB (analogous to a return-from-interrupt ...

    Android代码-probe

    Dissect layout traversals on Android. Features Intercept View methods. onMeasure(int, int) onLayout(boolean, int, int, int, int) draw(Canvas) and onDraw(Canvas) requestLayout() Override any of ...

Global site tag (gtag.js) - Google Analytics